ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

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
@inproceedings{DBLP:conf/pods/GangulyGS96,
  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,
               Canada},
  publisher = {ACM Press},
  year      = {1996},
  isbn      = {0-89791-781-2},
  pages     = {172-181},
  ee        = {http://doi.acm.org/10.1145/237661.237707, db/conf/pods/GangulyGS96.html},
  crossref  = {DBLP:conf/pods/96},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

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]

References

[BB90]
Krishna P. Belkhale, Prithviraj Banerjee: An Approximate Algorithm for the Partitionable Independent Task Scheduling Problem. ICPP (1) 1990: 72-75 BibTeX
[DGS+]
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
[DeWGra92]
David J. DeWitt, Jim Gray: Parallel Database Systems: The Future of High Performance Database Systems. Commun. ACM 35(6): 85-98(1992) BibTeX
[Gan92]
Sumit Ganguly: Parallel Evaluation of Deductive Database Queries. Ph.D. thesis, University of Texas, Austin 1992
BibTeX
[GHK92]
Sumit Ganguly, Waqar Hasan, Ravi Krishnamurthy: Query Optimization for Parallel Execution. SIGMOD Conference 1992: 9-18 BibTeX
[GGMW]
...
[GGJ78]
...
[Goel95]
...
[Gra69]
Ronald L. Graham: Bounds on Multiprocessing Timing Anomalies. SIAM Journal of Applied Mathematics 17(2): 416-429(1969) BibTeX
[Gra66]
...
[Hon91]
Wei Hong, Michael Stonebraker: Optimization of Parallel Query Execution Plans in XPRS. PDIS 1991: 218-225 BibTeX
[LVZ93]
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
[LST91]
Hongjun Lu, Ming-Chien Shan, Kian-Lee Tan: Optimization of Multi-Way Join Queries for Parallel Execution. VLDB 1991: 549-560 BibTeX
[NSHL93]
...
[RSB94]
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
[Sch90]
...
[SAC+]
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
[SriEls93]
Jaideep Srivastava, Gary Elsesser: Optimizing Multi-Join Queries in Parallel Relational Databases. PDIS 1993: 84-92 BibTeX
[SYT93]
Eugene J. Shekita, Honesty C. Young, Kian-Lee Tan: Multi-Join Optimization for Symmetric Multiprocessors. VLDB 1993: 479-492 BibTeX
[TL94]
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
[TWPY92]
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
[TWY92]
...
[WC92]
Qingzhou Wang, Kam-Hoi Cheng: A Heuristic of Scheduling Parallel Tasks and its Analysis. SIAM J. Comput. 21(2): 281-294(1992) BibTeX
[ZZBS94]
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
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
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:34:15 2009