System and method for cardinality estimation based on query execution feedback

• US 7,146,363 B2
• Filed: 05/20/2003
• Issued: 12/05/2006
• Est. Priority Date: 05/20/2003
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Galindo-Legaria, Cesar A., Waas, Florian M., Joshi, Milind M.
• Primary Examiner(s): Robinson, Greta
• Assistant Examiner(s): LEWIS, CHERYL RENEA
• Application Number:
  US10/441,812
• Publication Number:
  US 20040236722A1
• Time in Patent Office: 1,295 Days
• Field of Search: 707 1- 6
• US Class Current: 707/718
• CPC Class Codes: G06F 16/2454 Optimisation of common expressions
• CPC Class Codes: G06F 16/24545 Selectivity estimation or determination
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

During query execution, statistics associated with expressions are observed. Such observed statistics preferably include the cardinality of each expression. The observed statistics are submitted to an expression manager as feedback from the executed query. The statistics are preferably stored for use in estimating the cardinality of execution plans for future queries.

Claims

1. A computer implemented method for estimating a cardinality of an expression, the method comprising:

matching the expression with a stored expression;

retrieving previously gathered statistics associated with the stored expression, the previously gathered statistics comprising statistics based, at least in part, on a previous execution of a previous query; and

estimating the cardinality of the expression based on the previously gathered statistics.

2. The method of claim 1, wherein retrieving the previously gathered statistics associated with the stored expression comprises:

determining an identifier of the stored expression;

retrieving the previously gathered statistics associated with the stored expression, the previously gathered statistics indexed according to the identifier.

3. The method of claim 1, wherein estimating the cardinality of the expression based on the previously gathered statistics comprises estimating the cardinality of the expression based on the observed cardinality of the stored expression.

4. The method of claim 1, further comprising developing an execution plan for a query, the execution plan including the expression.

5. The method of claim 4, further comprising:

selecting the execution plan based on the estimated cardinality of the expression;

assigning an identifier to the expression;

executing the query according to the execution plan;

observing a cardinality of the expression; and

storing the observed cardinality wherein the stored cardinality is indexed according to the identifier of the expression.

6. The method of claim 5, wherein assigning an identifier to the expression comprises:

if the expression matches a stored expression, then assigning the expression the identifier of the stored expression,

if the expression does not match the stored expression, then assigning the expression a new identifier.

7. The method of claim 5, further comprising trimming the stored cardinality.

8. A computer readable medium having stored thereon computer readable instructions executed in a computer for performing the following steps:

matching an expression with a stored expression;

retrieving previously gathered statistics associated with the stored expression, the previously gathered statistics comprising statistics based,-at least in part, on a previous execution of a previous query; and

estimating a cardinality of the expression based on the previously gathered statistics.

9. The computer readable medium of claim 8, wherein retrieving statistics associated with the stored expression comprises:

determining an identifier of the stored expression;

retrieving the previously gathered statistics associated with the stored expression, the previously gathered statistics indexed according to the identifier.

10. The computer readable medium of claim 8, wherein estimating the cardinality of the expression based on the previously gathered statistics comprises estimating the cardinality of the expression based on the observed cardinality of the stored expression.

11. The computer readable medium of claim 8, further comprising computer readable instructions for performing the step of developing an execution plan for a query, the execution plan including the expression.

12. The computer readable medium of claim 11, further comprising computer readable instructions for performing the steps of:

selecting the execution plan based on the estimated cardinality of the expression;

assigning an identifier to the expression;

executing the query according to the execution plan;

observing a cardinality of the expression; and

storing the observed cardinality wherein the stored cardinality is indexed according to the identifier of the expression.

13. The computer readable medium of claim 12, wherein assigning an identifier to the expression comprises:

if the expression matches a stored expression, then assigning the expression the identifier of the stored expression,

if the expression does not match a stored expression, then assigning the expression a new identifier.

14. The computer readable medium of claim 12, further comprising computer readable instructions for performing the step of trimming the stored cardinality.

15. A computer implemented system for estimating a cardinality of an expression, the system comprising:

an expression manager for performing the steps of;

matching the expression with a stored expression; and

retrieving previously gathered statistics associated with the stored expression, the previously gathered statistics comprising statistics based, at least in part, on a previous execution of a previous query; and

an optimizer for performing the step of estimating the cardinality of the expression based on the previously gather statistics.

16. The system of claim 15, further comprising a metadata catalog for storing the previously gathered statistics.

17. The system of claim 16, wherein the previously gathered statistics are indexed in the metadata catalog according to an identifier of the stored expression.

18. The system of claim 17, further comprising an execution engine for executing the query according to the execution plan.

19. The system of claim 15, wherein the previously gathered statistics comprise an observed cardinality of the stored expression.

20. The system of claim 15, wherein the expression is an execution plan for a query, the execution plan developed by the optimizer.