More Web Proxy on the site http://driver.im/

research-article

Plan stitch: harnessing the best of many plans

Authors:

Surajit Chaudhuri,

Vivek NarasayyaAuthors Info & Claims

Proceedings of the VLDB Endowment, Volume 11, Issue 10

Pages 1123 - 1136

https://doi.org/10.14778/3231751.3231761

Published: 01 June 2018 Publication History

Abstract

Query performance regression due to the query optimizer selecting a bad query execution plan is a major pain point in production workloads. Commercial DBMSs today can automatically detect and correct such query plan regressions by storing previously-executed plans and reverting to a previous plan which is still valid and has the least execution cost. Such reversion-based plan correction has relatively low risk of plan regression since the decision is based on observed execution costs. However, this approach ignores potentially valuable information of efficient subplans collected from other previously-executed plans. In this paper, we propose a novel technique, Plan Stitch, that automatically and opportunistically combines efficient subplans of previously-executed plans into a valid new plan, which can be cheaper than any individual previously-executed plan. We implement Plan Stitch on top of Microsoft SQL Server. Our experiments on TPC-DS benchmark and three real-world customer workloads show that plans obtained via Plan Stitch can reduce execution cost significantly, with a reduction of up to two orders of magnitude in execution cost when compared to reverting to the cheapest previously-executed plan.

References

[1]

A. Aboulnaga and S. Chaudhuri. Self-tuning Histograms: Building Histograms Without Looking at Data. In Proceedings of the 1999 ACM SIGMOD International Conference on Management of Data, pages 181--192, 1999.

Digital Library

[2]

Access Plan in IBM DB2. https://www.ibm.com/support/knowledgecenter/en/SSEPGG_11.1.0/com.ibm.db2.luw.admin.explain.doc/doc/c0021356.html.

[3]

M. Akdere, U. Çetintemel, M. Riondato, E. Upfal, and S. B. Zdonik. Learning-based Query Performance Modeling and Prediction. In Proceedings of the 2012 IEEE 28th International Conference on Data Engineering, pages 390--401, 2012.

Digital Library

[4]

APPLY Operator in Microsoft SQL Server. https://social.technet.microsoft.com/wiki/contents/articles/6525.apply-operator-in-sql-server.aspx.

[5]

Automatic Plan Correction in Microsoft SQL Server 2017 and Azure SQL Database. https://docs.microsoft.com/en-us/sql/relational-databases/automatic-tuning/automatic-tuning.

[6]

SQL Plan Management with Oracle Database 12c. http://www.oracle.com/technetwork/database/bi-datawarehousing/twp-sql-plan-mgmt-12c-1963237.pdf.

[7]

Automatic Statistics Update in Microsoft SQL Server. https://docs.microsoft.com/en-us/sql/relational-databases/statistics/statistics.

[8]

Automatic Index Tuning in Azure SQL Database. https://blogs.msdn.microsoft.com/sqlserverstorageengine/2017/05/16/automatic-index-management-in-azure-sql-db/.

[9]

Azure SQL Database. https://azure.microsoft.com/en-us/services/sql-database/.

[10]

B. Babcock and S. Chaudhuri. Towards a Robust Query Optimizer: A Principled and Practical Approach. In Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data, pages 119--130, 2005.

Digital Library

[11]

N. Bruno and S. Chaudhuri. Exploiting Statistics on Query Expressions for Optimization. In Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data, pages 263--274, 2002.

Digital Library

[12]

N. Bruno and S. Chaudhuri. Automatic Physical Database Tuning: A Relaxation-based Approach. In Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data, pages 227--238, 2005.

Digital Library

[13]

N. Bruno and S. Chaudhuri. To Tune or Not to Tune?: A Lightweight Physical Design Alerter. In Proceedings of the 32nd International Conference on Very Large Data Bases, pages 499--510, 2006.

Digital Library

[14]

N. Bruno, S. Chaudhuri, and L. Gravano. STHoles: A Multidimensional Workload-aware Histogram. SIGMOD Rec., 30(2):211--222, May 2001.

Digital Library

[15]

N. Bruno, S. Chaudhuri, and R. Ramamurthy. Power Hints for Query Optimization. In Proceedings of the 2009 IEEE International Conference on Data Engineering, pages 469--480, 2009.

Digital Library

[16]

S. Chaudhuri, V. Narasayya, and R. Ramamurthy. A pay-as-you-go framework for query execution feedback. PVLDB, 1(1):1141--1152, 2008.

Digital Library

[17]

C. M. Chen and N. Roussopoulos. Adaptive Selectivity Estimation Using Query Feedback. In Proceedings of the 1994 ACM SIGMOD International Conference on Management of Data, pages 161--172, 1994.

Digital Library

[18]

Creating and deploying optimization hints for SQL statements that run on DB2 for z/OS. https://www.ibm.com/support/knowledgecenter/SS7LB8_4.1.0/com.ibm.datatools.qrytune.sngqry.doc/topics/reviewingvph.html.

[19]

A. Dutt, V. Narasayya, and S. Chaudhuri. Leveraging Re-costing for Online Optimization of Parameterized Queries with Guarantees. In Proceedings of the 2017 ACM International Conference on Management of Data, pages 1539--1554, 2017.

Digital Library

[20]

A. Ganapathi, H. Kuno, U. Dayal, J. L. Wiener, A. Fox, M. Jordan, and D. Patterson. Predicting Multiple Metrics for Queries: Better Decisions Enabled by Machine Learning. In Proceedings of the 2009 IEEE International Conference on Data Engineering, pages 592--603, 2009.

Digital Library

[21]

S. Ganguly. Design and Analysis of Parametric Query Optimization Algorithms. In Proceedings of the 24rd International Conference on Very Large Data Bases, pages 228--238, 1998.

Digital Library

[22]

A. Ghosh, J. Parikh, V. S. Sengar, and J. R. Haritsa. Plan Selection Based on Query Clustering. In Proceedings of the 28th International Conference on Very Large Data Bases, pages 179--190, 2002.

Digital Library

[23]

J. Goldstein and P.-A. Larson. Optimizing Queries Using Materialized Views: A Practical, Scalable Solution. SIGMOD Rec., 30(2):331--342, May 2001.

Digital Library

[24]

G. Graefe and W. J. McKenna. The Volcano Optimizer Generator: Extensibility and Efficient Search. In Proceedings of the Ninth International Conference on Data Engineering, pages 209--218, Washington, DC, USA, 1993.

Digital Library

[25]

H. Hacigumus, Y. Chi, W. Wu, S. Zhu, J. Tatemura, and J. F. Naughton. Predicting Query Execution Time: Are Optimizer Cost Models Really Unusable? In Proceedings of the 2013 IEEE International Conference on Data Engineering, pages 1081--1092, 2013.

Digital Library

[26]

H. Herodotou and S. Babu. Xplus: a sql-tuning-aware query optimizer. PVLDB, 3(1-2):1149--1160, 2010.

Digital Library

[27]

A. Hulgeri and S. Sudarshan. AniPQO: Almost Non-intrusive Parametric Query Optimization for Nonlinear Cost Functions. In Proceedings of the 29th International Conference on Very Large Data Bases, pages 766--777, 2003.

Digital Library

[28]

Y. E. Ioannidis, R. T. Ng, K. Shim, and T. K. Sellis. Parametric Query Optimization. The VLDB Journal, 6(2):132--151, May 1997.

Digital Library

[29]

Y. E. Ioannidis and R. Ramakrishnan. Containment of Conjunctive Queries: Beyond Relations As Sets. ACM Trans. Database Syst., 20(3):288--324, Sept. 1995.

Digital Library

[30]

P.-A. Larson, W. Lehner, J. Zhou, and P. Zabback. Cardinality Estimation Using Sample Views with Quality Assurance. In Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data, pages 175--186, 2007.

Digital Library

[31]

V. Leis, A. Gubichev, A. Mirchev, P. Boncz, A. Kemper, and T. Neumann. How Good Are Query Optimizers, Really? PVLDB, 9(3):204--215, Nov. 2015.

Digital Library

[32]

J. Li, A. C. König, V. Narasayya, and S. Chaudhuri. Robust Estimation of Resource Consumption for SQL Queries Using Statistical Techniques. PVLDB, 5(11):1555--1566, July 2012.

Digital Library

[33]

V. Markl, P. J. Haas, M. Kutsch, N. Megiddo, U. Srivastava, and T. M. Tran. Consistent Selectivity Estimation via Maximum Entropy. The VLDB Journal, 16(1):55--76, Jan. 2007.

Digital Library

[34]

Database Performance Tuning Guide - Using Optimizer Hints. https://docs.oracle.com/cd/B19306_01/server.102/b14211/hintsref.htm#i8327.

[35]

S. Papadomanolakis, D. Dash, and A. Ailamaki. Efficient Use of the Query Optimizer for Automated Physical Design. In Proceedings of the 33rd International Conference on Very Large Data Bases, pages 1093--1104, 2007.

Digital Library

[36]

Microsoft SQL Server Plan Guides. https://docs.microsoft.com/en-us/sql/relational-databases/performance/plan-guides.

[37]

Microsoft SQL Server Query Store. https://docs.microsoft.com/en-us/sql/relational-databases/performance/monitoring-performance-by-using-the-query-store.

[38]

Microsoft Query Hints. https://docs.microsoft.com/en-us/sql/t-sql/queries/hints-transact-sql-query.

[39]

P. Roy, S. Seshadri, S. Sudarshan, and S. Bhobe. Efficient and Extensible Algorithms for Multi Query Optimization. In Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data, pages 249--260, 2000.

Digital Library

[40]

P. G. Selinger, M. M. Astrahan, D. D. Chamberlin, R. A. Lorie, and T. G. Price. Access Path Selection in a Relational Database Management System. In Proceedings of the 1979 ACM SIGMOD International Conference on Management of Data, pages 23--34, 1979.

Digital Library

[41]

Statistics XML in Microsoft SQL Server. https://docs.microsoft.com/en-us/sql/t-sql/statements/set-statistics-xml-transact-sql.

[42]

Showplan XML Schema in Microsoft SQL Server. schemas.microsoft.com/sqlserver/2004/07/showplan/.

[43]

M. Stillger, G. M. Lohman, V. Markl, and M. Kandil. LEO - DB2's LEarning Optimizer. In Proceedings of the 27th International Conference on Very Large Data Bases, pages 19--28, 2001.

Digital Library

[44]

TPC Benchmark DS: Standard Specification v2.6.0. http://www.tpc.org/tpcds/.

[45]

TPC-DS Tools. http://www.tpc.org/tpc_documents_current_versions/current_specifications.asp.

[46]

Microsoft SQL Server USE PLAN Query Hint. https://technet.microsoft.com/en-us/library/ms186954(v=sql.105).aspx.

[47]

W. Wu, J. F. Naughton, and H. Singh. Sampling-Based Query Re-Optimization. In Proceedings of the 2016 International Conference on Management of Data, pages 1721--1736, 2016.

Digital Library

Cited By

Bianchi AChai ACorvinelli VGodfrey PSzlichta JZuzarte C(2024)Db2une: Tuning Under Pressure via Deep LearningProceedings of the VLDB Endowment10.14778/3685800.368581117:12(3855-3868)Online publication date: 8-Nov-2024
https://dl.acm.org/doi/10.14778/3685800.3685811
Siddiqui TWu W(2024)ML-Powered Index Tuning: An Overview of Recent Progress and Open ChallengesACM SIGMOD Record10.1145/3641832.364183652:4(19-30)Online publication date: 19-Jan-2024
https://dl.acm.org/doi/10.1145/3641832.3641836
Song HZhou WLi FPeng XCui H(2023)Rethink Query Optimization in HTAP DatabasesProceedings of the ACM on Management of Data10.1145/36267501:4(1-27)Online publication date: 12-Dec-2023
https://dl.acm.org/doi/10.1145/3626750
Show More Cited By

Recommendations

Continuing plan quality optimisation

Finding high quality plans for large planning problems is hard. Although some current anytime planners are often able to improve plans quickly, they tend to reach a limit at which the plans produced are still very far from the best possible, but these ...
Plan stability: replanning versus plan repair
ICAPS'06: Proceedings of the Sixteenth International Conference on International Conference on Automated Planning and Scheduling

The ultimate objective in planning is to construct plans for execution. However, when a plan is executed in a real environment it can encounter differences between the expected and actual context of execution. These differences can manifest as ...
Plan reuse in conformant planning

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 11, Issue 10

June 2018

248 pages

ISSN:2150-8097

Editors:
Jian Pei
Simon Fraser University
,
Sihem Amer-Yahia
University of Grenoble Alpes, CNRS

Issue’s Table of Contents

Publisher

VLDB Endowment

Publication History

Published: 01 June 2018

Published in PVLDB Volume 11, Issue 10

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
162
Total Downloads

Downloads (Last 12 months)20
Downloads (Last 6 weeks)2

Reflects downloads up to 14 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Bianchi AChai ACorvinelli VGodfrey PSzlichta JZuzarte C(2024)Db2une: Tuning Under Pressure via Deep LearningProceedings of the VLDB Endowment10.14778/3685800.368581117:12(3855-3868)Online publication date: 8-Nov-2024
https://dl.acm.org/doi/10.14778/3685800.3685811
Siddiqui TWu W(2024)ML-Powered Index Tuning: An Overview of Recent Progress and Open ChallengesACM SIGMOD Record10.1145/3641832.364183652:4(19-30)Online publication date: 19-Jan-2024
https://dl.acm.org/doi/10.1145/3641832.3641836
Song HZhou WLi FPeng XCui H(2023)Rethink Query Optimization in HTAP DatabasesProceedings of the ACM on Management of Data10.1145/36267501:4(1-27)Online publication date: 12-Dec-2023
https://dl.acm.org/doi/10.1145/3626750
Song JDou WCui ZDai QWang WWei JZhong HHuang TGrundy JPollock LPenta M(2023)Testing Database Systems via Differential Query ExecutionProceedings of the 45th International Conference on Software Engineering10.1109/ICSE48619.2023.00175(2072-2084)Online publication date: 14-May-2023
https://dl.acm.org/doi/10.1109/ICSE48619.2023.00175
Zhang JWu SZhao JXie ZLi FGao YChen G(2022)A Sampling-based Learning Framework for Big DatabasesProceedings of the ACM Web Conference 202210.1145/3485447.3511991(1871-1881)Online publication date: 25-Apr-2022
https://dl.acm.org/doi/10.1145/3485447.3511991
Paul DCao JLi FSrikumar V(2021)Database workload characterization with query plan encodersProceedings of the VLDB Endowment10.14778/3503585.350360015:4(923-935)Online publication date: 1-Dec-2021
https://dl.acm.org/doi/10.14778/3503585.3503600
Rigger MSu ZDevanbu PCohen MZimmermann T(2020)Detecting optimization bugs in database engines via non-optimizing reference engine constructionProceedings of the 28th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3368089.3409710(1140-1152)Online publication date: 8-Nov-2020
https://dl.acm.org/doi/10.1145/3368089.3409710
Ma LDing BDas SSwaminathan AMaier DPottinger RDoan ATan WAlawini ANgo H(2020)Active Learning for ML Enhanced Database SystemsProceedings of the 2020 ACM SIGMOD International Conference on Management of Data10.1145/3318464.3389768(175-191)Online publication date: 11-Jun-2020
https://dl.acm.org/doi/10.1145/3318464.3389768
Jindal APatel HRoy AQiao SYin ZSen RKrishnan S(2019)PeregrineProceedings of the ACM Symposium on Cloud Computing10.1145/3357223.3362726(416-427)Online publication date: 20-Nov-2019
https://dl.acm.org/doi/10.1145/3357223.3362726
Ding BDas SMarcus RWu WChaudhuri SNarasayya VBoncz PManegold SAilamaki ADeshpande AKraska T(2019)AI Meets AIProceedings of the 2019 International Conference on Management of Data10.1145/3299869.3324957(1241-1258)Online publication date: 25-Jun-2019
https://dl.acm.org/doi/10.1145/3299869.3324957
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.

Media

Figures

Other

Tables

View Issue’s Table of Contents