System and method for optimizing queries using materialized views and fast view matching

• US 6,850,933 B2
• Filed: 11/15/2001
• Issued: 02/01/2005
• Est. Priority Date: 11/15/2001
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Larson, Per-Ake, Goldstein, Jonathan
• Primary Examiner(s): Ali, Mohammad
• Application Number:
  US10/000,989
• Publication Number:
  US 20030093415A1
• Time in Patent Office: 1,174 Days
• Field of Search: 707 1- 10, 707100-1541, 707200-205
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24535 of sub-queries or views
• CPC Class Codes: G06F 16/24539 using cached or materialised query results
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A transformation-based optimizer generates rewritings by applying local algebraic transformation rules on subexpressions of a query. Application of a transformation rule produces substitute expressions, logically equivalent to the original expression. View matching, that is, computing a subexpression from materialized views, is one such transformation rule. The view matching rule applies a view matching technique that determines whether the original query can be computed from one or more of the existing materialized views and, if so, generates substitute expressions. An index structure of materialized views is provided that quickly narrows the search to a set of candidate views on which the view matching techniques can be applied. The index structure, also called a filter tree, speeds up the search for applicable materialized views.

Claims

1. A method for generating a substitute expression for a query expression comprising:

receiving a query expression;

receiving a plurality of materialized views;

generating a candidate subset of the materialized views;

determining qualifying materialized views based on the candidate subset by determining whether an equijoin subsumption test is satisfied, determining whether a range subsumption test is satisfied, and determining whether a residual subsumption test is satisfied; and

generating a substitute expression for the query expression based on each qualifying materialized view.

2. The method of claim 1, wherein generating the candidate subset of materialized views comprises determining which of the plurality of materialized views cannot be used.

3. The method of claim 2, wherein determining which of the plurality of materialized views cannot be used comprises searching a filter tree having a plurality of nodes.

4. The method of claim 3, wherein searching the filter tree comprises recursively subdividing the materialized views into non-overlapping partitions by applying predetermined partitioning conditions.

5. The method of claim 4, wherein the predetermined partitioning conditions comprise at least one of source table conditions, hub conditions, output column conditions, grouping columns conditions, range constraint conditions, residual predicate conditions, output expression conditions, and grouping expression conditions.

6. The method of claim 1, further comprising storing descriptions of the plurality of materialized views in a storage memory prior to receiving the plurality of materialized views.

7. The method of claim 6, wherein storing the descriptions of the plurality of materialized views in a storage memory comprises storing each of the materialized views as a table.

8. The method of claim 1, wherein determining the qualifying materialized views based on the candidate subset comprises checking each materialized view of the candidate subset against at least one predetermined condition.

9. The method of claim 8, wherein checking each materialized view against at least one predetermined condition comprises determining whether each materialized view of the candidate subset comprises a plurality of rows needed by the query expression.

10. The method of claim 9, wherein determining whether each materialized view of the candidate subset comprises the plurality of rows needed by the query expression comprises:

determining a plurality of column equivalence classes for the query expression;

determining a plurality of column equivalence classes for the materialized view;

determining whether the equijoin subsumption test is satisfied;

determining a plurality of range intervals for the query expression;

determining a plurality of range intervals for the materialized view;

determining whether the range subsumption test is satisfied; and

determining whether the residual subsumption test is satisfied.

11. The method of claim 8, wherein checking each materialized view against at least one predetermined condition comprises determining whether a plurality of rows needed by the query expression are extractable from the materialized view.

12. The method of claim 8, wherein checking each materialized view against at least one predetermined condition comprises determining whether a plurality of output expressions needed by the materialized view can be determined from the materialized view.

13. The method of claim 8, wherein checking each materialized view against at least one predetermined condition comprises determining a first plurality of tables referenced by the query expression, determining a second plurality of tables referenced by the materialized view, and comparing the first and second plurality of tables to determine a duplication factor.

14. A computer readable medium having computer-executable instructions for carrying out the method of:

receiving a query expression;

receiving a plurality of materialized views;

generating a candidate subset of the materialized views;

determining qualifying materialized view based on the candidate subset by determining whether an equijoin subsumption test is satisfied, determining whether a range subsumption test is satisfied, and determining whether a residual subsumption test is satisfied; and

generating a substitute expression for the query expression based on each qualifying materialized view.

15. The computer readable medium of claim 14, having further computer-executable instructions for determining which of the plurality of materialized views cannot be used when generating the candidate subset of materialized views.

16. The computer readable medium of claim 15, having further computer-executable instructions for searching a filter tree having a plurality of nodes when determining which of the plurality of materialized views cannot be used.

17. The computer readable medium of claim 16, having further computer-executable instructions for recursively subdividing the materialized views into non-overlapping partitions by applying predetermined partitioning conditions when searching the filter tree.

18. The computer readable medium of claim 17, wherein the predetermined partitioning conditions comprise at least one of source table conditions, hub conditions, output column conditions, grouping columns conditions, range constraint conditions, and residual predicate conditions, output expression conditions, and grouping expression conditions.

19. The computer readable medium of claim 14, having further computer-executable instructions for storing descriptions of the plurality of materialized views in a storage memory prior to receiving the plurality of materialized views.

20. The computer readable medium of claim 19, having further computer-executable instructions for storing each of the materialized views as a table when storing the descriptions of the plurality of materialized views in a storage memory.

21. The computer readable medium of claim 14, having further computer-executable instructions for checking each materialized view of the candidate subset against at least one predetermined condition when determining the qualifying materialized views based on the candidate subset.

22. The computer readable medium of claim 21, having further computer-executable instructions for determining whether each materialized view of the candidate subset comprises a plurality of rows needed by the query expression when checking each materialized view against at least one predetermined condition.

23. The computer readable medium of claim 22, having further computer-executable instructions for:

determining a plurality of column equivalence classes for the query expression;

determining a plurality of column equivalence classes for the materialized view;

determining whether the equijoin subsumption test is satisfied;

determining a plurality of range intervals for the query expression;

determining a plurality of range intervals for the materialized view;

determining whether the range subsumption test is satisfied; and

determining whether the residual subsumption test is satisfied.

24. The computer readable medium of claim 21, having further computer-executable instructions for determining whether a plurality of rows needed by the query expression are extractable from the materialized view.

25. The computer readable medium of claim 21, having further computer-executable instructions for determining whether a plurality of output expressions needed by the materialized view can be determined from the materialized view.

26. The computer readable medium of claim 21, having further computer-executable instructions for determining a first plurality of tables referenced by the query expression, determining a second plurality of tables referenced by the materialized view, and comparing the first and second plurality of tables to determine a duplication factor.

27. A server in a database system wherein the server generates a substitute expression for a query expression by (a) receiving the query expression;

(b) receiving a plurality of materialized views;

(c) generating a candidate subset of the materialized views;

(d) determining qualifying materialized views based on the candidate subset by determining whether an equijoin subsumption test is satisfied, determining whether a range subsumption test is satisfied, and determining whether a residual subsumption test is satisfied; and

(e) generating a substitute expression for the query expression based on each qualifying materialized view.

28. The server of claim 27, wherein generating the candidate subset of materialized views comprises determining which of the plurality of materialized views cannot be used.

29. The server of claim 28, wherein determining which of the plurality of materialized views cannot be used comprises searching a filter tree having a plurality of nodes.

30. The server of claim 29, wherein searching the filter tree comprises recursively subdividing the materialized views into non-overlapping partitions by applying predetermined partitioning conditions.

31. The server of claim 30, wherein the predetermined partitioning conditions comprise at least one of source table conditions, hub conditions, output column conditions, grouping columns conditions, range constraint conditions, residual predicate condition, output expression condition, and grouping expression condition.

32. The server of claim 27, further comprising storing descriptions of the plurality of materialized views in a storage memory prior to receiving the plurality of materialized views.

33. The server of claim 32, wherein storing the descriptions of the plurality of materialized views in a storage memory comprises storing each of the materialized views as a table.

34. The server of claim 27, wherein determining the qualifying materialized views based on the candidate subset comprises checking each materialized view of the candidate subset against at least one predetermined condition.

35. The server of claim 34, wherein checking each materialized view against at least one predetermined condition comprises determining whether each materialized view of the candidate subset comprises a plurality of rows needed by the query expression.

36. The server of claim 35, wherein determining whether each materialized view of the candidate subset comprises the plurality of rows needed by the query expression comprises:

determining a plurality of column equivalence classes for the query;

determining a plurality of column equivalence classes for the materialized view;

determining whether the equijoin subsumption test is satisfied;

determining a plurality of range intervals for the query expression;

determining a plurality of range intervals for the materialized view;

determining whether the range subsumption test is satisfied; and

determining whether the residual subsumption test is satisfied.

37. The server of claim 34, wherein checking each materialized view against at least one predetermined condition comprises determining whether a plurality of rows needed by the query expression are extractable from the materialized view.

38. The server of claim 34, wherein checking each materialized view against at least one predetermined condition comprises determining whether a plurality of output expressions needed by the materialized view can be determined from the materialized view.

39. The server of claim 34, wherein checking each materialized view against at least one predetermined condition comprises determining a first plurality of tables referenced by the query expression, determining a second plurality of tables referenced by the materialized view, and comparing the first and second plurality of tables to determine a duplication factor.