Identifying robust plans through plan diagram reduction
Authors:
Open Access
- 1 August 2008
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the VLDB Endowment
- Vol. 1 (1) , 1124-1140
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.Keywords
This publication has 15 references indexed in Scilit:
- Efficiently approximating query optimizer plan diagramsProceedings of the VLDB Endowment, 2008
- A critical look at the TAB benchmark for physical design toolsACM SIGMOD Record, 2007
- Adaptive Query ProcessingFoundations and Trends® in Databases, 2007
- Proactive re-optimization2005
- Robust query processing through progressive optimization2004
- Least expected cost query optimization2002
- Least expected cost query optimization1999
- A threshold of ln n for approximating set coverJournal of the ACM, 1998
- Accurate modeling of the hybrid hash join algorithm1994
- R* optimizer validation and performance evaluation for local queries1986