Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans.
Navin Kabra, David J. DeWitt:
Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans.
SIGMOD Conference 1998: 106-117@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-995-5},
pages = {106-117},
ee = {http://doi.acm.org/10.1145/276304.276315, db/conf/sigmod/KabraD98.html},
crossref = {DBLP:conf/sigmod/98},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
Abstract
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.
Copyright © 1998 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.
CDROM Version: Load the CDROM "DiSC, Volume 1 Number 1" and ...
Online Version (ACM WWW Account required): Full Text in PDF Format
DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...
Printed Edition
Laura M. Haas, Ashutosh Tiwary (Eds.):
SIGMOD 1998, Proceedings ACM SIGMOD International Conference on Management of Data, June 2-4, 1998, Seattle, Washington, USA.
ACM Press 1998, ISBN 0-89791-995-5 
,
SIGMOD Record 27(2),
June 1998
Contents
[Abstract]
[Full Text (Postscript)]
References
- [1]
- Laurent Amsaleg, Michael J. Franklin, Anthony Tomasic, Tolga Urhan:
Scrambling Query Plans to Cope With Unexpected Delays.
PDIS 1996: 208-219
- [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.
J. Comput. Syst. Sci. 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 J. Ellmann, 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.
IEEE Data Eng. Bull. 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 Conference 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.
IEEE Data Eng. Bull. 10(2): 16-23(1987)
- [24]
- Jeffrey Scott Vitter:
Random Sampling with a Reservoir.
ACM Trans. Math. Softw. 11(1): 37-57(1985)
- [25]
- Eugene Wong, Karel Youssefi:
Decomposition - A Strategy for Query Processing.
ACM Trans. Database Syst. 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 J. 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
Copyright © Mon Mar 15 03:54:35 2010
by Michael Ley (ley@uni-trier.de)
