Parametric Query Optimization.
Yannis E. Ioannidis, Raymond T. Ng, Kyuseok Shim, Timos K. Sellis:
Parametric Query Optimization.
VLDB J. 6(2): 132-151(1997)@article{DBLP:journals/vldb/IoannidisNSS97,
author = {Yannis E. Ioannidis and
Raymond T. Ng and
Kyuseok Shim and
Timos K. Sellis},
title = {Parametric Query Optimization},
journal = {VLDB J.},
volume = {6},
number = {2},
year = {1997},
pages = {132-151},
ee = {db/journals/vldb/IoannidisNSS97.html},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX
Abstract
In most database systems, the values of many important run-time parameters of the system, the data, or the query are unknown at query optimization time.
Parametric query optimization attempts to identify at compile time several execution plans, each one of which is optimal for a subset of all possible values of the run-time parameters.
The goal is that at run time, when the actual parameter values are known, the appropriate plan should be identifiable with essentially no overhead.
We present a general formulation of this problem and study it primarily for the buffer size parameter.
We adopt randomized algorithms as the main approach to this style of optimization and enhance them with a sideways information passing feature that increases their effectiveness in the new task.
Experimental results of these enhanced algorithms show that they optimize queries for large numbers of buffer sizes in the same time needed by their conventional versions for a single buffer size, without much sacrifice in the output quality and with essentially zero run-time overhead.
Key Words
Copyright © 1997 by Springer, Berlin, Heidelberg.
Permission to make digital or hard copies of the abstract is granted provided that copies are not made or distributed for profit or
direct commercial advantage, and that copies show this notice along with the full citation.
Citation Page
CDROM Version: Load the CDROM "Volume 4 Issue 1, Books, VLDB-j, TODS, ..." and ...
DVD Version: Load ACM SIGMOD Anthology DVD 2" and ...
BibTeX
References
- [CG94]
- Richard L. Cole, Goetz Graefe:
Optimization of Dynamic Query Evaluation Plans.
SIGMOD Conference 1994: 150-160 BibTeX
- [CY89]
- Douglas W. Cornell, Philip S. Yu:
Integration of Buffer Management and Query Optimization in Relational Database Environment.
VLDB 1989: 247-255 BibTeX
- [FNS91]
- Christos Faloutsos, Raymond T. Ng, Timos K. Sellis:
Predictive Load Control for Flexible Buffer Allocation.
VLDB 1991: 265-274 BibTeX
- [GM91]
- ...
- [GW89]
- Goetz Graefe, Karen Ward:
Dynamic Query Evaluation Plans.
SIGMOD Conference 1989: 358-366 BibTeX
- [HP88]
- ...
- [HS91]
- Wei Hong, Michael Stonebraker:
Optimization of Parallel Query Execution Plans in XPRS.
PDIS 1991: 218-225 BibTeX
- [IK90]
- Yannis E. Ioannidis, Younkyung Cha Kang:
Randomized Algorithms for Optimizing Large Join Queries.
SIGMOD Conference 1990: 312-321 BibTeX
- [IK91]
- Yannis E. Ioannidis, Younkyung Cha Kang:
Left-Deep vs. Bushy Trees: An Analysis of Strategy Spaces and its Implications for Query Optimization.
SIGMOD Conference 1991: 168-177 BibTeX
- [IW87]
- Yannis E. Ioannidis, Eugene Wong:
Query Optimization by Simulated Annealing.
SIGMOD Conference 1987: 9-22 BibTeX
- [Kan91]
- Younkyung Cha Kang:
Randomized Algorithms for Query Optimization.
Ph.D. thesis, Univ. of Wisconsin-Madison 1991
BibTeX
- [KGV83]
- ...
- [ML86]
- Lothar F. Mackert, Guy M. Lohman:
R* Optimizer Validation and Performance Evaluation for Local Queries.
SIGMOD Conference 1986: 84-95 BibTeX
- [NFS91]
- Raymond T. Ng, Christos Faloutsos, Timos K. Sellis:
Flexible Buffer Allocation Based on Marginal Gains.
SIGMOD Conference 1991: 387-396 BibTeX
- [NSS86]
- ...
- [SAC+79]
- 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
- [SG88]
- Arun N. Swami, Anoop Gupta:
Optimization of Large Join Queries.
SIGMOD Conference 1988: 8-17 BibTeX
- [Sha86]
- Leonard D. Shapiro:
Join Processing in Database Systems with Large Main Memories.
ACM Trans. Database Syst. 11(3): 239-264(1986) BibTeX
- [SKPO88]
- Michael Stonebraker, Randy H. Katz, David A. Patterson, John K. Ousterhout:
The Design of XPRS.
VLDB 1988: 318-330 BibTeX
- [Ull82]
- Jeffrey D. Ullman:
Principles of Database Systems, 2nd Edition.
Computer Science Press 1982, ISBN 0-914894-36-6
BibTeX
Referenced by
- Ron Avnur, Joseph M. Hellerstein:
Eddies: Continuously Adaptive Query Processing.
SIGMOD Conference 2000: 261-272
BibTeX
ACM SIGMOD Anthology - DBLP:
[Home | Search: Author, Title | Conferences | Journals]
VLDB Journal: 1992-1995 Copyright © by VLDB Endowment / 1996-... Copyright © by Springer Verlag,
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sun May 17 00:31:30 2009