Optimization of Dynamic Query Evaluation Plans.
Richard L. Cole, Goetz Graefe:
Optimization of Dynamic Query Evaluation Plans.
SIGMOD Conference 1994: 150-160@inproceedings{DBLP:conf/sigmod/ColeG94,
author = {Richard L. Cole and
Goetz Graefe},
editor = {Richard T. Snodgrass and
Marianne Winslett},
title = {Optimization of Dynamic Query Evaluation Plans},
booktitle = {Proceedings of the 1994 ACM SIGMOD International Conference on
Management of Data, Minneapolis, Minnesota, May 24-27, 1994},
publisher = {ACM Press},
year = {1994},
pages = {150-160},
ee = {http://doi.acm.org/10.1145/191839.191872, db/conf/sigmod/ColeG94.html},
crossref = {DBLP:conf/sigmod/94},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
Abstract
Traditional query optimizers assume accurate knowledge of run-time parameters
such as selectivities and resource availability during plan optimization, i.e.,
at compile-time. In reality, however, this assumption is often not justified.
Therefore, the "static" plans produced by traditional optimizers may not be
optimal for many of their actual run-time invocations. Instead, we propose a
novel optimization model that assigns the bulk of the optimization effort to
compile-time and delays carefully selected optimization decisions until
run-time. Our previous work defined the run-time primitives, "dynamic plans"
using "choose-plan" operators, for executing such delayed decisions, but did
not solve the problem of constructing dynamic plans at compile-time. The
present paper introduces techniques that solve this problem. Experience with
a working prototype optimizer demonstrates
(i) that the additional optimizationand start-up overhead of dynamic plans
compared to static plans is dominated bytheir advantage at run-time,
(ii) that dynamic plans are as robust as the
"brute-force" remedy of run-time optimization, i.e., dynamic plans maintain
their optimality even if parameters change between compile-time and run-time,
and (iii) that the start-up overhead of dynamic plans is significantly less
than the time required for complete optimization at run-time. In other words,
our proposed techniques are superior to both techniques considered to-date,
namely compile-time optimization into a single static plan as well as run-time
optimization. Finally, we believe that the concepts and technology described
can be transferred to commercial query optimizers in order to improve the
performance of embedded queries with host variables in the query predicate and
to adapt to run-time system loads unpredictable at compile-time.
Copyright © 1994 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.
Online Version (ACM WWW Account required): Full Text in PDF Format
CDROM Version: Load the CDROM "Volume 1 Issue 1, SIGMOD '93-'97" and ...
DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...
Printed Edition
Richard T. Snodgrass, Marianne Winslett (Eds.):
Proceedings of the 1994 ACM SIGMOD International Conference on Management of Data, Minneapolis, Minnesota, May 24-27, 1994.
ACM Press 1994 
,
SIGMOD Record 23(2),
June 1994
Contents
[Abstract and Index Terms]
[Full Text in PDF Format, 1415 KB]
References
- [Ant93]
- Gennady Antoshenkov:
Dynamic Query Optimization in Rdb/VMS.
ICDE 1993: 538-547
- [BMG93]
- José A. Blakeley, William J. McKenna, Goetz Graefe:
Experiences Building the Open OODB Query Optimizer.
SIGMOD Conference 1993: 287-296
- [BPR90]
- Peter Bodorik, James S. Pyra, J. Spruce Riordon:
Correcting Execution of Distributed Queries.
DPDS 1990: 192-201
- [CAK81]
- Donald D. Chamberlin, Morton M. Astrahan, W. Frank King III, Raymond A. Lorie, James W. Mehl, Thomas G. Price, Mario Schkolnick, Patricia G. Selinger, Donald R. Slutz, Bradford W. Wade, Robert A. Yost:
Support for Repetitive Transactions and Ad Hoc Queries in System R.
ACM Trans. Database Syst. 6(1): 70-94(1981)
- [Chr84]
- Stavros Christodoulakis:
Implications of Certain Assumptions in Database Performance Evaluation.
ACM Trans. Database Syst. 9(2): 163-186(1984)
- [CAB93]
- Richard L. Cole, Mark J. Anderson, Robert J. Bestgen:
Query Processing in the IBM Application System/400.
IEEE Data Eng. Bull. 16(4): 19-28(1993)
- [CLR89]
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest:
Introduction to Algorithms.
The MIT Press and McGraw-Hill Book Company 1989, ISBN 0-262-03141-8,0-07-013143-0
- [DMP93]
- Marcia A. Derr, Shinichi Morishita, Geoffrey Phipps:
Design and Implementation of the Glue-Nail Database System.
SIGMOD Conference 1993: 147-156
- [GHK92]
- Sumit Ganguly, Waqar Hasan, Ravi Krishnamurthy:
Query Optimization for Parallel Execution.
SIGMOD Conference 1992: 9-18
- [GrW89]
- Goetz Graefe, Karen Ward:
Dynamic Query Evaluation Plans.
SIGMOD Conference 1989: 358-366
- [Gra93]
- Goetz Graefe:
Query Evaluation Techniques for Large Databases.
ACM Comput. Surv. 25(2): 73-170(1993)
- [GrM93]
- Goetz Graefe, William J. McKenna:
The Volcano Optimizer Generator: Extensibility and Efficient Search.
ICDE 1993: 209-218
- [HaP88]
- ...
- [HoS93]
- Wei Hong, Michael Stonebraker:
Optimization of Parallel Query Execution Plans in XPRS.
Distributed and Parallel Databases 1(1): 9-32(1993)
- [IoC91]
- Yannis E. Ioannidis, Stavros Christodoulakis:
On the Propagation of Errors in the Size of Join Results.
SIGMOD Conference 1991: 268-277
- [INS92]
- Yannis E. Ioannidis, Raymond T. Ng, Kyuseok Shim, Timos K. Sellis:
Parametric Query Optimization.
VLDB 1992: 103-114
- [KGM91]
- Thomas Keller, Goetz Graefe, David Maier:
Efficient Assembly of Complex Objects.
SIGMOD Conference 1991: 148-157
- [Loh89]
- ...
- [MaL89]
- Lothar F. Mackert, Guy M. Lohman:
Index Scans Using a Finite LRU Buffer: A Validated I/O Model.
ACM Trans. Database Syst. 14(3): 401-424(1989)
- [MHW90]
- C. Mohan, Donald J. Haderle, Yun Wang, Josephine M. Cheng:
Single Table Access Using Multiple Indexes: Optimization, Execution, and Concurrency Control Techniques.
EDBT 1990: 29-43
- [OnL90]
- Kiyoshi Ono, Guy M. Lohman:
Measuring the Complexity of Join Enumeration in Query Optimization.
VLDB 1990: 314-325
- [OHM92]
- Jack A. Orenstein, Sam Haradhvala, Benson Margulies, Don Sakahara:
Query Processing in the ObjectStore Database System.
SIGMOD Conference 1992: 403-412
- [SAC79]
- 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
- [SBM89]
- ...
- [TsN92]
- Manolis M. Tsangaris, Jeffrey F. Naughton:
On the Performance of Object Clustering Techniques.
SIGMOD Conference 1992: 144-153
- [WoG93]
- Richard H. Wolniewicz, Goetz Graefe:
Algebraic Optimization of Computations over Scientific Databases.
VLDB 1993: 13-24
Copyright © Thu Dec 24 17:06:25 2009
by Michael Ley (ley@uni-trier.de)
