Techniques for estimating progress of database queries
AssigneeMicrosoft Corporation
InventorsSurajit Chaudhuri, Ravishankar Ramamurthy, Kaushik Shriraghav
Life of this patent
Estimating the term…
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.
Claims14
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.
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.
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.
Dependencies are inferred from the claim text.