Use of statistics on views in query optimization

• US 7,509,311 B2
• Filed: 08/29/2003
• Issued: 03/24/2009
• Est. Priority Date: 08/29/2003
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Galindo-Legaria, Cesar A., Joshi, Milind M.
• Primary Examiner(s): Alam; Hosain T
• Assistant Examiner(s): Ahluwalia; Navneet K
• Application Number:
  US10/652,423
• Publication Number:
  US 20050050041A1
• Time in Patent Office: 2,034 Days
• Field of Search: 707 1- 10, 707100-1041, 707200-205
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 16/2462 Approximate or statistical queries
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation

Abstract

A query optimizer produces a preferred execution plan by utilizing statistics on views. These provide the optimizer with statistical information beyond that available on tables, for example, with information on the result of scalar or relational expressions. Pre-derived accurate statistics are thus available which are used to improve the accuracy of estimation and thus increase the quality and reliability of the query processor. Transformations of expressions and sub-expressions of candidate plans produce equivalent sub-expressions. Where those sub-expressions include references to views, an estimation of the cardinality and other execution statistics for the sub-expression can be made using the view statistics. This can be used to estimate the cardinality for all equivalent sub-expressions, leading to higher accuracy for the estimate.

Claims

1. A computer-implemented method for performing query optimization comprising:

developing at least one candidate plan for execution of a query;

receiving a user request to collect a view statistic of a view for at least one of said at least one candidate plan, the user request comprising a completeness level, the completeness level indicating a sampling of data from the view, as selected by the user, that is to be used in collecting the view statistic;

collecting the view statistic responsive to the user request and the completeness level;

for said at least one of said at least one candidate plan, using the view statistic to estimate the cost of said candidate plan; and

selecting at least one of said at least one candidate plans as a recommended execution plan,

wherein said step of using the view statistic to estimate the cost of said candidate plan comprises using at least one transformation rule to transform a first expression comprising all or part of said candidate plan and having an associated first expression estimate quality indicator into an equivalent second expression having an associated second expression estimate quality indicator, where said second expression comprises a reference to one or more views matching the first expression, and wherein said second expression and said first expression have an equivalent cardinality; and

wherein the step of selecting the recommended execution plan comprises one of the first expression and the second expression having the higher of the first expression estimate quality indicator and the second expression estimate quality indicator.

2. The computer-implemented method of claim 1, where said view statistic comprises a previously stored view statistic.

3. The computer-implemented method of claim 1, where said view statistic comprises a computed view statistic.

4. The computer-implemented method of claim 1, where said view statistic comprises a cardinality for a corresponding view.

5. The computer-implemented method of claim 1, where said view statistic comprises distribution data for values for at least one column in a corresponding view.

6. A computer readable storage medium having a tangible component for performing query optimization having stored thereon computer readable instructions, said instructions comprising instructions for:

developing at least one candidate plan for execution of a query;

receiving a user request to collect a view statistic of a view for at least one of said at least one candidate plan, the user request comprising a completeness level, the completeness level indicating a sampling of data from the view, as selected by the user, that is to be used in collecting the view statistic;

collecting the view statistic responsive to the user request and the completeness level;

for said at least one of said at least one candidate plan, using the view statistic to estimate the cost of said candidate plan; and

selecting at least one of said at least one candidate plans as a recommended execution plan,

wherein said step of using the view statistic to estimate the cost of said candidate plan comprises using at least one transformation rule to transform a first expression comprising all or part of said candidate plan and having an associated first expression estimate quality indicator into an equivalent second expression having an associated second expression estimate quality indicator, where said second expression comprises a reference to one or more views matching the first expression, and wherein said second expression and said first expression have an equivalent cardinality; and

wherein the step of selecting the recommended execution plan comprises one of the first expression and the second expression having the higher of the first expression estimate quality indicator and the second expression estimate quality indicator.

7. The computer storage readable medium of claim 6, where said view statistic comprises a previously stored view statistic.

8. The computer readable storage medium of claim 6, where said view statistic comprises a computed view statistic.

9. The computer readable storage medium of claim 6, where said view statistic comprises a cardinality for a corresponding view.

10. The computer readable storage medium of claim 6, where said view statistic comprises distribution data for values for at least one column in a corresponding view.

11. A system for performing query optimization having stored thereon computer readable instructions, said system comprising:

a processor;

a view statistics storage comprising storage for at least one view statistic, each of said at least one view statistic relating to a corresponding view and collected pursuant to a user request, the user request comprising a completeness level, the completeness level indicating a sampling of data from the view, as selected by the user, that is to be used in collecting the view statistic;

a query optimizer, operably connected to said view statistics storage, for developing at least one candidate plan for a query and using at least one of said at least one view statistic to estimate the cost of said candidate plan,

wherein said query optimizer estimates the cost of said candidate plan using at least one transformation rule to transform a first expression comprising all or part of said candidate plan and having an associated first expression estimate quality indicator into an equivalent second expression having an associated second expression estimate quality indicator,

where said second expression comprises a reference to one or more views matching the first expression,

wherein said second expression and said first expression have an equivalent cardinality, and

wherein said query optimizer is further adapted to select a recommended execution plan comprising one of the first expression and the second expression having the higher of the first expression estimate quality indicator and the second expression estimate quality indicator.

12. The system of claim 11, where at least one of said at least one view statistic comprises a cardinality for a corresponding view.

13. The system of claim 11, where at least one of said at least one view statistic comprises distribution data for values for at least one column in a corresponding view.

14. A computer-implemented method for implementing a database comprising:

allowing a user to request a view of data from said database, and a completeness level, the completeness level indicating a sampling of data from the view, as selected by the user, that is to be used in collecting the view statistic;

collecting a view statistic regarding said view responsive to the request and the completeness level;

developing at least one candidate plan for execution of a query;

for at least one of said at least one candidate plan, using said view statistic to estimate the cost of said candidate plan; and

selecting at least one of said at least one candidate plans as a recommended execution plan,

wherein said step of using the view statistic to estimate the cost of said candidate plan comprises using at least one transformation rule to transform a first expression comprising all or part of said candidate plan and having an associated first expression estimate quality indicator into an equivalent second expression having an associated second expression estimate quality indicator, where said second expression comprises a reference to one or more views matching the first expression, and wherein said second expression and said first expression have an equivalent cardinality; and

wherein the step of selecting the recommended execution plan comprises one of the first expression and the second expression having the higher of the first expression estimate quality indicator and the second expression estimate quality indicator.

15. The computer-implemented method of claim 14, where said step of collecting a view statistic regarding said view comprises:

detecting that said view has been materialized.

16. The computer-implemented method of claim 14, where said step of collecting a view statistic regarding said view comprises:

detecting a user request to store said view statistic; and

collecting said view statistic.

17. The computer-implemented method of claim 16, where said step of detecting a user request to store said view statistic comprises detecting a completeness level request for said view statistic, and said step of collecting said view statistic collects said view statistic to said requested completeness level.

18. The computer-implemented method of claim 17 where said step of using said view statistic to estimate the cost of said candidate plan comprises using said requested completeness level to determine the accuracy of said cost estimation.

19. A computer readable storage medium having a tangible component for implementing a database having stored thereon computer readable instructions, said instructions comprising instructions for:

allowing a user to request a view of data from said database, and a completeness level, the completeness level indicating a sampling of data from the view, as selected by the user, that is to be used in collecting the view statistic;

collecting a view statistic regarding said view responsive to the request and the completeness level;

developing at least one candidate plan for execution of a query;

for at least one of said at least one candidate plan, using said view statistic to estimate the cost of said candidate plan;

identifying an accuracy reading for the estimate, said accuracy reading reflecting the amount of data from which the view statistic was derived; and

selecting based upon the estimate of the cost and the accuracy reading at least one of said at least one candidate plans as a recommended execution plan,

wherein said step of using the view statistic to estimate the cost of said candidate plan comprises using at least one transformation rule to transform a first expression comprising all or part of said candidate plan and having an associated first expression estimate quality indicator into an equivalent second expression having an associated second expression estimate quality indicator, where said second expression comprises a reference to one or more views matching the first expression, and wherein said second expression and said first expression have an equivalent cardinality; and

wherein the step of selecting the recommended execution plan comprises one of the first expression and the second expression having the higher of the first expression estimate quality indicator and the second expression estimate quality indicator.

20. The computer readable storage medium of claim 19, where said collecting a view statistic regarding said view comprises:

detecting that said view has been materialized.

21. The computer readable storage medium of claim 19, where said collecting a view statistic regarding said view comprises:

detecting a user request to store said view statistic; and

collecting said view statistic.

22. The computer readable storage medium of claim 21, where said detecting a user request to store said view statistic comprises detecting a completeness level request for said view statistic, and said step of collecting said view statistic collects said view statistic to said requested completeness level.

23. The computer readable storage medium of claim 22 where said using said view statistic to estimate the cost of said candidate plan comprises using said requested completeness level to determine the accuracy of said cost estimation.

24. A system for implementing a database comprising:

a processor;

a user request module for a user to request a view of data from said database, and a completeness level, the completeness level indicating a sampling of data from the view, as selected by the user, that is to be used in collecting the view statistic;

a view statistic storage for collecting a view statistic regarding said view responsive to the request and the completeness level;

a candidate plan developer for developing at least one candidate plan for execution of a query;

an estimator, for at least one of said at least one candidate plan, using said view statistic to estimate the cost of said candidate plan; and

a candidate plan selector for selecting at least one of said at least one candidate plans as a recommended execution plan,

wherein said estimator estimates the cost of said candidate plan using at least one transformation rule to transform a first expression comprising all or part of said candidate plan and having an associated first expression estimate quality indicator into an equivalent second expression having an associated second expression estimate quality indicator, where said second expression comprises a reference to one or more views matching the first expression, and wherein said second expression and said first expression have an equivalent cardinality; and

wherein said candidate plan selector selects the recommended execution plan having one of the first expression and the second expression having the higher of the first expression estimate quality indicator and the second expression estimate quality indicator.