ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Dynamic Load Balancing in Hierarchical Parallel Database Systems.

Luc Bouganim, Daniela Florescu, Patrick Valduriez: Dynamic Load Balancing in Hierarchical Parallel Database Systems. VLDB 1996: 436-447
@inproceedings{DBLP:conf/vldb/BouganimFV96,
  author    = {Luc Bouganim and
               Daniela Florescu and
               Patrick Valduriez},
  editor    = {T. M. Vijayaraman and
               Alejandro P. Buchmann and
               C. Mohan and
               Nandlal L. Sarda},
  title     = {Dynamic Load Balancing in Hierarchical Parallel Database Systems},
  booktitle = {VLDB'96, Proceedings of 22th International Conference on Very
               Large Data Bases, September 3-6, 1996, Mumbai (Bombay), India},
  publisher = {Morgan Kaufmann},
  year      = {1996},
  isbn      = {1-55860-382-4},
  pages     = {436-447},
  ee        = {db/conf/vldb/BouganimFV96.html},
  crossref  = {DBLP:conf/vldb/96},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We consider the execution of complex, multi-join queries in a hierarchical parallel system, i.e., a shared-nothing system whose nodes are shared-memory multiprocessors. In a hierarchical system, load balancing must be addressed at two levels, locally among the processors of each shared-memory node and globally among all nodes. In this paper, we propose a new execution model that dynamically maximizes local load balancing within shared-memory nodes and reduces as much as possible the need for load sharing across nodes. This is obtained by allowing each processor to execute any operator that can be processed locally. Thus, our execution model can take full advantage of inter- and intra-operator parallelism that is present in complex queries. We conducted a performance evaluation using an implementation of our execution model on a 72-processor KSR computer. The experiments with local load balancing show very good speed-up, even with highly skewed data. Finally, the experiments with global load balancing show that local load balancing is always maximized, thereby achieving overall good performance.

Copyright © 1996 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

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

T. M. Vijayaraman, Alejandro P. Buchmann, C. Mohan, Nandlal L. Sarda (Eds.): VLDB'96, Proceedings of 22th International Conference on Very Large Data Bases, September 3-6, 1996, Mumbai (Bombay), India. Morgan Kaufmann 1996, ISBN 1-55860-382-4
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Electronic Edition

References

[Ape92]
Peter M. G. Apers, Carel A. van den Berg, Jan Flokstra, Paul W. P. J. Grefen, Martin L. Kersten, Annita N. Wilschut: PRISMA/DB: A Parallel Main Memory Relational DBMS. IEEE Trans. Knowl. Data Eng. 4(6): 541-554(1992) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ber92]
...
[Ber91]
Björn Bergsten, Michel Couprie, Patrick Valduriez: Prototyping DBS3, a Shared-Memory Parallel Database System. PDIS 1991: 226-234 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Bor90]
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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Bra84]
Kjell Bratbergsengen: Hashing Methods and Relational Algebra Operations. VLDB 1984: 323-333 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Bou96]
Luc Bouganim, Benoît Dageville, Patrick Valduriez: Adaptive Parallel Query Execution in DBS3. EDBT 1996: 481-484 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Dag94]
...
[DeW90]
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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[DeW92]
David J. DeWitt, Jeffrey F. Naughton, Donovan A. Schneider, S. Seshadri: Practical Skew Handling in Parallel Joins. VLDB 1992: 27-40 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Gar96]
Minos N. Garofalakis, Yannis E. Ioannidis: Multi-dimensional Resource Scheduling for Parallel Queries. SIGMOD Conference 1996: 365-376 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Gra93]
Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Has94]
Waqar Hasan, Rajeev Motwani: Optimization Algorithms for Exploiting the Parallelism-Communication Tradeoff in Pipelined Parallelism. VLDB 1994: 36-47 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Hon92]
Wei Hong: Exploiting Inter-Operation Parallelism in XPRS. SIGMOD Conference 1992: 19-28 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Hsi94]
Hui-I Hsiao, Ming-Syan Chen, Philip S. Yu: On Parallel Execution of Multiple Pipelined Hash Joins. SIGMOD Conference 1994: 185-196 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Kit90]
Masaru Kitsuregawa, Yasushi Ogawa: Bucket Spreading Parallel Hash: A New, Robust, Parallel Hash Join Method for Data Skew in the Super Database Computer (SDC). VLDB 1990: 210-221 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Lo93]
Ming-Ling Lo, Ming-Syan Chen, Chinya V. Ravishankar, Philip S. Yu: On Optimal Processor Allocation to Support Pipelined Hash Joins. SIGMOD Conference 1993: 69-78 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Lu91]
Hongjun Lu, Ming-Chien Shan, Kian-Lee Tan: Optimization of Multi-Way Join Queries for Parallel Execution. VLDB 1991: 549-560 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Meh95]
Manish Mehta, David J. DeWitt: Managing Intra-operator Parallelism in Parallel Database Systems. VLDB 1995: 382-394 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Pir90]
Hamid Pirahesh, C. Mohan, Josephine M. Cheng, T. S. Liu, Patricia G. Selinger: Parallelism in Relational Data Base Systems: Architectural Issues and Design Approaches. DPDS 1990: 4-29 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Rah95]
Erhard Rahm, Robert Marek: Dynamic Multi-Resource Load Balancing in Parallel Database Systems. VLDB 1995: 395-406 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Sha93]
Ambuj Shatdal, Jeffrey F. Naughton: Using Shared Virtual Memory for Parallel Join Processing. SIGMOD Conference 1993: 119-128 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[She93]
Eugene J. Shekita, Honesty C. Young, Kian-Lee Tan: Multi-Join Optimization for Symmetric Multiprocessors. VLDB 1993: 479-492 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Val84]
Patrick Valduriez, Georges Gardarin: Join and Semijoin Algorithms for a Multiprocessor Database Machine. ACM Trans. Database Syst. 9(1): 133-161(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Val93]
Patrick Valduriez: Parallel Database Systems: Open Problems and New Issues. Distributed and Parallel Databases 1(2): 137-165(1993) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Wal91]
Christopher B. Walton, Alfred G. Dale, Roy M. Jenevein: A Taxonomy and Performance Model of Data Skew Effects in Parallel Joins. VLDB 1991: 537-548 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Wil95]
Annita N. Wilschut, Jan Flokstra, Peter M. G. Apers: Parallel Evaluation of Multi-Join Queries. SIGMOD Conference 1995: 115-126 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Zip49]
George Kingsley Zipf: Human Behaviour and the Principle of Least Effort: an Introduction to Human Ecology. Addison-Wesley 1949
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Tue Mar 16 02:22:06 2010 by Michael Ley (ley@uni-trier.de)