 |
|
|
Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans |
Full Paper (PDF)
|
For a number of reasons, even the best query optimizers can very often produce sub-optimal query execution plans, leading to a significant degradation of performance. This is especially true in databases used for complex decision support queries and/or object-relational databases. In this paper, we describe an algorithm that detects sub-optimality of a query execution plan during query execution and attempts to correct the problem. The basic idea is to collect statistics at key points during the execution of a complex query. These statistics are then used to optimize the execution of the query, either by improving the resource allocation for that query, or by changing the execution plan for the remainder of the query. To ensure that this does not significantly slow down the normal execution of a query, the Query Optimizer carefully chooses what statistics to collect, when to collect them, and the circumstances under which to re-optimize the query. We describe an implementation of this algorithm in the Paradise Database System, and we report on performance studies, which indicate that this can result in significant improvements in the performance of complex queries. |
References, where available, link to the DBLP on the World Wide Web.
[1]Laurent Amsaleg, Michael J. Franklin, Anthony Tomasic, Tolga Urhan:
Scrambling Query Plans to Cope With Unexpected Delays.
PDIS 1996: 0-[2]Gennady Antoshenkov:
Dynamic Query Optimization in Rdb/VMS.
ICDE 1993: 538-547[3]Gennady Antoshenkov:
Dynamic Optimization of Index Scans Restricted by Booleans.
ICDE 1996: 430-440[4]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[5]...
[6]Philippe Flajolet, G. Nigel Martin:
Probabilistic Counting Algorithms for Data Base Applications.
JCSS 31(2): 182-209(1985)[7]Richard L. Cole, Goetz Graefe:
Optimization of Dynamic Query Evaluation Plans.
SIGMOD Conference 1994: 150-160[8]Goetz Graefe, Karen Ward:
Dynamic Query Evaluation Plans.
SIGMOD Conference 1989: 358-366[9]Yannis E. Ioannidis, Stavros Christodoulakis:
On the Propagation of Errors in the Size of Join Results.
SIGMOD Conference 1991: 268-277[10]Yannis E. Ioannidis, Raymond T. Ng, Kyuseok Shim, Timos K. Sellis:
Parametric Query Optimization.
VLDB 1992: 103-114[11]Yannis E. Ioannidis, Viswanath Poosala:
Balancing Histogram Optimality and Practicality for Query Result Size Estimation.
SIGMOD Conference 1995: 233-244[12]...
[13]...
[14]Manish Mehta, David J. DeWitt:
Dynamic Memory Allocation for Multiple-Query Workloads.
VLDB 1993: 354-367[15]...
[16]Kiyoshi Ono, Guy M. Lohman:
Measuring the Complexity of Join Enumeration in Query Optimization.
VLDB 1990: 314-325[17]Jignesh M. Patel, Jie-Bing Yu, Navin Kabra, Kristin Tufte, Biswadeep Nag, Josef Burger, Nancy E. Hall, Karthikeyan Ramasamy, Roger Lueder, Curt Ellman, Jim Kupsch, Shelly Guo, David J. DeWitt, Jeffrey F. Naughton:
Building a Scaleable Geo-Spatial DBMS: Technology, Implementation, and Evaluation.
SIGMOD Conference 1997: 336-347[18]...
[19]Yannis E. Ioannidis, Viswanath Poosala:
Histogram-Based Solutions to Diverse Database Estimation Problems.
Data Engineering Bulletin 18(3): 10-18(1995)[20]Viswanath Poosala, Yannis E. Ioannidis, Peter J. Haas, Eugene J. Shekita:
Improved Histograms for Selectivity Estimation of Range Predicates.
SIGMOD Conf. 1996: 294-305[21]...
[22]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[23]Michael Stonebraker, Jeff Anton, Michael Hirohama:
Extendability in POSTGRES.
Data Engineering Bulletin 10(2): 16-23(1987)[24]Jeffrey Scott Vitter:
Random Sampling with a Reservoir.
TOMS 11(1): 37-57(1985)[25]Eugene Wong, Karel Youssefi:
Decomposition - A Strategy for Query Processing.
TODS 1(3): 223-241(1976)[26]Philip S. Yu, Douglas W. Cornell:
Buffer Management Based on Return on Consumption in a Multi-Query Environment.
VLDB Journal 2(1): 1-37(1993)[27]George Kingsley Zipf:
Human Behaviour and the Principle of Least Effort: an Introduction to Human Ecology.
Addison-Wesley 1949
|
@inproceedings{DBLP:conf/sigmod/KabraD98,
author = {Navin Kabra and
David J. DeWitt},
editor = {Laura M. Haas and
Ashutosh Tiwary},
title = {Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution
Plans},
booktitle = {SIGMOD 1998, Proceedings ACM SIGMOD International Conference
on Management of Data, June 2-4, 1998, Seattle, Washington, USA},
publisher = {ACM Press},
year = {1998},
isbn = {0-89791-955-5},
pages = {106-117},
crossref = {DBLP:conf/sigmod/98},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
|
DBLP: Copyright ©1999 by Michael Ley (ley@uni-trier.de).
|
|
