System and method for selection of materialized views

• US 7,191,169 B1
• Filed: 01/16/2003
• Issued: 03/13/2007
• Est. Priority Date: 05/21/2002
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Tao, Dongbin
• Primary Examiner(s): Wong; Don
• Assistant Examiner(s): NGUYEN, MERILYN P
• Application Number:
  US10/345,565
• Time in Patent Office: 1,517 Days
• Field of Search: 707 1- 7, 707/10, 707100-102, 707/104.1
• US Class Current: 707/714
• 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/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A method for selecting and recommending materialized views is described, in which a set of workload queries is classified in terms of a number of structural features that includes the structure of the join operations in the query (“full query join graph”), the structure of a specific subset of the join operations (“anchor join graph”), and other characteristics such as the measures, selection predicates, and grouping conditions employed in the query. These features are used to implement a two-level partitioned search for the recommended materialized views.

Claims

1. A method for selecting one or more materialized views based on a plurality of user-supplied queries, comprising the steps of:

classifying each of the plurality of user-supplied queries in terms of a full join graph and an anchor join graph wherein the anchor join graph is a smallest sub-graph of the full join graph and wherein any joins between the tables in the sub-graph and those outside the sub-graph are lossless;

selecting a set for materialized views for each set of user-supplied queries of the plurality of user-supplied queries classified to a same full join graph;

selecting the one or more materialized views based on the set of selected materialized views for each set of user-supplied queries classified to a same anchor join graph; and

outputting said selected materialized views.

2. A method according to claim 1, wherein the anchor join graph includes a smallest sub-graph of a query join graph such that all joins with tables outside of the sub-graph are lossless.

3. A method according to claim 1, further comprising the step of:

filtering each of the plurality of user-supplied queries to eliminate queries that are rewritten by a database kernel and

selecting said one or more materialized views.

4. A method according to claim 1, further comprising the steps of:

resolving group-by expressions of each of the plurality of user-supplied queries into basic columns;

classifying each of the plurality of user-supplied queries in terms of the resolved group-by expressions; and

selecting the number of materialized views based on the classified group-by expressions.

5. A method according to claim 1, further comprising the steps of:

classifying each of the plurality of user-supplied queries in terms of classified measures; and

selecting the number of materialized views based on the classified measures.

6. A method according to claim 1, further comprising the steps of:

classifying each of

the plurality of user-supplied queries in terms of ranges of values; and

selecting the number of materialized views based on the classified ranges of values.

7. A computer-readable medium bearing instructions for selecting one or more materialized views based on a plurality of user-supplied queries, said instructions being arranged, when executed, to cause one or more processors to perform the method according to claim 1, wherein the computer-readable medium is one of:

volatile memory and non-volatile memory.

8. A method for selecting one or more materialized views based on a plurality of user-supplied queries, comprising the steps of:

filtering each of the plurality of user-supplied queries in the plurality of user-supplied queries to identify user-supplied queries that are written by a data kernel;

classifying a user-supplied query that remains in terms of one or more structural features;

selecting the one or more materialized views based on the classified structural features, wherein the user-supplied query is classified in terms of a full join graph and an anchor join graph wherein the anchor join graph is a smallest sub-graph of the full join graph and wherein any joins between the tables in the sub-graph and those outside the sub-graph are lossless; and

outputting said selected one or more materialized views.

9. A method according to claim 8, wherein the classified structural features include one or more of:

a full query join graph, an anchor join graph, a measure, a selection predicate, and a grouping condition.

10. A method according to claim 8, wherein:

the classified structural features include at least a full query join graph, an anchor join graph; and

said selecting includes;

for each set of the queries classified to a same full join graph, selecting a set of materialized views; and

for each set of the queries classified to a same anchor join graph, selecting the one or more materialized views based on the set of selected materialized views.

11. A computer-readable medium bearing instructions for selecting one or more materialized views based on a plurality of user-supplied queries, said instructions being arranged, when executed, to cause one or more processors to perform the method according to claim 8, wherein the computer-readable medium is one of:

volatile memory and non-volatile memory.

12. A method for selecting one or more materialized views based on a plurality of user-supplied queries, comprising the steps of:

classifying each of the user-supplied queries in terms of at least a first anchor join graph and a second anchor join graph wherein an anchor join graph is a smallest sub-graph of a full join graph and wherein any joins between the tables in the sub-graph and those outside the sub-graph are lossless;

selecting materialized views for the user-supplied queries classified in terms of the first anchor join graph;

selecting materialized views for the user-supplied queries classified in terms of the second anchor join graph; and

outputting said selected materialized views.

13. A computer-readable medium bearing instructions for selecting one or more materialized views based on a plurality of user-supplied queries, said instructions being arranged, when executed, to cause one or more processors to perform the method according to claim 12, wherein the computer-readable medium is one of:

volatile memory and non-volatile memory.

14. A system for selecting one or more materialized views based on a plurality of user-supplied queries, comprising:

a processor operable to execute computer program instructions; and

a memory operable to store computer program instructions executable by the processor, for performing the steps of;

classifying each of the user-supplied queries in terms of a full join graph and an anchor join graph wherein the anchor join graph is a smallest sub-graph of the full join graph and wherein any joins between the tables in the sub-graph and those outside the sub-graph are lossless, wherein each of the queries is classified in terms of one or more structural features including the full join graph and the anchor join graph;

selecting the one or more materialized views based on said classifying; and

outputting said selected one or more materialized views.