Query processing method for multi-attribute clustered relations
Lilian Harada, Miyuki Nakano, Masaru Kitsuregawa, Mikio Takagi · Very Large Data Bases · 1990
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 been proposed and analyzed yet. The multi-attribute clustered relations treat all attributes symmetrically, at the 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 ID cost caused by the problem of no total order presented by the multiattribute 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 secondary storage 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 the minimum 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