Cost based materialized view selection for query optimization

• US 6,510,422 B1
• Filed: 09/27/2000
• Issued: 01/21/2003
• Est. Priority Date: 09/27/2000
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Galindo-Legaria, Cesar A., Joshi, Milind M.
• Primary Examiner(s): Mizrahi, Diane D.
• Application Number:
  US09/671,458
• Time in Patent Office: 846 Days
• Field of Search: 707/2, 707/3, 707/102
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24539 using cached or materialised query results
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 16/2458 Special types of queries, e.g. statistical queries, fuzzy queries or distributed queries
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A query optimizer determines the applicability of materialized views to a query. View utilization alternatives are generated in the exploration stage of optimization, so that interaction with other transformations in complex queries is taken into account. A final decision on whether to use a materialized view is based on estimated cost. The optimizer generates a table of alternatives, which compactly encodes the various possibilities for each sub-expression of the query. Optimal-cost operator trees are extracted from this table. Materialized views are detected and substituted during exploration of the various possibilities and added to the table of alternatives. Materialized views and the alternatives are selected for use in a query execution plan based on cost. When two operator trees are not identical, a residual operator can be used if one operator tree subsumes the other operator tree. The residual expression can contain operators such as filters, group by and join.

Claims

1. A method of selecting materialized views for use in execution of a database query, the method comprising:

obtaining a table of alternatives having multiple entries for execution of the query;

selecting relevant materialized views for the query;

for each entry and view;

extracting an operator tree for the entry and the view;

matching operator trees for entries and views; and

if a match is found, extending the table of alternatives with the view.

2. The method of claim 1 wherein extracting an operator tree for an entry containing binary joins comprises collapsing operators into a query graph.

3. The method of claim 2 wherein the collapsing of the operators into a query graph comprises listing underlying tables along with predicates that are applied on them.

4. The method of claim 1 wherein extracting an operator tree for a view comprises collapsing operators into a primitive graph-tree.

5. The method of claim 4 wherein a primitive graph-tree is restricted to a specific set of operators and is restricted to primitive tables.

6. The method of claim 5 wherein only join, outerjoins and filter operators are allowed in the operator tree for join graphs.

7. The method of claim 1 wherein the table of alternatives is extended by adding a root operator.

8. The method of claim 1 and further comprising:

using a cost based optimizer to select an execution plan based on the augmented table of alternatives.

9. A machine readable medium having instructions for causing a computer to perform a method of selecting materialized views for use in execution of a database query, the method comprising:

obtaining a table of alternatives having multiple entries for execution of the query;

selecting relevant materialized views for the query;

for each entry and view;

extracting an operator tree for the entry and the view;

matching operator trees for entries and views; and

if a match is found, extending the table of alternatives with the view.

10. The machine readable medium of claim 9 wherein extracting an operator tree for an entry containing binary joins comprises collapsing operators into a query graph.

11. The machine readable medium of claim 10 wherein the collapsing of the operators into a query graph comprises listing underlying tables along with predicates that are applied on them.

12. The machine readable medium of claim 9 wherein extracting an operator tree for a view comprises collapsing operators into a primitive graph-tree.

13. The machine readable medium of claim 12 wherein a primitive graph-tree is restricted to a specific set of operators and is restricted to primitive tables.

14. The machine readable medium of claim 13 wherein only join, outerjoin and filter operators are allowed in the operator tree for join graphs.

15. The machine readable medium of claim 9 wherein the table of alternatives is extended by adding a root operator.

16. The machine readable medium of claim 9 and further comprising:

using a cost based optimizer to select an execution plan based on the augmented table of alternatives.

17. A query optimizer that selects materialized views for use in execution of a database query, the query optimizer comprising:

means for obtaining a table of alternatives having multiple entries for execution of the query;

means for selecting relevant materialized views for the query;

for each entry and view;

means for extracting an operator tree for the entry and the view;

means for matching operator trees for entries and views; and

if a match is found, extending the table of alternatives with the view.

18. The query optimizer of claim 17 wherein means for extracting an operator tree for an entry containing binary joins and outerjoins comprises means for collapsing operators into a query graph.

19. The query optimizer of claim 18 wherein means for collapsing of the operators into a query graph comprises means for listing underlying tables along with predicates that are applied on them.

20. The query optimizer of claim 17 wherein means for extracting an operator tree for a view comprises means for collapsing operators into a primitive graph-tree.

21. The query optimizer of claim 20 wherein a primitive graph-tree is restricted to a specific set of operators and is restricted to primitive tables.

22. The query optimizer of claim 21 wherein only join, outerjoins and filter operators are allowed in the operator tree for join graphs.

23. The query optimizer of claim 17 wherein the table of alternatives is extended by adding a root operator.

24. The query optimizer of claim 17 and further comprising:

means for selecting an execution plan based on the augmented table of alternatives using a cost based optimizer.

25. A method of selecting materialized views for use in execution of a database query, the method comprising:

obtaining a table of alternatives for execution of the query;

augmenting the table of alternatives with selected materialized views; and

using a cost based optimizer to select an execution plan based on the augmented table of alternatives.

26. A computer readable medium having instructions to perform a method of selecting materialized views for use in execution of a database query, the method comprising:

obtaining a table of alternatives for execution of the query;

augmenting the table of alternatives with selected materialized views; and

using a cost based optimizer to select an execution plan based on the augmented table of alternatives.

27. A method of selecting materialized views for use in execution of a database query, the method comprising:

obtaining a table of alternative entries for execution of the query;

selecting relevant views for the query;

matching relevant views with each entry;

augmenting the table of alternative entries with select matching materialized views; and

using a cost based optimizer to select an execution plan based on the augmented table of alternatives.

28. A method of selecting materialized views for use in execution of a database query, the method comprising:

obtaining a table of alternatives having multiple entries for execution of the query;

selecting relevant materialized views for the query;

for each entry and view;

extracting an operator tree for the entry and the view;

attempting a subsumption map from a definition of the

materialized view to the operator tree;

matching operator trees for entries and views; and

if a match is found, extending the table of alternatives with the view.

29. The method of claim 28 wherein if the subsumption map attempt is successful, defining residual operations.

30. The method of claim 29 and further comprising adding defined residual operations to the table of alternatives.

31. The method of claim 30 wherein the residual operations are selected from the group consisting of filters, group by and joins.

32. The method of claim 28 wherein extracting an operator tree for an entry containing binary joins comprises collapsing operators into a query graph.

33. The method of claim 32 wherein the collapsing of the operators into a query graph comprises listing underlying tables along with predicates that are applied on them.

34. The method of claim 28 wherein extracting an operator tree for a view comprises collapsing operators into a primitive graph-tree.

35. The method of claim 34 wherein a primitive graph-tree is restricted to a specific set of operators and is restricted to primitive tables.

36. The method of claim 35 wherein only join and filter operators are allowed in the operator tree for join graphs.

37. The method of claim 28 wherein the table of alternatives is extended by adding a root operator.

38. The method of claim 28 and further comprising:

using a cost based optimizer to select an execution plan based on the augmented table of alternatives.

39. A computer readable medium having instructions for causing a computer to perform a method of selecting materialized views for use in execution of a database query, the method comprising:

obtaining a table of alternatives having multiple entries for execution of the query;

selecting relevant materialized views for the query;

for each entry and view;

extracting an operator tree for the entry and the view;

attempting a subsumption map from a definition of the

materialized view to the operator tree;

matching operator trees for entries and views; and

if a match is found, extending the table of alternatives with the view.

40. A method of selecting materialized views for use in execution of a database query, the method comprising:

obtaining a table of alternatives having multiple entries for execution of the query;

selecting relevant materialized views for the query;

for each entry and view;

extracting an operator tree for the entry by collapsing operators into a query graph

extracting an operator tree for the view by collapsing operators into a query graph;

attempting a subsumption map from a definition of the materialized view to the operator tree;

if the subsumption map attempt is successful, defining residual

operations;

matching operator trees for entries and views;

if a match is found, extending the table of alternatives with the view by adding a root operator; and

using a cost based optimizer to select an execution plan based on the augmented table of alternatives.

41. A computer readable medium having instructions for causing a computer to perform a method of selecting materialized views for use in execution of a database query, the method comprising:

obtaining a table of alternatives having multiple entries for execution of the query;

selecting relevant materialized views for the query;

for each entry and view;

extracting an operator tree for the entry by collapsing operators into a query graph

extracting an operator tree for the view by collapsing operators into a query graph;

attempting a subsumption map from a definition of the materialized view to the operator tree;

if the subsumption map attempt is successful, defining residual operations;

matching operator trees for entries and views;

if a match is found, extending the table of alternatives with the view by adding a root operator; and

using a cost based optimizer to select an execution plan based on the augmented table of alternatives.