|
|
|
@inproceedings{DBLP:conf/vldb/HaradaNKT90,
author = {Lilian Harada and
Miyuki Nakano and
Masaru Kitsuregawa and
Mikio Takagi},
editor = {Dennis McLeod and
Ron Sacks-Davis and
Hans-J{\"o}rg Schek},
title = {Query Processing for Multi-Attribute Clustered Records},
booktitle = {16th International Conference on Very Large Data Bases, August
13-16, 1990, Brisbane, Queensland, Australia, Proceedings},
publisher = {Morgan Kaufmann},
year = {1990},
isbn = {1-55860-149-X},
pages = {59-70},
ee = {db/conf/vldb/HaradaNKT90.html},
crossref = {DBLP:conf/vldb/90},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
In this paper we introduce a new query processing method for multi-attribute clustered relations. Many proposals on multi-attribute clustered relations have been done so far. However, an efficient query processing method for these relations has not beenproposed and analyzed yet. The multi-attribute clustered relations treat all attributes symmetrically, atthe cost of losing the sequential data order between some specific pages. Thus, if the naive query processing methods used for single-attribute clustered relations, which rely on the sequential order of the clustered attribute, are straightly used for the multi-attribute clustered relations, it results in a high I/O cost.
Here, aiming at reducing this high I/O cost caused by the problem of no total order presented by the multi- attribute data, we introduce a query processing method which emphasizes the page loading strategy. In this query processing method we introduce a new concept called wave. Wave is a set of pages which represents the unit of loading from the secondarystorage to the main memory. Our query processing method uses the information of the multi-attribute clustering index to group pages, whose data are not ordered, into waves, which are ordered and must fit in the memory size as much as possible. Thus the execution of the relational operation for the tuples in the waves results in the execution of the whole multi-attribute clustered relation with theminimum I/O cost. We evaluate the proposed model using the KD-tree and the Grid-file, which are representative multi-attribute clustering methods. Simulation results show that this query processing method is efficient and thequeries for multi-attribute clustered relations can be executed with almost one relation scan, which is the lowest I/O bound.
Copyright © 1990 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.
