research-article

Identifying robust plans through plan diagram reduction

Authors:

Pooja N. Darera,

Jayant R. HaritsaAuthors Info & Claims

Proceedings of the VLDB Endowment, Volume 1, Issue 1

Pages 1124 - 1140

https://doi.org/10.14778/1453856.1453976

Published: 01 August 2008 Publication History

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.

Digital Library

[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.

Digital Library

[3]

S. Babu, P. Bizarro and D. DeWitt, "Proactive Re-Optimization", Proc. of ACM SIGMOD Intl. Conf. on Management of Data, June 2005.

Digital Library

[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.

Digital Library

[5]

N. Bruno, "A Critical Look at the TAB Benchmark for Physical Design Tools", SIGMOD Record, 36(4), 2007.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[9]

A. Deshpande, Z. Ives and V. Raman "Adaptive Query Processing", Foundations and Trends in Databases, 2007.

Digital Library

[10]

U. Feige, "A threshold of In n for approximating set cover", Journal of ACM, 45(4), 1998.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[23]

P. Slavik, "A tight analysis of the greedy algorithm for set cover", Proc. of 28th ACM Symp. on Theory of Computing, 1996.

Digital Library

[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.

Digital Library

[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

Cited By

Justen DRitter DFraser CLamb ALee ABodner THaddad MZeuch SMarkl VBoehm M(2024)POLAR: Adaptive and Non-invasive Join Order Selection via Plans of Least ResistanceProceedings of the VLDB Endowment10.14778/3648160.364817517:6(1350-1363)Online publication date: 3-May-2024
https://dl.acm.org/doi/10.14778/3648160.3648175
Yan YWang HHuang JZhong DYu TZhang KYang MWang T(2024)QCFE: An Efficient Feature Engineering for Query Cost Estimation2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00328(4302-4315)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00328
Zhu RChen WDing BChen XPfadler AWu ZZhou J(2023)Lero: A Learning-to-Rank Query OptimizerProceedings of the VLDB Endowment10.14778/3583140.358316016:6(1466-1479)Online publication date: 1-Feb-2023
https://dl.acm.org/doi/10.14778/3583140.3583160
Show More Cited By

Index Terms

Identifying robust plans through plan diagram reduction

Recommendations

Plan bouquets: query processing without selectivity estimation
SIGMOD '14: Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data

Selectivity estimates for optimizing OLAP queries often differ significantly from those actually encountered during query execution, leading to poor plan choices and inflated response times. We propose here a conceptually new approach to address this ...
Plan Bouquets: A Fragrant Approach to Robust Query Processing
Invited Paper from SIGMOD 2014 and Regular Papers

Identifying efficient execution plans for declarative OLAP queries typically entails estimation of several predicate selectivities. In practice, these estimates often differ significantly from the values actually encountered during query execution, ...
Looking ahead makes query plans robust: making the initial case with in-memory star schema data warehouse workloads

Query optimizers and query execution engines cooperate to deliver high performance on complex analytic queries. Typically, the optimizer searches through the plan space and sends a selected plan to the execution engine. However, optimizers may at times ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Proceedings of the VLDB Endowment

Proceedings of the VLDB Endowment Volume 1, Issue 1

August 2008

1216 pages

ISSN:2150-8097

Issue’s Table of Contents

Publisher

VLDB Endowment

Publication History

Published: 01 August 2008

Published in PVLDB Volume 1, Issue 1

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

21
Total Citations
View Citations
207
Total Downloads

Downloads (Last 12 months)8
Downloads (Last 6 weeks)1

Reflects downloads up to 13 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Justen DRitter DFraser CLamb ALee ABodner THaddad MZeuch SMarkl VBoehm M(2024)POLAR: Adaptive and Non-invasive Join Order Selection via Plans of Least ResistanceProceedings of the VLDB Endowment10.14778/3648160.364817517:6(1350-1363)Online publication date: 3-May-2024
https://dl.acm.org/doi/10.14778/3648160.3648175
Yan YWang HHuang JZhong DYu TZhang KYang MWang T(2024)QCFE: An Efficient Feature Engineering for Query Cost Estimation2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00328(4302-4315)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00328
Zhu RChen WDing BChen XPfadler AWu ZZhou J(2023)Lero: A Learning-to-Rank Query OptimizerProceedings of the VLDB Endowment10.14778/3583140.358316016:6(1466-1479)Online publication date: 1-Feb-2023
https://dl.acm.org/doi/10.14778/3583140.3583160
Trummer IWang JWei ZMaram DMoseley SJo SAntonakakis JRayabhari A(2021)SkinnerDB: Regret-bounded Query Evaluation via Reinforcement LearningACM Transactions on Database Systems10.1145/346438946:3(1-45)Online publication date: 28-Sep-2021
https://dl.acm.org/doi/10.1145/3464389
Haritsa J(2020)Robust query processingProceedings of the VLDB Endowment10.14778/3415478.341556113:12(3425-3428)Online publication date: 1-Aug-2020
https://dl.acm.org/doi/10.14778/3415478.3415561
Trummer IWang JMaram DMoseley SJo SAntonakakis JBoncz PManegold SAilamaki ADeshpande AKraska T(2019)SkinnerDBProceedings of the 2019 International Conference on Management of Data10.1145/3299869.3300088(1153-1170)Online publication date: 25-Jun-2019
https://dl.acm.org/doi/10.1145/3299869.3300088
Karthik SHaritsa JKenkre SPandit V(2018)A concave path to low-overhead robust query processingProceedings of the VLDB Endowment10.14778/3275366.328496411:13(2183-2195)Online publication date: 1-Sep-2018
https://dl.acm.org/doi/10.14778/3275366.3284964
Wolf FBrendle MMay NWillems PSattler KGrossniklaus M(2018)Robustness metrics for relational query execution plansProceedings of the VLDB Endowment10.14778/3236187.323619111:11(1360-1372)Online publication date: 1-Jul-2018
https://dl.acm.org/doi/10.14778/3236187.3236191
Trummer IMoseley SMaram DJo SAntonakakis J(2018)SkinnerDBProceedings of the VLDB Endowment10.14778/3229863.323626311:12(2074-2077)Online publication date: 1-Aug-2018
https://dl.acm.org/doi/10.14778/3229863.3236263
Wolf FMay NWillems PSattler KDas GJermaine CBernstein P(2018)On the Calculation of Optimality Ranges for Relational Query Execution PlansProceedings of the 2018 International Conference on Management of Data10.1145/3183713.3183742(663-675)Online publication date: 27-May-2018
https://dl.acm.org/doi/10.1145/3183713.3183742
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents