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},
editor = {Richard Hull},
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}
}
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 ...
Printed Edition
Richard Hull (Ed.):
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 
[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
- [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)
- [DeWGra92]
- David J. DeWitt, Jim Gray:
Parallel Database Systems: The Future of High Performance Database Systems.
Commun. ACM 35(6): 85-98(1992)
- [Gan92]
- Sumit Ganguly:
Parallel Evaluation of Deductive Database Queries.
Ph.D. thesis, University of Texas, Austin 1992
- [GHK92]
- Sumit Ganguly, Waqar Hasan, Ravi Krishnamurthy:
Query Optimization for Parallel Execution.
SIGMOD Conference 1992: 9-18
- [GGMW]
- ...
- [GGJ78]
- ...
- [Goel95]
- ...
- [Gra69]
- Ronald L. Graham:
Bounds on Multiprocessing Timing Anomalies.
SIAM Journal of Applied Mathematics 17(2): 416-429(1969)
- [Gra66]
- ...
- [Hon91]
- Wei Hong, Michael Stonebraker:
Optimization of Parallel Query Execution Plans in XPRS.
PDIS 1991: 218-225
- [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
- [LST91]
- Hongjun Lu, Ming-Chien Shan, Kian-Lee Tan:
Optimization of Multi-Way Join Queries for Parallel Execution.
VLDB 1991: 549-560
- [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
- [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
- [SriEls93]
- Jaideep Srivastava, Gary Elsesser:
Optimizing Multi-Join Queries in Parallel Relational Databases.
PDIS 1993: 84-92
- [SYT93]
- Eugene J. Shekita, Honesty C. Young, Kian-Lee Tan:
Multi-Join Optimization for Symmetric Multiprocessors.
VLDB 1993: 479-492
- [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)
- [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
- [TWY92]
- ...
- [WC92]
- Qingzhou Wang, Kam-Hoi Cheng:
A Heuristic of Scheduling Parallel Tasks and its Analysis.
SIAM J. Comput. 21(2): 281-294(1992)
- [ZZBS94]
- Mikal Ziane, Mohamed Zaït, Pascale Borla-Salamet:
Parallel Query Processing in DBS3.
PDIS 1993: 93-102
Referenced by
- Clara Nippl, Bernhard Mitschang:
TOPAZ: a Cost-Based, Rule-Driven, Multi-Phase Parallelizer.
VLDB 1998: 251-262
- Janusz Charczuk:
Physical Structures Design For Relational Databases.
ADBIS 1998: 357-362
- Minos N. Garofalakis, Yannis E. Ioannidis:
Parallel Query Scheduling and Optimization with Time- and Space-Shared Resources.
VLDB 1997: 296-305
Last update Fri May 25 08:32:50 2012
CET by the DBLP Team — 
Data released under the ODC-BY 1.0 license — See also our legal information page
