A Performance Analysis of Alternative Multi-Attribute Declustering Strategies.

@inproceedings{DBLP:conf/sigmod/GhandeharizadehDQ92,
  author    = {Shahram Ghandeharizadeh and
               David J. DeWitt and
               Waheed Qureshi},
  editor    = {Michael Stonebraker},
  title     = {A Performance Analysis of Alternative Multi-Attribute Declustering
               Strategies},
  booktitle = {Proceedings of the 1992 ACM SIGMOD International Conference on
               Management of Data, San Diego, California, June 2-5, 1992},
  publisher = {ACM Press},
  year      = {1992},
  pages     = {29-38},
  ee        = {http://doi.acm.org/10.1145/130283.130293, db/conf/sigmod/GhandeharizadehDQ92.html},
  crossref  = {DBLP:conf/sigmod/92},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

During the past decade, parallel database systems have gained increased popularity due to their high performance, scalability and availability characteristics. With the predicted future database sizes and the complexity of queries, the scalability of these systems to hundreds and thousands of processors is essential for satisfying the projected demand. Several studies have repeatedly demonstrated that both the performance and scalability of a parallel database system is contingent on the physical layout of data across the processors of the system. If the data is not declustered properly, the execution of an operator might waste resources, reducing the overall processing capability of the system.

With earlier, single attribute declustering strategies, such as those found in Tandem, Teradata, Gamma, and Bubba parallel database systems, a selection query including a range predicate on any attribute other than the partitioning attribute must be sent to all processors containing tuples of the relation. By directing a query with minimal resource requirements to processors that contain no relevant tuples, the system wastes CPU cycles, communication bandwidth, and I/O bandwidth, reducing its overall processing capability. As a solution, several multi-attribute declustering strategies have been proposed. However, the performance of these declustering techniques have not previously been compared to one another nor with a single attribute partitioning strategy. This paper, compares the performance of Multi-Attribute Grid deClustering (MAGIC) strategy and Bubba's Extended Range Declustering (BERD) strategy with one another and with the range partitioning strategy. Our results indicate that MAGIC outperforms both range and BERD in all experiments conducted in this study.

Copyright © 1992 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

• 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/smod7592 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

Online Edition: ACM Digital Library

References

[BAC+90]

Haran Boral, William Alexander, Larry Clay, George P. Copeland, Scott Danforth, Michael J. Franklin, Brian E. Hart, Marc G. Smith, Patrick Valduriez: Prototyping Bubba, A Highly Parallel Database System. IEEE Trans. Knowl. Data Eng. 2(1): 4-24(1990) BibTeX

[BDC83]

Dina Bitton, David J. DeWitt, Carolyn Turbyfill: Benchmarking Database Systems A Systematic Approach. VLDB 1983: 8-19 BibTeX

[CABK88]

George P. Copeland, William Alexander, Ellen E. Boughter, Tom W. Keller: Data Placement In Bubba. SIGMOD Conference 1988: 99-108 BibTeX

[DGS+90]

David J. DeWitt, Shahram Ghandeharizadeh, Donovan A. Schneider, Allan Bricker, Hui-I Hsiao, Rick Rasmussen: The Gamma Database Machine Project. IEEE Trans. Knowl. Data Eng. 2(1): 44-62(1990) BibTeX

[GD90]

Shahram Ghandeharizadeh, David J. DeWitt: A Multiuser Performance Analysis of Alternative Declustering Strategies. ICDE 1990: 466-475 BibTeX

[Gha90]

...

[GMSY90]

...

[Gra89]

...

[Hsi90]

...

[Liv88]

...

[LKB87]

Miron Livny, Setrag Khoshafian, Haran Boral: Multi-Disk Management Algorithms. SIGMETRICS 1987: 69-77 BibTeX

[NHS84]

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

[RE78]

...

[Sch90]

...

[SPO88]

Michael Stonebraker, Randy H. Katz, David A. Patterson, John K. Ousterhout: The Design of XPRS. VLDB 1988: 318-330 BibTeX

[Tan88]

The Tandem Performance Group: A Benchmark of NonStop SQL on the Debit Credit Transaction (Invited Paper). SIGMOD Conference 1988: 337-341 BibTeX

[Ter85]

...

[TP72]

Toby J. Teorey, Tad B. Pinkerton: A Comparative Analysis of Disk Scheduling Policies. Commun. ACM 15(3): 177-184(1972) BibTeX

Referenced by

1. Uwe Röhm, Klemens Böhm, Hans-Jörg Schek: OLAP Query Routing and Physical Design in a Database Cluster. EDBT 2000: 254-268
2. Bongki Moon, Joel H. Saltz: Scalability Analysis of Declustering Methods for Multidimensional Range Queries. IEEE Trans. Knowl. Data Eng. 10(2): 310-327(1998)
3. Manish Mehta, David J. DeWitt: Data Placement in Shared-Nothing Parallel Database Systems. VLDB J. 6(1): 53-72(1997)
4. Khaled A. S. Abdel-Ghaffar, Amr El Abbadi: Optimal Allocation of Two-Dimensional Data. ICDT 1997: 409-418
5. Nick Koudas, Christos Faloutsos, Ibrahim Kamel: Declustering Spatial Databases on a Multi-Computer Architecture. EDBT 1996: 592-614
6. Nick Bassiliades, Ioannis P. Vlahavas: A Non-Uniform Data Fragmentation Strategy for Parallel Main-Menory Database Systems. VLDB 1995: 370-381
7. Erik G. Hoel, Hanan Samet: Performance of Data-Parallel Spatial Operations. VLDB 1994: 156-167
8. Bhaskar Himatsingka, Jaideep Srivastava: Performance Evaluation of Grid Based Multi-Attibute Record Declustering Methods. ICDE 1994: 356-365
9. Shahram Ghandeharizadeh, David Wilhite, Kai-Ming Lin, Xiaoming Zhao: Object Placement in Parallel Object-Oriented Database Systems. ICDE 1994: 253-262