Learning from empirical results in query optimization

• US 6,763,359 B2
• Filed: 06/06/2001
• Issued: 07/13/2004
• Est. Priority Date: 06/06/2001
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Lohman, Guy Maring, Markl, Volker, Stillger, Michael
• Primary Examiner(s): AMSBURY, WAYNE P
• Application Number:
  US09/876,642
• Publication Number:
  US 20020198867A1
• Time in Patent Office: 1,133 Days
• Field of Search: 707/102, 707/2
• US Class Current: 707/718
• CPC Class Codes: G06F 16/24545 Selectivity estimation or determination
• CPC Class Codes: G06F 16/24547 Optimisations to support specific applications; Extensibility of optimisers
• CPC Class Codes: G06F 16/24549 Run-time optimisation
• CPC Class Codes: Y10S 707/954 Relational
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

An optimizer function of a Relational Database Management System (RDBMS) generates alternative query execution plans (QEPs) for executing a query, provides an execution model of each of the QEPs, chooses one of the QEPs for execution based on the model associated therewith, and exploits an empirical measurement from the execution of the chosen QEP to validate the model associated therewith, by determining whether the model is in error, and by computing one or more adjustments to the model to correct the determined error.

Claims

1. A method of performing a query in a computer system to retrieve data from a database stored on the computer system, the method comprising:

(a) generating a plurality of query execution plans (QEPs) for the query;

(b) providing an execution model of each of the QEPs;

(c) choosing one of the QEPs for execution based on the model associated therewith; and

(d) using a feedback loop to monitor the execution of the chosen QEP, to analyze information from the monitored execution, to compute adjustments to the model using the analyzed information, and in exploit the computed adjustments to refine the model, wherein the model is used to estimate intermediate results at each step of the QEP.

2. The method of claim 1, wherein the model comprises a cost estimate based on statistics for distinct values.

4. The method of claim 1, wherein the statistics comprise statistics for single columns on base tables.

3. A method of performing a query in a computer system to retrieve data from a database stored on the computer system, the method comprising:

(a) generating a plurality of query execution plans (QEPs) for the query;

(b) providing an execution model of each of the QEPs;

(c) choosing one of the QEPs for execution based on the model associated therewith; and

(d) using a feedback loop to monitor the execution of the chosen QEP, to analyze information from the monitored execution, and to determine from the analyzed information which statistics should be created.

5. The method of claim 3, wherein the statistics comprise statistics for multiple columns on a single base table.

6. The method of claim 3, wherein the statistics comprise statistics for an intermediate result defined by a view.

7. A method of performing a query in a computer system to retrieve data from a database stored on the computer system, the method comprising:

(a) generating a plurality of query execution plans (QEPs) for the query;

(b) providing an execution model of each of the QEPs;

(c) choosing one of the QEPs for execution based on the model associated therewith; and

(d) using a feedback loop to monitor the execution of the chosen QEP, to analyze information from the monitored execution, to compute adjustments to the model using the analyzed information, and to exploit the computed adjustments to refine the model, wherein the model is used to determine a cost of the QEP at each step of the QEP.

8. The method of claim 7, wherein the cost comprises characteristics of the data being retrieved by the QEP, machine resources used to execute the QEP, or time required to process one or more steps of the QEP.

9. The method of claim 7, further comprising using the computed adjustments to the model to optimize the QEPs.

10. A computer-implemented apparatus fox performing a query, comprising:

a computer system, wherein the query is performed by the computer system to retrieve data from a database stored on rite computer system;

logic, performed by the computer system, for;

(a) generating a plurality of query execution plans (QEPs) for the query;

(b) providing an execution model of each of the QEPs;

(c) choosing one of the QEPs for execution based on the model associated therewith; and

(d) using a feedback loop to monitor the execution of the chosen QEP, to analyze information from the monitored execution, to compute adjustments to the model using the analyzed information, and to exploit the computed adjustments to refine the model, wherein the model is used to estimate intermediate results at each step of the QEP.

11. The apparatus of claim 10, wherein the model comprises a cost estimate based on statistics for distinct values.

12. A computer-implemented apparatus for performing a query, comprising:

a computer system, wherein the query is performed by the computer system to retrieve data from a database stored on the computer system;

logic, performed by the computer system, for;

(a) generating a plurality of query execution plans (QEPs) for the query;

(b) providing an execution model of each of the QEPs;

(c) choosing one of the QEPs for execution based on the model associated therewith; and

(d) using a feedback loop to monitor the execution of the chosen QEP, to analyze information from the monitored execution, and to determine from the analyzed information which statistics should be created.

13. The apparatus of claim 12, wherein the statistics comprise statistics for single columns on base tables.

14. The apparatus of claim 12, wherein the statistics comprise statistics for multiple columns on a single base table.

15. The apparatus of claim 12, wherein the statistics comprise statistics for an intermediate result defined by a view.

16. A computer-implemented apparatus for performing a query, comprising:

a computer system, wherein the query is performed by the computer system to retrieve data from a database stored on the computer system;

logic, performed by the computer system, for;

(a) generating a plurality of query execution plans (QEPs) for the query;

(b) providing an execution model of each of the QEPs;

(c) choosing one of the QEPs for execution based on the model associated therewith; and

(d) using a feedback loop to monitor the execution of the chosen QEP, to analyze information from the monitored execution, to compute adjustments to the model using the analyzed information, and to exploit the computed adjustments to refine the model, wherein the model is used to determine a cost of the QEP at each step of the QEP.

17. The apparatus of claim 16, wherein the cost comprises characteristics of the data being retrieved by the QEP, machine resources used to execute the QEP, or time required to process one or more steps of the QEP.

18. The apparatus of claim 16, further comprising logic for using the computed adjustments to the model to optimize the QEPs.

19. An article of manufacture embodying logic for performing a query in a computer system to retrieve data from a database stored in a data storage device coupled to the computer system, the logic comprising:

(a) generating a plurality of query execution plans (QEPs) for the query;

(b) providing an execution model of each of the QEPs;

(c) choosing one of the QEPs for execution based on the model associated therewith; and

(d) using a feedback loop to monitor the execution of the chosen QEP, to analyze information from the monitored execution, to compute adjustments to the model using the analyzed information, and to exploit the computed adjustments to refine the model, wherein the model is used to estimate intermediate results at each step of the QEP.

20. The article of claim 19, wherein the model comprises a cost estimate based on statistics for distinct values.

21. An article of manufacture embodying logic for performing a query in a computer system to retrieve data front a database stored in a data storage device coupled to the computer system, the logic comprising:

(a) generating a plurality of query execution plans (QEPs) for the query;

(b) providing an execution model of each of the QEPs;

(c) choosing one of the QEPs for execution based on the model associated therewith;

said

(d) using a feedback loop to monitor the execution of the chosen QEP, to analyze information from the monitored execution, and to determine from the analyzed information which statistics should be created.

22. The article of claim 21, wherein the statistics comprise statistics for single columns on base tables.

23. The article of claim 21, wherein the statistics comprise statistics for multiple columns on a single base table.

24. The article of claim 21, wherein the statistics comprise statistics for an intermediate result defined by a view.

25. An article of manufacture embodying logic for performing a query in a computer system to retrieve data from a database stored in a data storage device coupled to the computer system, the logic comprising:

(a) generating a plurality of quay execution plans (QEPs) for the query;

(b) providing an execution model of each of the QEPs;

(c) choosing one of the QEPs for execution based on the model associated therewith; and

(d) using a feedback loop to monitor the execution of the chosen QEP, to analyze information from the monitored execution, to compute adjustments to the model using the analyzed information, and to exploit the computed adjustments to refine the model, wherein the model is used to determine a cost of the QEP at each step of the QEP.

26. The article of claim 25, wherein the cost comprises characteristics of the data being retrieved by the QEP, machine resources used to execute the QEP, or time required to process one or more steps of the QEP.

27. The article of claim 25, further comprising using the computed adjustments to the model to optimize the QEPs.

28. A method of performing a query in a computer system to retrieve data from a database stored on the computer system, the method comprising:

(a) generating a plurality of query execution plans (QEPs) for the query;

(b) providing an execution model of each of the QEPs;

(c) choosing one of the QEPs fox execution based on the model associated therewith; and

(d) using a feedback loop to monitor the execution of the chosen QEP and to analyze information from the monitored execution;

(e) wherein the feedback loop is used to compute adjustments to the model using the analyzed information, and to exploit the computed adjustments to refine the model, wherein the model is used to estimate intermediate results at each step of the QEP;

(f) wherein the feedback loop is used to determine from the analyzed information which statistics should be created; and

(g) wherein the feedback loop is used to compute adjustments to the model using the analyzed information, and to exploit the computed adjustments to refine the model, wherein the model is used to determine a cost of the QEP at each step of the QEP.