Identifying robust plans through plan diagram reduction

Abstract

Estimates of predicate selectivities by database query optimizers often differ significantly from those actually encountered during query execution, leading to poor plan choices and inflated response times. In this paper, we investigate mitigating this problem by replacing selectivity error-sensitive plan choices with alternative plans that provide robust performance. Our approach is based on the recent observation that even the complex and dense "plan diagrams" associated with industrial-strength optimizers can be efficiently reduced to "anorexic" equivalents featuring only a few plans, without materially impacting query processing quality.

Extensive experimentation with a rich set of TPC-H and TPC-DS-based query templates in a variety of database environments indicate that plan diagram reduction typically retains plans that are substantially resistant to selectivity errors on the base relations. However, it can sometimes also be severely counter-productive, with the replacements performing much worse. We address this problem through a generalized mathematical characterization of plan cost behavior over the parameter space, which lends itself to efficient criteria of when it is safe to reduce. Our strategies are fully non-invasive and have been implemented in the Picasso optimizer visualization tool.

References

1. A. Aboulnaga and S. Chaudhuri, "Self-tuning Histograms: Building Histograms without Looking at Data", Proc. of ACM SIGMOD Intl. Conf. on Management of Data, May 1999.
2. B. Babcock and S. Chaudhuri, "Towards a Robust Query Optimizer: A Principled and Practical Approach", Proc. of ACM SIGMOD Intl. Conf. on Management of Data, June 2005.
3. S. Babu, P. Bizarro and D. DeWitt, "Proactive Re-Optimization", Proc. of ACM SIGMOD Intl. Conf. on Management of Data, June 2005.
4. S. Babu, P. Bizarro and D. DeWitt, "Proactive Re-Optimization with Rio", Proc. of ACM SIGMOD Intl. Conf. on Management of Data, June 2005.
5. N. Bruno, "A Critical Look at the TAB Benchmark for Physical Design Tools", SIGMOD Record, 36(4), 2007.
6. F. Chu, J. Halpern and P. Seshadri, "Least Expected Cost Query Optimization: An Exercise in Utility", Proc. of ACM Symp. on Principles of Database Systems (PODS), May 1999.
7. A. Dey, S. Bhaumik, Harish D. and J. Haritsa, "Efficiently Approximating Query Optimizer Plan Diagrams", Proc. of 34th Intl. Conf. on Very Large Data Bases (VLDB), August 2008.
8. F. Chu, J. Halpern and J. Gehrke, "Least Expected Cost Query Optimization: What Can We Expect", Proc. of ACM Symp. on Principles of Database Systems (PODS), May 2002.
9. A. Deshpande, Z. Ives and V. Raman "Adaptive Query Processing", Foundations and Trends in Databases, 2007.
10. U. Feige, "A threshold of In n for approximating set cover", Journal of ACM, 45(4), 1998.
11. Harish D., P. Darera and J. Haritsa, "On the Production of Anorexic Plan Diagrams", Proc. of 33rd Intl. Conf. on Very Large Data Bases (VLDB), September 2007.
12. Harish D., P. Darera and J. Haritsa, "Robust Plans through Plan Diagram Reduction", Tech. Rep. TR-2007-02, DSL/SERC, Indian Inst. of Science, 2007. http://dsl.serc.iisc.ernet.in/publications/report/TR/TR-2007-02.pdf
13. A. Hulgeri and S. Sudarshan, "Parametric Query Optimization for Linear and Piecewise Linear Cost Functions", Proc. of 28th Intl. Conf. on Very Large Data Bases (VLDB), August 2002.
14. A. Hulgeri and S. Sudarshan, "AniPQO: Almost Non-intrusive Parametric Query Optimization for Nonlinear Cost Functions", Proc. of 29th Intl. Conf. on Very Large Data Bases (VLDB), September 2003.
15. Y. Ioannidis and S. Christodoulakis, "On the Propagation of Errors in the Size of Join Results", Proc. of ACM SIGMOD Intl. Conf. on Management of Data, May 1991.
16. N. Kabra and D. DeWitt, "Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans", Proc. of ACM SIGMOD Intl. Conf. on Management of Data, May 1998.
17. E. Kreyszig, Advanced Engineering Mathematics, New Age International, 5th ed, 1997.
18. L. Mackert and G. Lohman, "R* Optimizer Validation and Performance Evaluation for Local Queries", Proc. of ACM SIGMOD Intl. Conf. on Management of Data, May 1986.
19. V. Markl, V. Raman, D. Simmen, G. Lohman, H. Pirahesh and M. Cilimdzic, "Robust Query Processing through Progressive Optimization", Proc. of ACM SIGMOD Intl. Conf. on Management of Data, June 2004.
20. J. Patel, M. Carey and M. Vernon, "Accurate Modeling of the Hybrid Hash Join Algorithm", Proc. of ACM SIGMETRICS Intl. Conf. on Measurement and Modeling of Computer Systems, May 1994.
21. Picasso Database Query Optimizer Visualizer, http://dsl.serc.iise.ernet.in/projects/PICASSO/picasso.html
22. N. Reddy and J. Haritsa, "Analyzing Plan Diagrams of Database Query Optimizers", Proc. of 31st Intl. Conf. on Very Large Data Bases (VLDB), August 2005.
23. P. Slavik, "A tight analysis of the greedy algorithm for set cover", Proc. of 28th ACM Symp. on Theory of Computing, 1996.
24. M. Stillger, G. Lohman, V. Markl and M. Kandil, "LEO -- DB2's LEarning Optimizer", Proc. of 27th Intl. Conf. on Very Large Data Bases (VLDB), September 2001.
25. MATLAB, http://www.mathworks.com
26. http://www.tpc.org/tpch
27. http://www.tpc.org/tpcds
28. http://publib.boulder.ibm.com/infocenter/db2luw/v9/index.jsp?topic=/com. ibm.db2.udb.admin.doc/doc/t0024533.htm
29. http://msdn2.microsoft.com/en-us/library/ms189298.aspx
30. http://infocenter.sybase.com/help/index.jsp?topic=/com.sybase. dc34982_1500/html/mig_gde/BABIFCAF.htm

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Planning and scheduling

• Information systems

  • Data management systems

    • Database management system engines

      • Database query processing

  • Information retrieval

    • Evaluation of retrieval results

    • Information retrieval query processing

    • Retrieval models and ranking

• Theory of computation

  • Theory and algorithms for application domains

    • Database theory

      • Database query processing and optimization (theory)