Using query expression signatures in view matching

• US 7,599,925 B2
• Filed: 03/31/2005
• Issued: 10/06/2009
• Est. Priority Date: 03/31/2005
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zhou, Jingren, DeHann, David Edward, Larson, Per-Ake
• Primary Examiner(s): Alam; Shahid A
• Assistant Examiner(s): Khakhar; Nirav K
• Application Number:
  US11/094,924
• Publication Number:
  US 20060230017A1
• Time in Patent Office: 1,650 Days
• Field of Search: None
• 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
• 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 system for optimizing queries against a database is described. The system comprises a memo structure that encodes a plurality of query expressions. The system also includes a signature mechanism that enables an assignment of the query expressions into equivalence classes. Methods of using such a system are additionally provided.

Claims

1. A computer implemented system for optimizing queries against a database, comprising:

at least a processor executing the following components;

a memo structure that encodes a plurality of query expressions frequently encountered in queries as a set of explored operator trees such that an operator tree comprises at least select, project, join and group-by operators;

a signature mechanism that enables an assignment of the query expressions into equivalence classes, each class access the same set of base tables, wherein the signature data structure is a synopsis of the plurality of query expressions in the memo structure and is stored in the memo structure, the signature facilitates identification of at least one query expression from the memo structure that can be matched and substituted with at least a subset of a given query expression, the identified query expression is utilized to access a stacked materialized view of the database, wherein each signature for an operator tree in the memo structure is a tuple comprising at least an indication of whether a root of the corresponding operator tree is a group-by operator, a set of sources including tables and views used as input for operators with in the operator tree, and a set of candidate views for the operator tree; and

wherein memory coupled to a processor retains the memo structure or the signature mechanism.

2. The system of claim 1, the query expressions of an equivalence class have common input sources.

3. The system of claim 2, the query optimizer is a transformation-based optimizer.

4. The system of claim 1, further comprising a query optimizer that uses the signature mechanism to identify at least one of the plurality of query expressions that can be substituted for an initial query expression.

5. The system of claim 4, further comprising a relational database that uses the query optimizer to access data.

6. The system of claim 5, the relational database includes a materialized view.

7. The system of claim 6, the at least one of the plurality of query expressions can reference the materialized view.

8. The system of claim 1, wherein the identified query expression a query minimizes amount of computation necessary to obtain results desired by a user.

9. A method for optimizing queries against a database, comprising:

employing a processor to execute computer executable instructions stored in memory to perform the following acts;

encoding a plurality of query expressions into a memo structure as a set of explored operator trees such that an operator tree comprises at least select, project, join and group-by operators;

generating a signature for each of the operator trees such that the signature comprises boolean information corresponding to a root of an operator tree being a group-by operator, a set of sources including tables and views used as input for operators within the operator tree, and a set of candidate views for the operator tree; and

identifying at least one of the plurality of query expressions that can be substituted for an initial query expression using the signature such that the identified query expression accesses at least a stacked materialized view of the database, and the signature assists in identifying the query expressions via input-distinct bindings of a corresponding operator tree when matching the stacked views and estimating potential that a single query operator from an operator tree corresponding to the given query expression will cause one or more materialized views to be matched;

substituting the identified query expression for the initial query expression; and

using the identified query expression to access data of a relational database by accessing the stacked materialized view.

10. A computer implemented system for optimizing queries against a database, comprising the following computer executable components:

means for storing a plurality of query expressions frequently encountered in queries as a set of explored operator trees such that an operator tree comprises at least select, project, join and group-by operators;

means for identifying query expressions from the storing means that can be substituted for at least a subset of a given query expression to generate an optimized query such that the identified query expression is utilized to access a stacked materialized view of the database, the substitute query expressions are identified by determining bindings with different inputs for an operator tree corresponding to the given query expression when matching the stacked views and estimating potential that a single query operator from an operator tree corresponding to the given query expression will cause one or more materialized views to be matched, the identifying means comprises boolean information regarding a root of an operator tree corresponding to the identified query expression being a group-by operator, a set of sources including tables and views to be used as input for operators within the operator tree, and a set of candidate views for the operator tree; and

means for displaying results obtained by executing the optimized query on at least one stacked materialized view of a relational database.