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

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}
}
BibTeX

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.

ACM SIGMOD Anthology

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 ... BibTeX

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 BibTeX , SIGMOD Record 23(2), June 1994
Contents

Online Edition: ACM Digital Library

[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 BibTeX
[BMG93]
José A. Blakeley, William J. McKenna, Goetz Graefe: Experiences Building the Open OODB Query Optimizer. SIGMOD Conference 1993: 287-296 BibTeX
[BPR90]
Peter Bodorik, James S. Pyra, J. Spruce Riordon: Correcting Execution of Distributed Queries. DPDS 1990: 192-201 BibTeX
[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) BibTeX
[Chr84]
Stavros Christodoulakis: Implications of Certain Assumptions in Database Performance Evaluation. ACM Trans. Database Syst. 9(2): 163-186(1984) BibTeX
[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) BibTeX
[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
BibTeX
[DMP93]
Marcia A. Derr, Shinichi Morishita, Geoffrey Phipps: Design and Implementation of the Glue-Nail Database System. SIGMOD Conference 1993: 147-156 BibTeX
[GHK92]
Sumit Ganguly, Waqar Hasan, Ravi Krishnamurthy: Query Optimization for Parallel Execution. SIGMOD Conference 1992: 9-18 BibTeX
[GrW89]
Goetz Graefe, Karen Ward: Dynamic Query Evaluation Plans. SIGMOD Conference 1989: 358-366 BibTeX
[Gra93]
Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993) BibTeX
[GrM93]
Goetz Graefe, William J. McKenna: The Volcano Optimizer Generator: Extensibility and Efficient Search. ICDE 1993: 209-218 BibTeX
[HaP88]
...
[HoS93]
Wei Hong, Michael Stonebraker: Optimization of Parallel Query Execution Plans in XPRS. Distributed and Parallel Databases 1(1): 9-32(1993) BibTeX
[IoC91]
Yannis E. Ioannidis, Stavros Christodoulakis: On the Propagation of Errors in the Size of Join Results. SIGMOD Conference 1991: 268-277 BibTeX
[INS92]
Yannis E. Ioannidis, Raymond T. Ng, Kyuseok Shim, Timos K. Sellis: Parametric Query Optimization. VLDB 1992: 103-114 BibTeX
[KGM91]
Thomas Keller, Goetz Graefe, David Maier: Efficient Assembly of Complex Objects. SIGMOD Conference 1991: 148-157 BibTeX
[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) BibTeX
[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 BibTeX
[OnL90]
Kiyoshi Ono, Guy M. Lohman: Measuring the Complexity of Join Enumeration in Query Optimization. VLDB 1990: 314-325 BibTeX
[OHM92]
Jack A. Orenstein, Sam Haradhvala, Benson Margulies, Don Sakahara: Query Processing in the ObjectStore Database System. SIGMOD Conference 1992: 403-412 BibTeX
[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 BibTeX
[SBM89]
...
[TsN92]
Manolis M. Tsangaris, Jeffrey F. Naughton: On the Performance of Object Clustering Techniques. SIGMOD Conference 1992: 144-153 BibTeX
[WoG93]
Richard H. Wolniewicz, Goetz Graefe: Algebraic Optimization of Computations over Scientific Databases. VLDB 1993: 13-24 BibTeX

Referenced by

  1. Ron Avnur, Joseph M. Hellerstein: Eddies: Continuously Adaptive Query Processing. SIGMOD Conference 2000: 261-272
  2. Peter A. Boncz, Martin L. Kersten: MIL Primitives for Querying a Fragmented World. VLDB J. 8(2): 101-119(1999)
  3. Zachary G. Ives, Daniela Florescu, Marc Friedman, Alon Y. Levy, Daniel S. Weld: An Adaptive Query Execution System for Data Integration. SIGMOD Conference 1999: 299-310
  4. Francis C. Chu, Joseph Y. Halpern, Praveen Seshadri: Least Expected Cost Query Optimization: An Exercise in Utility. PODS 1999: 138-147
  5. William O'Connell, Felipe Cariño, G. Linderman: Optimizer and Parallel Engine Extensions for Handling Expensive Methods Based on Large Objects. ICDE 1999: 304-313
  6. Daniela Florescu, Alon Y. Levy, Alberto O. Mendelzon: Database Techniques for the World-Wide Web: A Survey. SIGMOD Record 27(3): 59-74(1998)
  7. Sumit Ganguly: Design and Analysis of Parametric Query Optimization Algorithms. VLDB 1998: 228-238
  8. Felipe Cariño, William O'Connell: Plan-Per-Tuple Optimization Solution - Parallel Execution of Expensive User-Defined Functions. VLDB 1998: 690-695
  9. Tolga Urhan, Michael J. Franklin, Laurent Amsaleg: Cost Based Query Scrambling for Initial Delays. SIGMOD Conference 1998: 130-141
  10. Navin Kabra, David J. DeWitt: Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans. SIGMOD Conference 1998: 106-117
  11. Yannis E. Ioannidis, Raymond T. Ng, Kyuseok Shim, Timos K. Sellis: Parametric Query Optimization. VLDB J. 6(2): 132-151(1997)
  12. Sunita Sarawagi: Execution Reordering for Tertiary Memory Access. IEEE Data Eng. Bull. 20(3): 46-54(1997)
  13. Laurent Amsaleg, Philippe Bonnet, Michael J. Franklin, Anthony Tomasic, Tolga Urhan: Improving Responsiveness for Wide-Area Data Access. IEEE Data Eng. Bull. 20(3): 3-11(1997)
  14. Sunita Sarawagi, Michael Stonebraker: Reordering Query Execution in Tertiary Memory Databases. VLDB 1996: 156-167
  15. Hongjun Lu, Kian-Lee Tan, Son Dao: The Fittest Survives: An Adaptive Approach to Query Optimization. VLDB 1995: 251-262
  16. Staffan Flodin, Tore Risch: Processing Object-Oriented Queries with Invertible Late Bound Functions. VLDB 1995: 335-344
  17. Diane L. Davison, Goetz Graefe: Dynamic Resource Brokering for Multi-User Query Execution. SIGMOD Conference 1995: 281-292
  18. Marcelo F. Frias, Silvia E. Gordillo: Semantic Optimization of Queries in Deductive Object-Oriented Database. ADBIS 1995: 55-72
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: Wed Nov 19 18:53:47 2008