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

• US 20050091208A1
• Filed: 10/29/2004
• Published: 04/28/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
• Granted Patent: US 7,383,256 B2
• Time in Patent Office: Days
• 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-42. -42. (canceled)

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

means for receiving a query expression;

means for receiving a plurality of materialized views;

means for generating a candidate subset of the materialized views;

means for 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

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

44. The method of claim 43, wherein means for generating the candidate subset of materialized views comprises means for determining which of the plurality of materialized views cannot be used.

45. The method of claim 44, wherein means for determining which of the plurality of materialized views cannot be used comprises means for searching a filter tree having a plurality of nodes.

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

47. The method of claim 46, 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.

48. The method of claim 43, further comprising means for storing descriptions of the plurality of materialized views in a storage memory prior to receiving the plurality of materialized views.

49. The method of claim 48, wherein means for storing the descriptions of the plurality of materialized views in a storage memory comprises means for storing each of the materialized views as a table.

50. The method of claim 43, wherein means for 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.

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

52. The method of claim 51, wherein means for determining whether each materialized view of the candidate subset comprises the plurality of rows needed by the query expression comprises:

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

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

means for determining whether the equijoin subsumption test is satisfied;

means for determining a plurality of range intervals for the query expression;

means for determining a plurality of range intervals for the materialized view;

means for determining whether the range subsumption test is satisfied; and

means for determining whether the residual subsumption test is satisfied.

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

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

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

56. A computer readable medium having stored thereon a data structure, comprising:

a first data field for receiving a query expression;

a second data field for receiving a plurality of materialized views;

a third data field for generating a candidate subset of the materialized views;

a fourth data field for 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

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

57. The computer readable medium of claim 56, having stored thereon a fifth data structure for determining which of the plurality of materialized views cannot be used when generating the candidate subset of materialized views.

58. The computer readable medium of claim 57, having stored thereon a sixth data structure for searching a filter tree having a plurality of nodes when determining which of the plurality of materialized views cannot be used.

59. The computer readable medium of claim 58, having stored thereon a seventh data structure for recursively subdividing the materialized views into non-overlapping partitions by applying predetermined partitioning conditions when searching the filter tree.

60. The computer readable medium of claim 59, 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.

61. The computer readable medium of claim 56, having stored thereon an eighth data structure for storing descriptions of the plurality of materialized views in a storage memory prior to receiving the plurality of materialized views.

62. The computer readable medium of claim 61, having stored thereon a ninth data structure for storing each of the materialized views as a table when storing the descriptions of the plurality of materialized views in a storage memory.

63. The computer readable medium of claim 56, having stored thereon a tenth data structure 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.

64. The computer readable medium of claim 63, having stored thereon an eleventh data structure 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.

65. The computer readable medium of claim 64, having stored thereon a twelfth data structure 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.

66. The computer readable medium of claim 63, having stored thereon a thirteenth data structure for determining whether a plurality of rows needed by the query expression are extractable from the materialized view.

67. The computer readable medium of claim 63, having stored thereon a fourteenth data structure for determining whether a plurality of output expressions needed by the materialized view can be determined from the materialized view.

68. The computer readable medium of claim 63, having stored thereon a fifteenth data structure 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.