IP Library › Granted Patent US 12,321,346
Granted Patent B2
US 12,321,346 · App. 16/452,652 · Granted Jun 3, 2025

Adaptive query optimization using machine learning

Inventors: Vincent Corvinelli (Mississauga, CA); Calisto Zuzarte (Pickering, CA); Vinith Suriyakumar (Ottawa, CA); Joel Raymond Scarfone (London, CA); Diana Koval (Toronto, CA)
Assignee: International Business Machines Corporation
G06F16/2453G06N20/00
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 12,321,346
App. No.
16/452,652
Granted
Jun 3, 2025
Kind
B2
Abstract

A computer implemented method for processing database queries includes receiving a query and a set of runtime metrics corresponding to the query, wherein the query includes a set of elements, generating a set of encoded elements corresponding to the set of elements, processing the set of encoded elements and the set of runtime metrics to identify one or more possibly query classifications, determining a query execution plan according to the identified one or more possible query classifications, and executing the query according to the determined query execution plan. The computer implemented method may additionally include providing one or more runtime metrics corresponding to the executed query. A computer program product and a computer system corresponding to the method are also disclosed.

Claims (39)

1. A computer implemented method for query optimization, the method comprising:

receiving a query and a set of runtime metrics corresponding to the query, wherein the query includes a set of elements;

processing the set of elements and the set of runtime metrics to identify one or more possible query classifications associated with the query;

determining a query execution plan for the query according to the identified one or more possible query classifications associated with the query, wherein the query execution plan is a combination of two or more existing single query execution plans for executing respective queries corresponding to each of the identified one or more possible query classifications; and

executing the query according to the determined query execution plan.

2. The computer implemented method of claim 1 , further comprising:

providing one or more runtime metrics corresponding to the executed query.

3. The computer implemented method of claim 1 , wherein each element of the set of elements corresponds to a word or term.

4. The computer implemented method of claim 1 , wherein processing the set of elements and the set of runtime metrics to identify one or more possible query classifications includes comparing the set of encoded elements and the set of runtime metrics to one or more sets of elements and one or more sets of runtime metrics corresponding to one or more additional queries, wherein the additional queries are each associated with a classification.

5. The computer implemented method of claim 1 , wherein the set of runtime metrics includes elapsed time and memory usage.

6. The computer implemented method of claim 1 , wherein each classification corresponds to a join order and an access type.

7. The computer implemented method of claim 1 , further comprising generating a set of encoded elements corresponding to the set of elements.

8. A computer program product for query optimization, the computer program product comprising:

one or more computer readable storage media and program instructions stored on the one or more computer readable storage media, the program instructions comprising instructions to:

receive a query and a set of runtime metrics corresponding to the query, wherein the query includes a set of elements;

process the set of elements and the set of runtime metrics to identify one or more possible query classifications associated with the query;

determine a query execution plan for the query according to the identified one or more possible query classifications associated with the query, wherein the query execution plan corresponds to a combination of two or more existing single query execution plans for executing respective queries corresponding to each of the identified one or more possible query classifications; and

execute the query according to the determined query execution plan.

9. The computer program product of claim 8 , further comprising instructions to:

provide one or more runtime metrics corresponding to the executed query.

10. The computer program product of claim 8 , wherein each element of the set of elements corresponds to a word or term.

11. The computer program product of claim 8 , wherein instructions to process the set of elements and the set of runtime metrics to identify one or more possible query classifications include instructions to compare the set of encoded elements and the set of runtime metrics to one or more sets of elements and one or more sets of runtime metrics corresponding to one or more additional queries, wherein the additional queries are each associated with a classification.

12. The computer program product of claim 8 , wherein the set of runtime metrics includes elapsed time and memory usage.

13. The computer program product of claim 8 , wherein each classification corresponds to a join order and an access type.

14. The computer program product of claim 8 , the program instructions further comprising instructions to generate a set of encoded elements corresponding to the set of elements.

15. A computer system for query optimization, the computer system comprising:

one or more computer processors;

one or more computer-readable storage media;

program instructions stored on the computer-readable storage media for execution by at least one of the one or more processors, the program instructions comprising instructions to:

receive a query and a set of runtime metrics corresponding to the query, wherein the query includes a set of elements;

process the set of elements and the set of runtime metrics to identify one or more possible query classifications associated with the query;

determine a query execution plan for the query according to the identified one or more possible query classifications associated with the query, wherein the query execution plan corresponds to a combination of two or more existing single query execution plans for executing respective queries corresponding to each of the identified one or more possible query classifications; and

execute the query according to the determined query execution plan.

16. The computer system of claim 15 , further comprising instructions to:

provide one or more runtime metrics corresponding to the executed query.

17. The computer system of claim 15 , wherein each element of the set of elements corresponds to a word or term.

18. The computer system of claim 15 , wherein instructions to process the set of elements and the set of runtime metrics to identify one or more possible query classifications include instructions to compare the set of encoded elements and the set of runtime metrics to one or more sets of elements and one or more sets of runtime metrics corresponding to one or more additional queries, wherein the additional queries are each associated with a classification.

19. The computer system of claim 15 , wherein the set of runtime metrics includes elapsed time and memory usage.

20. The computer system of claim 15 , the program instructions further comprising instructions to generate a set of encoded elements corresponding to the set of elements.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Jun 26, 2019
From: CORVINELLI, VINCENT; ZUZARTE, CALISTO; SURIYAKUMAR, VINITH; SCARFONE, JOEL RAYMOND; KOVAL, DIANA
To: INTERNATIONAL BUSINESS MACHINES CORPORATION
Reel/Frame 049589/0834 →
Continuity (1)
Related Publication 20200409948A1 · Dec 31, 2020
References Cited (36)
US 6108648A · Lakshmi · 2000 [cited by applicant]
US 6353818B1 · Carino, Jr. · 2002 [cited by applicant]
US 6763359B2 · Lohman · 2004 [cited by applicant]
US 7636735B2 · Haas · 2009 [cited by applicant]
US 8099410B2 · Day · 2012 [cited by applicant]
US 9189523B2 · Ganapathi · 2015 [cited by applicant]
US 10740333B1 · Betawadkar-Norwood · 2020 [cited by examiner]
US 20020103793A1 · Koller · 2002 [cited by applicant]
US 20080133454A1 · Markl · 2008 [cited by applicant]
US 20090144229A1 · Meijer · 2009 [cited by applicant]
US 20160034530A1 · Nguyen · 2016 [cited by applicant]
US 20160260011A1 · Corvinelli · 2016 [cited by applicant]
US 20160275398A1 · Corvinelli · 2016 [cited by applicant]
US 20170193398A1 · Schmidt · 2017 [cited by applicant]
US 20170323200A1 · Corvinelli · 2017 [cited by applicant]
US 20180089271A1 · Kosuru · 2018 [cited by examiner]
US 20180131645A1 · Magliozzi · 2018 [cited by examiner]
US 20180276277A1 · Wang · 2018 [cited by examiner]
US 20190384845A1 · Saxena · 2019 [cited by examiner]
US 20200034357A1 · Panuganty · 2020 [cited by examiner]
US 20200272667A1 · Ding · 2020 [cited by examiner]
US 20200409949A1 · Saxena · 2020 [cited by examiner]
“Adaptive Query Optimization in Postgresql”, PGCon 2017 The PostgreSQL Conference, 1 page. [cited by applicant]
Boulos et al., “A Neural Networks Approach for Query Cost Evaluation”, (2001), printed Jan. 29, 2019, 16 pages. [cited by applicant]
Boulos et al., “Cost Estimation of User-Defined Methods in Object-Relational Database Systems”, SIGMOD Record, vol. 28, No. 3, Sep. 1999, 7 pages. [cited by applicant]
Chaudhuri et al., “Optimization of Queries with User-defined Predicates”, Proceedings of the 22nd VLDB Conference, Mumbai(Bombay), India, 1996, pp. 87-98. [cited by applicant]
Farias et al., A Machine Learning Approach for SQL Queries Response Time Estimation in the Cloud, Simposio Brasileiro de Banco de Dados—SBBD 2013 Short Papers, printed Jan. 29, 2019, 6 pages. [cited by applicant]
He et al., “Self-Tuning Cost Modeling of User-Defined Functions in an Object-Relational DBMS”, ACM Transactions on Database Systems, vol. 30, No. 3, Sep. 2005, pp. 812-853. [cited by applicant]
He et al., “Self-tuning UDF Cost Modeling Using the Memory-Limited Quadtree”, E. Bertino et al. (Eds.): EDBT 2004, LNCS 2992, pp. 513-531, 2004. Springer-Verlag Berlin Heidelberg 2004. [cited by applicant]
Kraska et al., The Case for Learned Index Structures, arXiv:1712.01208v3 [cs.DB] Apr. 30, 2018, 30 pages. [cited by applicant]
Liu et al., “Cardinality Estimation Using Neural Networks”, CASCON '15 Proceedings of the 25th Annual International Conference on Computer Science and Software Engineering, Nov. 2-4, 2015, pp. 53-59. [cited by applicant]
Wu et al., “Predicting Query Execution Time: Are Optimizer Cost Models Really Unusable?”, Computer Sciences Department, University of Wisconsin, Madison, WI, USA, printed Jan. 29, 2019, 18 pages. [cited by applicant]
Zhang et al., “Statistical Learning Techniques for Costing XML Queries”, Proceedings of the 31st VLDB Conference, Trondheim, Norway, 2005, 12 pages. [cited by applicant]
Ganapathi et al., “Predicting Multiple Metrics for Queries: Better Decisions Enabled by Machine Learning”, IEEE International Conference on Data Engineering, 12 pages, © 2009 IEEE, DOI 10.1109/ICDE.2009.130. [cited by applicant]
Marcus et al., “Deep Reinforcement Learning for Join Order Enumeration”, arXiv:1803.00055v2 [cs.DB] Mar. 12, 2018, 7 pages. [cited by applicant]
Ortiz et al., “Learning State Representations for Query Optimization with Deep Reinforcement Learning”, arXiv:1803.08604v1 [cs.DB] Mar. 22, 2018, 5 pages. [cited by applicant]