Use of materialized transient views in query optimization

• US 20070250473A1
• Filed: 04/21/2006
• Published: 10/25/2007
• Est. Priority Date: 04/21/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Larson, Per-Ake, Zhou, Jingren
• Granted Patent: US 7,693,820 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24539 using cached or materialised query results
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing

Abstract

Methods and systems for integrating use of materialized transient views into generation of an optimized query execution plan. Features and aspects hereof provide rapid identification of common expressions in a query as transient view candidates and then rapidly select among the transient view candidates for those transient views that most benefit the cost of execution of the query. The selected transient views are incorporated into a generated final, optimized query execution plan including operator to materialize the selected transient views for re-use in execution of the query.

Claims

1. A method of optimizing a database query or batch of queries, the method comprising:

identifying sharable subexpressions in a query;

generating one or more transient view candidates covering sets of sharable subexpressions;

selecting from among the transient view candidates those candidates that are most beneficial for execution of the query; and

generating an optimized query execution plan including the selected transient views and including operators to materialize the selected transient views for re-use during execution of the optimized query execution plan.

2. The method of claim 1

wherein the step of identifying further comprises:

determining a table signature associated with each expression of the query;

storing the table signature associated with said each expression; and

identifying sharable subexpressions as expressions having the same table signature.

3. The method of claim 2

wherein the step of storing further comprises storing each table signature in a hash table structure using the table signature to compute a hash table index value.

4. The method of claim 1

wherein the step of selecting further comprises:

applying one or more heuristic rules to eliminate one or more of the generated transient view candidates to reduce the set of transient view candidates.

5. The method of claim 4

wherein the step of applying one or more heuristic rules further comprises:

applying one or more heuristic rules to eliminate any identified transient view candidates the use of which is not likely to improve execution performance of the optimized query plan, the heuristic rules selected from the group consisting of;

eliminating any transient view candidate for which the estimated total cost of evaluating its potential consumers does not exceed a minimum threshold portion of the estimated total cost for evaluating the query;

eliminating any potential consumer expression from consideration when constructing a candidate transient view if the estimated cost of evaluating the expression without use of the transient view candidate is less than the estimated cost of evaluating the expression by scanning the transient view candidate;

eliminating any transient view candidate wherein the transient view candidate Vnew represents the merger of two other transient view candidates V1 and V2 and wherein the estimated cost of evaluating the potential consumers using Vnew is greater than the estimated cost of evaluating them using V1 and V2;

eliminating any transient view candidate wherein the maximum benefit for use of the transient view candidate in evaluating the query does not exceed a minimum threshold portion of the estimated total cost for evaluating the query; and

eliminating any transient view candidate if it is contained by a wider view candidate with the same potential consumers and where the result size of the transient view candidate exceeds a minimum threshold portion of the size of the wider candidate. A view V1 is wider than another view V2 if V1 references the same tables as V2 plus at least one additional table.

6. The method of claim 1

wherein the step of selecting further comprises:

repeating cost-based query optimization to select one or more of the identified transient view candidates based on costs associated with each identified transient view candidate to generate the selected transient view candidates for inclusion in the optimized query plan.

7. The method of claim 1

wherein the step of selecting further comprises:

generating an ordered list L containing all subsets of the set of transient view candidates wherein the list is sorted in decreasing order of the size of the subsets;

extracting a first subset S from list L;

re-optimizing the query using cost-based optimization with subset S;

applying a rule to eliminate those subsets from list L that need not be considered; and

repeating the steps of extracting, re-optimizing, and applying a rule for all subsets remaining in list L to determine one or more selected transient view candidates for each subset of the transient view candidates evaluated by the re-optimization.

8. The method of claim 7

wherein the step of applying a rule further comprises applying a rule selected from the group consisting of:

Rule 1;

Suppose S=T∪

R, T∩

R=Ø

, is a set of candidate transient views such that every candidate transient view in T is independent of all other candidate transient views in S. After the query has been optimized with S enabled, optimization for any set S_i such that S_i⊂

S, S_i∩

R=R and S_i∩

T⊂

T can be skipped.

Rule 2;

For each optimization, if the returned optimal plan uses a subset S^used of the enabled transient views, the returned plan is optimal also if optimizing with only S^used enabled thus optimization with only S^used enabled can be skipped At the same time, the optimization as having been done with S^used enabled can be skipped and the previous observation applied to eliminate additional combinations.

9. The method of claim 1

wherein the one or more identified transient view candidates comprises a plurality of identified transient view candidates,

wherein the step of selecting further comprises:

determining through cost-based query optimization analysis a best query execution plan presuming all of the plurality of identified transient view candidates are enabled for substitution cost-based query optimization wherein the best query execution plan so determined uses a first subset of the plurality of identified transient view candidates;

repeating the cost-based analysis to determine other best query execution plans only for other subsets of the plurality of identified transient view candidates where each other subset has at least as many elements as the first subset; and

selecting a best query execution plan having lowest estimated cost from among the determined best query execution plans as the optimized query execution.

10. A method of processing an SQL query, the method comprising:

identifying sharable expressions in the SQL query as transient view candidates;

applying one or more heuristic rules to eliminate from further consideration in processing the query any of the identified transient view candidates unlikely to substantially improve execution performance of the SQL query;

performing cost-based query optimization estimating the cost of each of one or more subsets of the identified transient view candidates to generate a final query plan including any remaining identified transient view candidates after application of heuristic; and

executing the final query plan including the step of materializing the remaining identified transient view candidates for re-use while executing the final query plan.

11. The method of claim 10

wherein the step of identifying further comprises:

computing a table signature value associated with each expression; and

identifying two or more expressions having equal table signature values as sharable expressions.

12. The method of claim 10

wherein the step of applying one or more heuristic rules further comprises:

applying one or more heuristic rules to eliminate any identified transient view candidates the use of which is not likely to improve performance of the final query plan, the heuristic rules selected from the group consisting of;

eliminating any transient view candidate for which the estimated total cost of evaluating its potential consumers does not exceed a minimum threshold portion of the estimated total cost for evaluating the query;

eliminating any potential consumer expression from consideration when constructing a candidate transient view if the estimated cost of evaluating the expression without use of the transient view candidate is less than the estimated cost of evaluating the expression by scanning the transient view candidate;

eliminating any transient view candidate wherein the transient view candidate Vnew represents the merger of two other transient view candidates V1 and V2 and wherein the estimated cost of evaluating the potential consumers using Vnew is greater than the estimated cost of evaluating them using V1 and V2;

eliminating any transient view candidate wherein the maximum benefit for use of the transient view candidate in evaluating the query does not exceed a minimum threshold portion of the estimated total cost for evaluating the query; and

eliminating any transient view candidate if it is contained by a wider view candidate with the same potential consumers and where the result size of the transient view candidate exceeds a minimum threshold portion of the size of the wider candidate. A view V1 is wider than another view V2 if V1 references the same tables as V2 plus at least one additional table.

13. The method of claim 10

wherein the step of performing cost-based query optimization further comprises:

determining an initial cost for each of the identified transient view candidates wherein the initial cost of a identified transient view candidate includes a cost of computing the identified transient view candidate and includes a cost of writing the identified transient view candidate;

representing the query as an operator tree where each node of the operator tree comprises either a source table or an operation node representing a view formed by an operator applied to one or more other views or source tables represented as child nodes of the node;

determining the final query plan by determining the lowest estimated cost query plan including any subset of the set of identified transient view candidates where the step of determining evaluates less than all identified subset of the set of all identified transient view candidates.

14. The method of claim 10

wherein the step of applying heuristics further comprises:

generating an ordered list L containing all subsets of the set of transient view candidates wherein the list is sorted in decreasing order of the size of the subsets;

extracting a first subset S from list L;

re-optimizing the query using cost-based optimization with subset S;

applying a rule to eliminate those subsets from list L that need not be considered; and

repeating the steps of extracting, re-optimizing, and applying a rule for all subsets remaining in list L to determine zero or more selected transient view candidates for each subset of the transient view candidates evaluated by the re-optimization.

15. The method of claim 14

wherein the step of applying a rule further comprises applying a rule selected from the group consisting of:

Rule 1;

Suppose S=T∪

R, T∩

R=Ø

, is a set of candidate transient views such that every candidate transient view in T is independent of all other candidate transient views in S. After the query has been optimized with S enabled, optimization for any set S_i such that S_i⊂

S, S_i∩

R=R and S_i∩

T⊂

T can be skipped.

Rule 2;

For each optimization, if the returned optimal plan uses a subset S^used of the enabled transient views, the returned plan is optimal also if optimizing with only S^used enabled thus optimization with only S^used enabled can be skipped At the same time, the optimization as having been done with S^used enabled can be skipped and the previous observation applied to eliminate additional combinations.

16. A database query processing system comprising:

a query compiler adapted to receive one or more query and adapted to translate the received query into an operator tree including views and operators representing the received query;

a transient view manager adapted to store information regarding identified transient views; and

a query optimizer coupled to receive the operator tree from the query compiler and coupled to exchange information regarding identified transient views with the transient view manager, the query optimizer adapted to generate a query execution plan including zero or more identified transient views to perform the received query.

17. The system of claim 16

wherein the query optimizer is adapted to compute a table signature for each identified transient view and is adapted to store the table signature in cooperation with the transient view manager wherein the table signature identifies the source tables in the transient view.

18. The system of claim 17

wherein the query optimizer is adapted to identify common transient views used in the query that may be materialized to optimize execution of the query.

19. The system of claim 18

wherein the query optimizer is adapted to identify common transient view that may be most beneficially materialized to optimize execution of the query by heuristically eliminating any transient views that are not likely to be beneficial to query optimization.

20. The system of claim 18

wherein the query optimizer is adapted to identify common transient view that may be most beneficially materialized to optimize execution of the query by estimating costs of each transient view and by evaluating the reduction in query execution cost by evaluating subsets of the set of all common transient views.