System and method for cardinality estimation based on query execution feedback

• US 20040236722A1
• Filed: 05/20/2003
• Published: 11/25/2004
• Est. Priority Date: 05/20/2003
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Galindo-Legaria, Cesar A., Waas, Florian M., Joshi, Milind M.
• Granted Patent: US 7,146,363 B2
• Time in Patent Office: Days
• US Class Current: 707/2
• 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 method for estimating a cardinality of an expression, the method comprising:

matching the expression with a stored expression;

retrieving statistics associated with the stored expression; and

estimating the cardinality of the expression based on the statistics.

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

determining an identifier of the stored expression;

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

3. The method of claim 1, wherein estimating the cardinality of the expression based on the 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 for performing the following steps:

matching an expression with a stored expression;

retrieving statistics associated with the stored expression; and

estimating the cardinality of the expression based on the 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 statistics associated with the stored expression, the statistics indexed according to the identifier.

10. The computer readable medium of claim 8, wherein estimating the cardinality of the expression based on the 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 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 statistics associated with the stored expression; and

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

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

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

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

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

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