Article

Plan selection based on query clustering

Authors:

Jignashu Parikh,

Vibhuti S. Sengar,

Jayant R. HaritsaAuthors Info & Claims

VLDB '02: Proceedings of the 28th international conference on Very Large Data Bases

Pages 179 - 190

Published: 20 August 2002 Publication History

Abstract

Query optimization is a computationally intensive process, especially for complex queries. We present here a tool, called PLASTIC, that can be used by query optimizers to amortize the optimization cost. Our scheme groups similar queries into clusters and uses the optimizer-generated plan for the cluster representative to execute all future queries assigned to the cluster. Query similarity is evaluated based on a comparison of query structures and the associated table schemas and statistics, and a classifier is employed for efficient cluster assignments. Experiments with a variety of queries on a commercial optimizer show that PLASTIC predicts the correct plan choice in most cases, thereby providing significantly improved query optimization times. Further, when errors are made, the additional execution cost incurred due to the sub-optimal plan choices is marginal.

References

[1]

{1} http://www.tpc.org

[2]

{2} http://download-east.oracle.com/otndoc/oracle9i/ 901 doc/server.901/a87503/toc.htm

[3]

{3} R. Cole and G. Graefe, "Optimization of Dynamic Query Evaluation Plans", Proc. of ACM SIGMOD Intl. Conf. on Management of Data, 1994.

Digital Library

[4]

{4} R. Duda and P. Hart, Pattern Recognition and Scene Analysis , John Wiley, New York, 1973.

[5]

{5} S. Ganguly, "Design and Analysis of Parametric Query Optimization Algorithms", Proc. of 24th Intl. Conf. on Very Large Data Bases (VLDB), August 1998.

Digital Library

[6]

{6} P. Gassner, G. Lohman, K. Schiefer and Y. Wang, "Query Optimization in the IBM DB2 Family", Data Engineering Bulletin, 16 (4), (1993).

[7]

{7} A. Ghosh, J. Parikh, V. Sengar and J. Haritsa, "Query Clustering for Plan Selection", Tech Report, DSL/SERC, Indian Institute of Science, July 2002.

[8]

{8} R. Gopal and R. Ramesh, "The Query Clustering Problem: A Set Partitioning Approach", IEEE Trans. on Knowledge and Data Engineering, 7(6), December 1995.

Digital Library

[9]

{9} J. Hartigan, Clustering Algorithms, John Wiley & Sons, Inc., 1975.

Digital Library

[10]

{10} Y. Ioannidis, R. Ng, K. Shim and T. Sellis, "Parametric Query Processing", Proc. of Intl. Conf. on Very Large Data Bases (VLDB), 1992.

[11]

{11} J. Park and A. Segev, "Using common sub-expressions to optimize multiple queries", Proc. of IEEE Intl. Conf. on Data Engineering (ICDE), 1993.

Digital Library

[12]

{12} R. Quinlan, http://www.rulequest.com/see5-info.html

[13]

{13} P. Roy, S. Seshadri, S. Sudarshan and S. Bhobe, "Efficient and Extensible Algorithms for Multi Query Optimization", Proc. of ACM SIGMOD Intl. Conf. on Management of Data, May 2000.

Digital Library

[14]

{14} T. Sellis, "Multiple Query Optimization", ACM Trans. on Database Systems, 13(1), March 1988.

Digital Library

[15]

{15} P. Selinger, M. Astrahan, D. Chamberlin, R. Lorie and T. Price, "Access Path Selection in a Relational Database Management System", Proc. of ACM SIGMOD Intl. Conf. on Management of Data, 1979.

Digital Library

[16]

{16} K. Shim, T. Sellis and D. Nau, "Improvements on a heuristic algorithm for multiple-query optimization", Data and Knowledge Engineering, 12, 1994.

Digital Library

[17]

{17} M. Stonebraker, J. Frew, K. Gardels and J. Meredith, "The SEQUOIA 2000 Storage Benchmark", Proc. of ACM SIGMOD Intl. Conf. on Management of Data, 1993.

Digital Library

[18]

{18} T. Zhang, R. Ramakrishnan and M. Livny, "BIRCH: An Efficient Data Clustering Method for Very Large Databases", Proc. of ACM SIGMOD Intl. Conf. on Management of Data, 1996.

Digital Library

Cited By

Guo BYu JYang DLeng HLiao B(2022)Energy-Efficient Database Systems: A Systematic SurveyACM Computing Surveys10.1145/353822555:6(1-53)Online publication date: 7-Dec-2022
https://dl.acm.org/doi/10.1145/3538225
Ding BDas SWu WChaudhuri SNarasayya V(2018)Plan stitchProceedings of the VLDB Endowment10.14778/3231751.323176111:10(1123-1136)Online publication date: 1-Jun-2018
https://dl.acm.org/doi/10.14778/3231751.3231761
Ma LVan Aken DHefny AMezerhane GPavlo AGordon GDas GJermaine CBernstein P(2018)Query-based Workload Forecasting for Self-Driving Database Management SystemsProceedings of the 2018 International Conference on Management of Data10.1145/3183713.3196908(631-645)Online publication date: 27-May-2018
https://dl.acm.org/doi/10.1145/3183713.3196908
Show More Cited By

Index Terms

Plan selection based on query clustering

Recommendations

Distributed Query Plan Generation using Ant Colony Optimization

Query processing is a critical performance evaluation parameter and has received a considerable amount of attention especially in the context of distributed database systems. The aim of distributed query processing is to effectively and efficiently ...
Distributed Query Plan Generation using Particle Swarm Optimization

A large number of queries are posed on databases spread across the globe. In order to process these queries efficiently, optimal query processing strategies that generate efficient query processing plans are being devised. In distributed relational ...
Distributed Query Plan Generation Using HBMO
MIWAI 2013: Proceedings of the 7th International Workshop on Multi-disciplinary Trends in Artificial Intelligence - Volume 8271

Processing a distributed query entails accessing data from multiple sites. The inter site communication cost, being the dominant cost, needs to be reduced in order to improve the query response time. This would require the query optimizer to devise a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image DL Hosted proceedings

VLDB '02: Proceedings of the 28th international conference on Very Large Data Bases

August 2002

1110 pages

Publisher

VLDB Endowment

Publication History

Published: 20 August 2002

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
211
Total Downloads

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

Reflects downloads up to 14 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Guo BYu JYang DLeng HLiao B(2022)Energy-Efficient Database Systems: A Systematic SurveyACM Computing Surveys10.1145/353822555:6(1-53)Online publication date: 7-Dec-2022
https://dl.acm.org/doi/10.1145/3538225
Ding BDas SWu WChaudhuri SNarasayya V(2018)Plan stitchProceedings of the VLDB Endowment10.14778/3231751.323176111:10(1123-1136)Online publication date: 1-Jun-2018
https://dl.acm.org/doi/10.14778/3231751.3231761
Ma LVan Aken DHefny AMezerhane GPavlo AGordon GDas GJermaine CBernstein P(2018)Query-based Workload Forecasting for Self-Driving Database Management SystemsProceedings of the 2018 International Conference on Management of Data10.1145/3183713.3196908(631-645)Online publication date: 27-May-2018
https://dl.acm.org/doi/10.1145/3183713.3196908
Dutt ANarasayya VChaudhuri SChirkova RYang JSuciu D(2017)Leveraging Re-costing for Online Optimization of Parameterized Queries with GuaranteesProceedings of the 2017 ACM International Conference on Management of Data10.1145/3035918.3064040(1539-1554)Online publication date: 9-May-2017
https://dl.acm.org/doi/10.1145/3035918.3064040
Aligon JGolfarelli MMarcel PRizzi STurricchia E(2014)Similarity measures for OLAP sessionsKnowledge and Information Systems10.1007/s10115-013-0614-139:2(463-489)Online publication date: 1-May-2014
https://dl.acm.org/doi/10.1007/s10115-013-0614-1
Martinez LCollet CBobineau CDublé EDesai BPokorny JBernardino J(2012)The QOL approach for optimizing distributed queries without complete knowledgeProceedings of the 16th International Database Engineering & Applications Sysmposium10.1145/2351476.2351487(91-99)Online publication date: 8-Aug-2012
https://dl.acm.org/doi/10.1145/2351476.2351487
Kantere (Dash DGratsias GAilamaki ASellis TMiller RKementsietsidis AVelegrakis Y(2011)Predicting cost amortization for query servicesProceedings of the 2011 ACM SIGMOD International Conference on Management of data10.1145/1989323.1989358(325-336)Online publication date: 12-Jun-2011
https://dl.acm.org/doi/10.1145/1989323.1989358
Chaudhuri SLee HNarasayya VElmagarmid AAgrawal D(2010)Variance aware optimization of parameterized queriesProceedings of the 2010 ACM SIGMOD International Conference on Management of data10.1145/1807167.1807226(531-542)Online publication date: 6-Jun-2010
https://dl.acm.org/doi/10.1145/1807167.1807226
Dey ABhaumik SD HHaritsa J(2008)Efficiently approximating query optimizer plan diagramsProceedings of the VLDB Endowment10.14778/1454159.14541731:2(1325-1336)Online publication date: 1-Aug-2008
https://dl.acm.org/doi/10.14778/1454159.1454173
Papadomanolakis SDash DAilamaki AKlas WNeuhold E(2007)Efficient use of the query optimizer for automated physical designProceedings of the 33rd international conference on Very large data bases10.5555/1325851.1325974(1093-1104)Online publication date: 23-Sep-2007
https://dl.acm.org/doi/10.5555/1325851.1325974
Show More Cited By

View Options

Get Access

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 Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents