Techniques for estimating progress of database queries

• US 20060282404A1
• Filed: 06/10/2005
• Published: 12/14/2006
• Est. Priority Date: 06/10/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chaudhuri, Surajit, Shriraghav, Kaushik, Ramamurthy, Ravishankar
• Granted Patent: US 7,454,407 B2
• Time in Patent Office: Days
• 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. The progress estimate is computed by dividing the work done so far by the sums of the above averages for each node in the tree.

Claims

1. One or more computer readable 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; and

estimate progress of the database query at a given point in the database query based at least in part upon the lower-bound parameters.

2. The computer readable media of claim 1, wherein the computer executable instructions direct the computing device to associate the respective lower-bound parameter by associating with each node a respective lower-bound parameter that represents a lower bound on an expected number of operations expected to be performed when processing the node during the database query.

3. The computer readable 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.

4. The computer readable 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.

5. The computer readable media of claim 1, 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 a sum of the respective lower-bound parameters associated with the nodes of the operator tree.

6. The computer readable 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.

7. The computer readable 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.

8. The computer readable media of claim 7, 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.

9. One or more computer readable 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; and

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.

10. The computer readable media of claim 9, wherein the computer executable instructions direct the computing device to associate a respective lower-bound parameter by associating with each node a respective lower-bound parameter that represents a lower bound on an expected number of operations expected to be performed when processing the node during the database query.

11. The computer readable media of claim 9, 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.

12. The computer readable media of claim 9, 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.

13. The computer readable media of claim 9, wherein the computer executable instructions direct the computing device to associate a respective upper-bound parameter with each node by associating with each node a respective upper-bound parameter that represents an upper bound on an expected number of operations expected to be performed when processing the node during the database query.

14. The computer readable media of claim 9, 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.

15. The computer readable media of claim 9, 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.

16. The computer readable media of claim 9, 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.

17. The computer readable media of claim 9, 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 a parameter determined by summing the lower-bound parameter and the upper-bound parameter of each node in the operator tree and computing an average thereof.

18. The computer readable media of claim 9, 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.

19. A method comprising:

associating at least a respective lower-bound parameter with each node in an operator tree representing a database query; and

estimating progress of the database query at a given point in the database query based at least in part upon the lower-bound parameters.

20. The method of claim 19, further comprising associating at least a respective upper-bound parameter with each node in the operator tree, and further comprising estimating progress of the database query based at least in part on the lower-bound parameters and the upper-bound parameters.