Efficient and Acurate Cost Models for Parallel Query Optimization.

Sumit Ganguly, Akshay Goel, Abraham Silberschatz: Efficient and Acurate Cost Models for Parallel Query Optimization. PODS 1996: 172-181
  author    = {Sumit Ganguly and
               Akshay Goel and
               Abraham Silberschatz},
  title     = {Efficient and Acurate Cost Models for Parallel Query Optimization},
  booktitle = {Proceedings of the Fifteenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, June 3-5, 1996, Montreal,
  publisher = {ACM Press},
  year      = {1996},
  isbn      = {0-89791-781-2},
  pages     = {172-181},
  ee        = {, db/conf/pods/GangulyGS96.html},
  crossref  = {DBLP:conf/pods/96},
  bibsource = {DBLP,}


One of the key problems in the design of a query optimizer for parallel databases is the derivation of efficient and accurate cost models. These cost models rely on accurate estimators for the response time of a query, which can only be obtained by invoking expensive scheduling algorithms. To achieve efficiency, cost models must estimate the response time using approximation functions. In this paper, we consider the issue of design and validation of cost models for SQL-query optimizers for parallel executions. We present a theoretical foundation underlying the design of efficient cost models that accurately approximate response time. Based on the above theoretical foundation, we formulate two heuristical cost functions. We use simulations to determine the accuracy of these heuristic functions. Our simulation results indicate that the heuristic cost functions generate plans whose performance is within 20-60% of the optimal scheduled plan for 90-95% of the queries.

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

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Fifteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 3-5, 1996, Montreal, Canada. ACM Press 1996, ISBN 0-89791-781-2
Contents BibTeX

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 1039 KB]


Krishna P. Belkhale, Prithviraj Banerjee: An Approximate Algorithm for the Partitionable Independent Task Scheduling Problem. ICPP (1) 1990: 72-75 BibTeX
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
David J. DeWitt, Jim Gray: Parallel Database Systems: The Future of High Performance Database Systems. Commun. ACM 35(6): 85-98(1992) BibTeX
Sumit Ganguly: Parallel Evaluation of Deductive Database Queries. Ph.D. thesis, University of Texas, Austin 1992
Sumit Ganguly, Waqar Hasan, Ravi Krishnamurthy: Query Optimization for Parallel Execution. SIGMOD Conference 1992: 9-18 BibTeX
Ronald L. Graham: Bounds on Multiprocessing Timing Anomalies. SIAM Journal of Applied Mathematics 17(2): 416-429(1969) BibTeX
Wei Hong, Michael Stonebraker: Optimization of Parallel Query Execution Plans in XPRS. PDIS 1991: 218-225 BibTeX
Rosana S. G. Lanzelotte, Patrick Valduriez, Mohamed Zaït: On the Effectiveness of Optimization Search Strategies for Parallel Execution Spaces. VLDB 1993: 493-504 BibTeX
Hongjun Lu, Ming-Chien Shan, Kian-Lee Tan: Optimization of Multi-Way Join Queries for Parallel Execution. VLDB 1991: 549-560 BibTeX
Shankar Ramaswamy, Sachin S. Sapatnekar, Prithviraj Banerjee: A Convex Programming Approach for Exploiting Data and Functional Parallelism on Distributed Memory Multicomputers. ICPP 1994: 116-125 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
Eugene J. Shekita, Honesty C. Young, Kian-Lee Tan: Multi-Join Optimization for Symmetric Multiprocessors. VLDB 1993: 479-492 BibTeX
Kian-Lee Tan, Hongjun Lu: On Resource Scheduling of Multi-Join Queries in Parallel Database Systems. Inf. Process. Lett. 48(4): 189-195(1993) BibTeX
John Turek, Joel L. Wolf, Krishna R. Pattipati, Philip S. Yu, Icel Wolf: Scheduling Parallelizable Tasks: Putting it All on the Shelf. SIGMETRICS 1992: 225-236 BibTeX
Qingzhou Wang, Kam-Hoi Cheng: A Heuristic of Scheduling Parallel Tasks and its Analysis. SIAM J. Comput. 21(2): 281-294(1992) BibTeX
Mikal Ziane, Mohamed Zaït, Pascale Borla-Salamet: Parallel Query Processing in DBS3. PDIS 1993: 93-102 BibTeX

Referenced by

  1. Clara Nippl, Bernhard Mitschang: TOPAZ: a Cost-Based, Rule-Driven, Multi-Phase Parallelizer. VLDB 1998: 251-262
  2. Janusz Charczuk: Physical Structures Design For Relational Databases. ADBIS 1998: 357-362
  3. Minos N. Garofalakis, Yannis E. Ioannidis: Parallel Query Scheduling and Optimization with Time- and Space-Shared Resources. VLDB 1997: 296-305
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:34:15 2009