Techniques for estimating progress of database queries

• US 7,454,407 B2
• Filed: 06/10/2005
• Issued: 11/18/2008
• Est. Priority Date: 06/10/2005
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chaudhuri, Surajit, Shriraghav, Kaushik, Ramamurthy, Ravishankar
• Primary Examiner(s): Rones; Charles
• Assistant Examiner(s): CAO, PHUONG THAO
• Application Number:
  US11/149,968
• Publication Number:
  US 20060282404A1
• Time in Patent Office: 1,257 Days
• Field of Search: 707/2, 707/3, 707/4, 707/5
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24549 Run-time optimisation
• CPC Class Codes: G06F 16/2457 with adaptation to user needs
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

Techniques for estimating the progress of database queries are described herein. In a first implementation, a respective lower-bound parameter is associated with each node in an operator tree that representing a given database query, and the progress of the database query at a given point is estimated based upon the lower-bound parameters. In a second implementation, the progress of the query is estimated by associating respective lower-bound and upper-bound parameters with each node in the operator tree. The progress of the query at the given point is then estimated based on the lower-bound and upper-bound parameters.

Claims

1. One or more computer readable storage media comprising computer executable instructions that, when executed, direct a computing device to:

associate at least a respective lower-bound parameter with each node in an operator tree representing a database query, wherein each lower-bound parameter represents a lower bound on a number of operations expected to be performed when processing the node during the database query;

execute the database query;

estimate progress of the database query at a given point in the database query based at least in part upon the lower-bound parameters by dividing a number of operations performed during the database query up to the given point by a sum of the respective lower-bound parameters associated with each of the nodes of the operator tree; and

refine the estimate of the progress of the database query based on characteristics observed during the query.

2. The computer readable storage media of claim 1, wherein the computer executable instructions direct the computing device to associate the respective lower-bound parameter by defining the lower-bound parameter based on a cardinality of at least one base relation associated with the database query.

3. The computer readable storage media of claim 1, wherein the computer executable instructions direct the computing device to associate the respective lower-bound parameter by defining the lower-bound parameter based on a number of tuples returned up to the given point in the database query.

4. The computer readable storage media of claim 1, further comprising computer executable instructions that direct the computing device to refine at least one lower-bound parameter associated with at least one of the nodes as the database query progresses.

5. The computer readable storage media of claim 1, further comprising computer executable instructions that direct the computing device to associate at least a respective upper-bound parameter with at least one node in the operator tree.

6. The computer readable storage media of claim 5, further comprising computer executable instructions that direct the computing device to estimate progress of the database query based at least in part on the upper-bound parameter and the lower-bound parameter.

7. One or more computer readable storage media comprising computer executable instructions that, when executed, direct a computing device to:

associate a respective lower-bound parameter and a respective upper-bound parameter with each node in an operator tree representing a database query, wherein each lower-bound parameter represents a lower bound on a number of operations expected to be performed when processing the node during the database query and each upper-bound parameter represents an upper bound on a number of operations expected to be performed when processing the node during the database query;

execute the database query;

estimate progress of the database query at a given point in the database query based on the lower-bound parameter and the upper-bound parameter by dividing a number of operations performed during the database query up to the given point by a parameter determined by summing the average of the lower-bound parameter and the upper-bound parameter of each node in the operator tree; and

refine the estimate of the progress of the database query based on characteristics observed during the query.

8. The computer readable storage media of claim 7, wherein the computer executable instructions direct the computing device to associate the respective lower-bound parameter by defining the lower-bound parameter based on a cardinality of at least one base relation associated with the database query.

9. The computer readable storage media of claim 7, wherein the computer executable instructions direct the computing device to associate the respective lower-bound parameter by defining the lower-bound parameter based on a number of tuples returned up to the given point in the database query.

10. The computer readable storage media of claim 7, wherein the computer executable instructions direct the computing device to associate a respective upper-bound parameter with each node by defining the upper-bound parameter based on a cardinality of at least one base relation associated with the database query.

11. The computer readable storage media of claim 7, wherein the computer executable instructions direct the computing device to associate a respective upper-bound parameter with each node by assigning to a given operator node an upper-bound parameter of a child node of the given operator node.

12. The computer readable storage media of claim 7, wherein the computer executable instructions direct the computing device to associate a respective upper-bound parameter with each node by assigning to a given node a largest upper-bound parameter associated with one of a plurality of child nodes of the given node.

13. The computer readable storage media of claim 7, wherein the computer executable instructions direct the computing device to estimate progress of the database query by dividing a number of operations performed during the database query up to the given point by the square root of the sum of the respective lower-bound parameters multiplied by the sum of the respective upper-bound parameters.

14. A computer implemented method comprising:

associating at least a respective lower-bound parameter with each node in an operator tree representing a database query, wherein each lower-bound parameter represents a lower bound on a number of operations expected to be performed when processing the node during the database query;

executing the database query;

estimating progress of the database query at a given point in the database query based exclusively on the lower-bound parameters by dividing a number of operations performed during the database query up to the given point by a sum of the respective lower-bound parameters associated with the nodes of the operator tree and

refining the estimate of the progress of the database query based on characteristics observed during the query.