Coloring Away Communication in Parallel Query Optimization.

Waqar Hasan, Rajeev Motwani: Coloring Away Communication in Parallel Query Optimization. VLDB 1995: 239-250
  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,}


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


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
Chandra Chekuri, Waqar Hasan, Rajeev Motwani: Scheduling Problems in Parallel Query Optimization. PODS 1995: 255-265 BibTeX
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
Stefano Ceri, Giuseppe Pelagatti: Distributed Databases: Principles and Systems. McGraw-Hill Book Company 1984, ISBN 0-07-010829-3
David J. DeWitt, Jim Gray: Parallel Database Systems: The Future of High Performance Database Systems. Commun. ACM 35(6): 85-98(1992) BibTeX
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
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
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
Sumit Ganguly, Waqar Hasan, Ravi Krishnamurthy: Query Optimization for Parallel Execution. SIGMOD Conference 1992: 9-18 BibTeX
Jim Gray: The Cost of Messages. PODC 1988: 1-7 BibTeX
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
Waqar Hasan, Rajeev Motwani: Optimization Algorithms for Exploiting the Parallelism-Communication Tradeoff in Pipelined Parallelism. VLDB 1994: 36-47 BibTeX
Wei Hong, Michael Stonebraker: Optimization of Parallel Query Execution Plans in XPRS. Distributed and Parallel Databases 1(1): 9-32(1993) BibTeX
Hongjun Lu, Ming-Chien Shan, Kian-Lee Tan: Optimization of Multi-Way Join Queries for Parallel Execution. VLDB 1991: 549-560 BibTeX
M. Tamer Özsu, Patrick Valduriez: Principles of Distributed Database Systems. Prentice-Hall 1991, ISBN 0-13-715681-2
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
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
Jaideep Srivastava, Gary Elsesser: Optimizing Multi-Join Queries in Parallel Relational Databases. PDIS 1993: 84-92 BibTeX
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
Eugene J. Shekita, Honesty C. Young, Kian-Lee Tan: Multi-Join Optimization for Symmetric Multiprocessors. VLDB 1993: 479-492 BibTeX
Patrick Valduriez: Parallel Database Systems: Open Problems and New Issues. Distributed and Parallel Databases 1(2): 137-165(1993) BibTeX
Clement T. Yu, C. C. Chang: Distributed Query Processing. ACM Comput. Surv. 16(4): 399-433(1984) BibTeX
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
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:46:05 2009