Francis Chu
Johannes Gehrke
ABSTRACT
A standard assumption in the database query optimization literature is that it suffices to optimize for the "typical" case---that is, the case in which various parameters (e.g., the amount of available memory, the selectivities of predicates, etc.) take on their "typical" values. It was claimed in [CHS99] that we could do better by choosing plans based on their expected cost. Here we investigate this issue more thoroughly. We show that in many circumstances of interest, a "typical" value of the parameter often does give acceptable answers, provided that it is chosen carefully and we are interested only in minimizing expected running time. However, by minimizing the expected running time, we are effectively assuming that if plan p1 runs three times as long as plan p2, then p1 is exactly three times as bad as p2. An assumption like this is not always appropriate. We show that focusing on least expected cost can lead to significant improvement for a number of cost functions of interest.
- {CHS99} F. Chu, J. Y. Halpern, and P. Seshadri. Least expected cost query optimization: an exercise in utility. In Proceedings of the 18th ACM Symposium on Principles of Database Systems, pages 138-147, 1999. Google Scholar
Digital Library
- {CN00} S. Chaudhuri and V. R. Narasayya. Automating statistics management for query optimizers. In Proceedings of the 16th International Conference on Data Engineering, pages 339-348, 2000. Google ScholarDigital Library
- {GBC98} G. Graefe, R. Bunker, and S. Cooper. Hash joins and hash teams in Microsoft, SQL Server. In A. Gupta, O. Shmueli, and J. Widom, editors, VLDB'98, Proceedings of 24th International Conference on Very Large Data Bases, pages 86-97, 1998. Google ScholarDigital Library
- {HHW97} J. M. Hellerstein, P. J. Haas, and H. Wang. Online aggregation. In J. Peckham, editor, SIGMOD 1997, Proceedings ACM SIGMOD International Conference on Management of Data, pages 171-182, 1997. Google ScholarDigital Library
- {HKWY97} L. M. Haas, D. Kossmann, E. L. Wimmers, and J. Yang. Optimizing queries across diverse data sources. In M. Jarke, M. J. Carey, K. R. Dittrich, F. H. Lochovsky, P. Loucopoulos, and M. A. Jeusfeld, editors, Proceedings of 23rd International Conference on Very Large Data Bases, pages 276-285, 1997. Google ScholarDigital Library
- {INSS92} Y. Ioannidis, R. Ng, K. Shim, and T. K. Sellis. Parametric Query Optimization. In Proceedings of the 18th International Conference on Very Large Data Bases, pages 103-114, 1992. Google ScholarDigital Library
- {LG98} P. Larson and G. Graefe. Memory management during run generation in external sorting. In L. M. Haas and A. Tiwary, editors, SIGMOD 1998, Proceedings ACM SIGMOD International Conference on Management of Data, pages 472-483, 1998. Google ScholarDigital Library
- {ROH99) M. T. Roth, F. Özcan, and L. M. Haas. Cost models do matter: Providing cost information for diverse data sources in a federated system. In M. P. Atkinson, M. E. Orlowska, P. Valduriez, S. B. Zdonik, and M. L. Brodie, editors, Proceedings of 25th International Conference on Very Large Data Bases, pages 599-610, 1999. Google ScholarDigital Library
- {SAC+79} P. G. Selinger, M. Astrahan, D. Chamberlin, R. Loric, and T. Price. Access Path Selection in a Relational Database Management System. In Proceedings of ACM SIGMOD '79 International Conference on Management of Data, pages 23-34, 1979. Google ScholarDigital Library
- {SLMK01} M. Stillger, G. M. Lohman, V. Markl, and M. Kandil. LEO---DB2's LEarning Optimizer. In P. M. G. Apers, P. Atzeni, S. Ceri, S. Paraboschi, K. Ramamohanarao, and R. T. Snodgrass, editors, Proceedings of 27th International Conference on Very Large Data Bases, pages 19-28, 2001. Google ScholarDigital Library
- {TPPC99} Transaction Processing Performance Council. TPC Benchmark™ H (Decision Support) Standard Specification Revision 1.2.1. Transaction Processing Performance Council, 1999.Google Scholar
- {Ull89} J. D. Ullman. Principles of Database and Knowledge Base Systems, Volume II: The New Technologies. Computer Science Press, 1989. Google ScholarDigital Library
Index Terms
- Least expected cost query optimization: what can we expect?
Recommendations
Multi-objective parametric query optimization
Classical query optimization compares query plans according to one cost metric and associates each plan with a constant cost value. In this paper, we introduce the Multi-Objective Parametric Query Optimization (MPQ) problem where query plans are ...
Multi-objective parametric query optimization
Classical query optimization compares query plans according to one cost metric and associates each plan with a constant cost value. In this paper, we introduce the multi-objective parametric query optimization (MPQO) problem where query plans are ...
Comments