ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Coloring Away Communication in Parallel Query Optimization.

Waqar Hasan, Rajeev Motwani: Coloring Away Communication in Parallel Query Optimization. VLDB 1995: 239-250
@inproceedings{DBLP:conf/vldb/HasanM95,
  author    = {Waqar Hasan and
               Rajeev Motwani},
  editor    = {Umeshwar Dayal and
               Peter M. D. Gray and
               Shojiro Nishio},
  title     = {Coloring Away Communication in Parallel Query Optimization},
  booktitle = {VLDB'95, Proceedings of 21th International Conference on Very
               Large Data Bases, September 11-15, 1995, Zurich, Switzerland},
  publisher = {Morgan Kaufmann},
  year      = {1995},
  isbn      = {1-55860-379-4},
  pages     = {239-250},
  ee        = {db/conf/vldb/HasanM95.html},
  crossref  = {DBLP:conf/vldb/95},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

We address the problem of finding parallel plans for SQL queries using thetwo-phase approach of join ordering and query rewrite (JOQR) followed by parallelization. We focus on the JOQR phase and develop optimization algorithms that account for communication as well as computation costs. Using a model based on representing the partitioning of data as a color, we devise an efficient algorithm for the problem of choosing the partitioning attributes in a query tree so as to minimize total cost. We extend our model and algorithm to incorporate the interaction of data partitioning with conventional optimization choices such as access methods and strategies for computing operators. Our algorithms apply to queries that include operators such as grouping, aggregation, intersection and set difference in addition to joins.

Copyright © 1995 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 ... BibTeX

Printed Edition

Umeshwar Dayal, Peter M. D. Gray, Shojiro Nishio (Eds.): VLDB'95, Proceedings of 21th International Conference on Very Large Data Bases, September 11-15, 1995, Zurich, Switzerland. Morgan Kaufmann 1995, ISBN 1-55860-379-4
Contents BibTeX

References

[BCC+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
[CHM95]
Chandra Chekuri, Waqar Hasan, Rajeev Motwani: Scheduling Problems in Parallel Query Optimization. PODS 1995: 255-265 BibTeX
[CLYY92]
Ming-Syan Chen, Ming-Ling Lo, Philip S. Yu, Honesty C. Young: Using Segmented Right-Deep Trees for the Execution of Pipelined Hash Joins. VLDB 1992: 15-26 BibTeX
[CP84]
Stefano Ceri, Giuseppe Pelagatti: Distributed Databases: Principles and Systems. McGraw-Hill Book Company 1984, ISBN 0-07-010829-3
BibTeX
[CR91]
...
[DG92]
David J. DeWitt, Jim Gray: Parallel Database Systems: The Future of High Performance Database Systems. Commun. ACM 35(6): 85-98(1992) BibTeX
[DGG+86]
David J. DeWitt, Robert H. Gerber, Goetz Graefe, Michael L. Heytens, Krishna B. Kumar, M. Muralikrishna: GAMMA - A High Performance Dataflow Database Machine. VLDB 1986: 228-237 BibTeX
[DJP+92]
Elias Dahlhaus, David S. Johnson, Christos H. Papadimitriou, Paul D. Seymour, Mihalis Yannakakis: The Complexity of Multiway Cuts (Extended Abstract). STOC 1992: 241-251 BibTeX
[EGH95]
Susanne Englert, Ray Glasstone, Waqar Hasan: Parallelism and its Price: A Case Study of NonStop SQL/MP. SIGMOD Record 24(4): 61-71(1995) BibTeX
[ES94]
...
[GHK92]
Sumit Ganguly, Waqar Hasan, Ravi Krishnamurthy: Query Optimization for Parallel Execution. SIGMOD Conference 1992: 9-18 BibTeX
[Gra88]
Jim Gray: The Cost of Messages. PODC 1988: 1-7 BibTeX
[Has95]
...
[HLY93]
Kien A. Hua, Yu-lung Lo, Honesty C. Young: Including the Load Balancing Issue in the Optimization of Multi-way Join Queries for Shared-Nothing Database Computers. PDIS 1993: 74-83 BibTeX
[HM94]
Waqar Hasan, Rajeev Motwani: Optimization Algorithms for Exploiting the Parallelism-Communication Tradeoff in Pipelined Parallelism. VLDB 1994: 36-47 BibTeX
[Hon92]
...
[HS91]
Wei Hong, Michael Stonebraker: Optimization of Parallel Query Execution Plans in XPRS. Distributed and Parallel Databases 1(1): 9-32(1993) BibTeX
[LST91]
Hongjun Lu, Ming-Chien Shan, Kian-Lee Tan: Optimization of Multi-Way Join Queries for Parallel Execution. VLDB 1991: 549-560 BibTeX
[OV91]
M. Tamer Özsu, Patrick Valduriez: Principles of Distributed Database Systems. Prentice-Hall 1991, ISBN 0-13-715681-2
BibTeX
[PMC+90]
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 BibTeX
[SAC+79]
Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, Thomas G. Price: Access Path Selection in a Relational Database Management System. SIGMOD Conference 1979: 23-34 BibTeX
[SE93]
Jaideep Srivastava, Gary Elsesser: Optimizing Multi-Join Queries in Parallel Relational Databases. PDIS 1993: 84-92 BibTeX
[SW91]
Dennis Shasha, Jason Tsong-Li Wang: Optimizing Equijoin Queries In Distributed Databases Where Relations Are Hash Partitioned. ACM Trans. Database Syst. 16(2): 279-308(1991) BibTeX
[SYT93]
Eugene J. Shekita, Honesty C. Young, Kian-Lee Tan: Multi-Join Optimization for Symmetric Multiprocessors. VLDB 1993: 479-492 BibTeX
[Val93]
Patrick Valduriez: Parallel Database Systems: Open Problems and New Issues. Distributed and Parallel Databases 1(2): 137-165(1993) BibTeX
[X3H92]
...
[YC84]
Clement T. Yu, C. C. Chang: Distributed Query Processing. ACM Comput. Surv. 16(4): 399-433(1984) BibTeX
[ZZBS93]
Mikal Ziane, Mohamed Zaït, Pascale Borla-Salamet: Parallel Query Processing in DBS3. PDIS 1993: 93-102 BibTeX

Referenced by

  1. Daniel F. Lieuwen: Parallelizing Loops in Database Programming Languages. ICDE 1998: 86-93
  2. Chandra Chekuri, Waqar Hasan, Rajeev Motwani: Scheduling Problems in Parallel Query Optimization. PODS 1995: 255-265
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:46:05 2009