Learning from empirical results in query optimization
First Claim
Patent Images
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.
1 Assignment
0 Petitions
Accused Products
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.
114 Citations
28 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. - View Dependent Claims (2, 4)
-
-
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. - View Dependent Claims (5, 6)
-
-
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. - View Dependent Claims (8, 9)
-
-
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. - View Dependent Claims (11)
-
-
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. - View Dependent Claims (13, 14, 15)
-
-
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. - View Dependent Claims (17, 18)
-
-
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. - View Dependent Claims (20)
-
-
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. - View Dependent Claims (22, 23, 24)
-
-
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. - View Dependent Claims (26, 27)
-
-
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.
-
Specification