Digital Symposium Collection 2000  

 
 
 
 
 
 

 


















Least Expected Cost Query Optimization: An Exercise in Utility

Francis Chu, Joseph Y. Halpern, and Praveen Seshadri

  View Paper (PDF)  

Return to Database Theory Sampler

Abstract
We identify two unreasonable, though standard, assumptions made by database query optimizers that can adversely affect the quality of t,he chosen evaluation plans. One assumption is that it is adequate to optimize for the expected case-that is, the case where various parameters (like available memory) take on their expected value. The other assumption is that the parameters are constant throughout the execution of the query. We present an algorithm based on the ‘System R”-s@ile query optimization algorithm that does not rely on these assumptions. The algorithm we propose chooses the plan of the least expected cost instead of the plan of least cost given expected values of the parameters. In execution environments that exhibit a high degree of variability, our techniques should result in better performance.


References

Note: References link to DBLP on the Web.

[Ant93]
Gennady Antoshenkov : Dynamic Query Optimization in Rdb/VMS. ICDE 1993 : 538-547
[GC94]
Richard L. Cole , Goetz Graefe : Optimization of Dynamic Query Evaluation Plans. SIGMOD Conference 1994 : 150-160
[Gra93]
Goetz Graefe : Query Evaluation Techniques for Large Databases. Computing Surveys 25(2) : 73-170(1993)
[IK90]
Yannis E. Ioannidis , Younkyung Cha Kang : Randomized Algorithms for Optimizing Large Join Queries. SIGMOD Conference 1990 : 312-321
[Ill94]
...
[INSS92]
Yannis E. Ioannidis , Raymond T. Ng , Kyuseok Shim , Timos K. Sellis : Parametric Query Optimization. VLDB 1992 : 103-114
[KD98]
Navin Kabra , David J. DeWitt : Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans. SIGMOD Conference 1998 : 106-117
[LNSS93]
Richard J. Lipton , Jeffrey F. Naughton , Donovan A. Schneider , S. Seshadri : Efficient Sampling Strategies for Relational Database Operations. TCS 116(1&2) : 195-226(1993)
[Loh98]
...
[Pea88]
...
[PHH92]
Hamid Pirahesh , Joseph M. Hellerstein , Waqar Hasan : Extensible/Rule Based Query Rewrite Optimization in Starburst. SIGMOD Conference 1992 : 39-48
[PIHS96]
Viswanath Poosala , Yannis E. Ioannidis , Peter J. Haas , Eugene J. Shekita : Improved Histograms for Selectivity Estimation of Range Predicates. SIGMOD Conf. 1996 : 294-305
[Res87]
...
[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
[SBM93]
...
[Sha86]
Leonard D. Shapiro : Join Processing in Database Systems with Large Main Memories. TODS 11(3) : 239-264(1986)
[Swa89]
Arun N. Swami : Optimization of Large Join Queries: Combining Heuristic and Combinatorial Techniques. SIGMOD Conference 1989 : 367-376
[UFA98]
Tolga Urhan , Michael J. Franklin , Laurent Amsaleg : Cost Based Query Scrambling for Initial Delays. SIGMOD Conference 1998 : 130-141

Referenced by

  1. Donko Donjerkovic , Raghu Ramakrishnan : Probabilistic Optimization of Top N Queries. VLDB 1999 : 411-422

BIBTEX

@inproceedings{DBLP:conf/pods/ChuHS99,
  author    = {Francis Chu and
                Joseph Y. Halpern and
                Praveen Seshadri},
   title     = {Least Expected Cost Query Optimization: An Exercise in Utility},
   booktitle = {Proceedings of the Eighteenth ACM SIGACT-SIGMOD-SIGART Symposium
                on Principles of Database Systems, May 31 - June 2, 1999, Philadelphia,
                Pennsylvania},
   publisher = {ACM Press},
   year      = {1999},
   isbn      = {1-58113-062-7},
   pages     = {138-147},
   crossref  = {DBLP:conf/pods/99},
   bibsource = {DBLP, http://dblp.uni-trier.de} } },


























Copyright(C) 2000 ACM