Query Processing for Multi-Attribute Clustered Records.

@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}
}

Abstract

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.

Online Paper

• Download PDF file (www.vldb.org, Darmstadt, Germany)
• Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD Anthology

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/vldb8997 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

Printed Edition

References

[1]

Jon Louis Bentley: Multidimensional Binary Search Trees Used for Associative Searching. Commun. ACM 18(9): 509-517(1975) BibTeX

[2]

Jon Louis Bentley: Multidimensional Binary Search Trees in Database Applications. IEEE Trans. Software Eng. 5(4): 333-340(1979) BibTeX

[3]

Jo-Mei Chang, King-sun Fu: A Dynamic Clustering Technique for Physical Database Design. SIGMOD Conference 1980: 188-199 BibTeX

[4]

David J. DeWitt, Randy H. Katz, Frank Olken, Leonard D. Shapiro, Michael Stonebraker, David A. Wood: Implementation Techniques for Main Memory Database Systems. SIGMOD Conference 1984: 1-8 BibTeX

[5]

Michael Freeston: The BANG File: A New Kind of Grid File. SIGMOD Conference 1987: 260-269 BibTeX

[6]

Shinya Fushimi, Masaru Kitsuregawa, Masaya Nakayama, Hidehiko Tanaka, Tohru Moto-Oka: Algorithm and Performance Evaluation of Adaptive Multidimensional Clustering Technique. SIGMOD Conference 1985: 308-318 BibTeX

[7]

...

[8]

Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57 BibTeX

[9]

...

[10]

...

[11]

Andreas Henrich, Hans-Werner Six, Peter Widmayer: The LSD tree: Spatial Access to Multidimensional Point and Nonpoint Objects. VLDB 1989: 45-53 BibTeX

[12]

Andreas Hutflesz, Hans-Werner Six, Peter Widmayer: Twin Grid Files: Space Optimizing Access Schemes. SIGMOD Conference 1988: 183-190 BibTeX

[13]

Masaru Kitsuregawa, Hidehiko Tanaka, Tohru Moto-Oka: Application of Hash to Data Base Machine and Its Architecture. New Generation Comput. 1(1): 63-74(1983) BibTeX

[14]

Masaru Kitsuregawa, Masaya Nakayama, Mikio Takagi: The Effect of Bucket Size Tuning in the Dynamic Hybrid GRACE Hash Join Method. VLDB 1989: 257-266 BibTeX

[15]

Masaru Kitsuregawa, Lilian Harada, Mikio Takagi: Join Strategies on KB-Tree Indexed Relations. ICDE 1989: 85-93 BibTeX

[16]

Hans-Peter Kriegel, Bernhard Seeger: PLOP-Hashing: A Grid File without Directory. ICDE 1988: 369-376 BibTeX

[17]

...

[18]

David B. Lomet, Betty Salzberg: A Robust Multi-Attribute Search Structure. ICDE 1989: 296-304 BibTeX

[19]

Jürg Nievergelt, Hans Hinterberger, Kenneth C. Sevcik: The Grid File: An Adaptable, Symmetric Multikey File Structure. ACM Trans. Database Syst. 9(1): 38-71(1984) BibTeX

[20]

Esen A. Ozkarahan, Aris M. Ouksel: Dynamic and Order Preserving Data Partitioning for Database Machines. VLDB 1985: 358-368 BibTeX

[21]

John T. Robinson: The K-D-B-Tree: A Search Structure For Large Multidimensional Dynamic Indexes. SIGMOD Conference 1981: 10-18 BibTeX

Referenced by

1. Volker Markl, Martin Zirkel, Rudolf Bayer: Processing Operations with Restrictions in RDBMS without External Sorting: The Tetris Algorithm. ICDE 1999: 562-571
2. Jignesh M. Patel, David J. DeWitt: Partition Based Spatial-Merge Join. SIGMOD Conference 1996: 259-270
3. Thomas A. Mück, Manfred J. Schauer: Optimizing Sort Order Query Execution in Balanced and Nested Grid Files. IEEE Trans. Knowl. Data Eng. 7(2): 246-260(1995)
4. Sang-Wook Kim, Wan-Sup Cho, Min-Jae Lee, Kyu-Young Whang: A New Algorithm for Processing Joins Using the Multilevel Grid File. DASFAA 1995: 115-123
5. Jaideep Srivastava, Thomas M. Niccum, Bhaskar Himatsingka: Data Declustering in PADMA: A PArallel Database MAnager. IEEE Data Eng. Bull. 17(3): 3-13(1994)
6. Bhaskar Himatsingka, Jaideep Srivastava: Performance Evaluation of Grid Based Multi-Attibute Record Declustering Methods. ICDE 1994: 356-365
7. Thomas Brinkhoff, Hans-Peter Kriegel, Bernhard Seeger: Efficient Processing of Spatial Joins Using R-Trees. SIGMOD Conference 1993: 237-246
8. Priti Mishra, Margaret H. Eich: Join Processing in Relational Databases. ACM Comput. Surv. 24(1): 63-113(1992)