Group pruning from cube, rollup, and grouping sets

• US 6,775,662 B1
• Filed: 05/21/2001
• Issued: 08/10/2004
• Est. Priority Date: 05/21/2001
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Bozkaya, Tolga, Witkowski, Andrew
• Primary Examiner(s): Channavajjala, Srirama
• Assistant Examiner(s): Lu, Kuen S
• Application Number:
  US09/863,236
• Time in Patent Office: 1,177 Days
• Field of Search: 707/2, 707/3, 707/5
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24537 of operators
• 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/99935 Query augmenting and refining, e.g. inexact access

Abstract

A system rewrites queries so that they may be executed more efficiently. Queries that reference the result set of an aggregate query are rewritten to reference another aggregate query in the form of an inner query that omits groupings that can not possibly satisfy the criteria imposed by the predicates of the outer query. Thus, when the inner query is computed, only rows for groupings that satisfy the criteria are generated, conserving resources that would otherwise be wasted generating rows that could not possibly satisfy the criteria.

Claims

1. A method for processing queries, the method comprising the steps of:

receiving a particular query that operates on a result set of an aggregate query, wherein the aggregate query specifies an operation for computing the result set such that the result set groups rows by groupings of columns that include a first grouping;

determining whether the particular query specifies criteria that qualifies a subset of said groupings that does not include said first grouping; and

if the particular query specifies criteria that qualifies a subset of said groupings that does not include said first grouping, then rewriting said aggregate query to produce a rewritten query that generates a result set that groups rows by said subset of groupings.

2. The method of claim 1,

wherein said criteria is based on one or more expressions in said particular query that are based on a plurality of predicates;

and

wherein the step of determining includes examining said plurality of predicates to determine whether the particular query specifies criteria that qualifies said subset of said groupings.

3. The method of claim 2, further including the step of generating another set of expressions representing a disjunctive normal form of said one or more expressions;

wherein said set of expressions includes one or more conjunctions;

wherein the subset of groupings includes a second grouping; and

wherein the step of determining whether the particular query specifies criteria that qualifies a subset of said groupings includes the step of determining that said second grouping is qualified by at least one of said one or more conjunctions.

4. The method of claim 3, wherein the step of determining whether the particular query specifies criteria that qualifies a subset of said groupings includes determining that no conjunction of said one or more conjunctions qualifies said first grouping.

5. The method of claim 1, wherein the step of determining includes the step of generating a first set of patterns that describe one or more groupings that are qualified by said criteria.

6. The method of claim 5, wherein the step of determining includes determining that each grouping of said subset of groupings is qualified by at least one of pattern of said first set of patterns.

7. The method of claim 5, wherein each pattern of said first set of patterns indicates the particular columns in a qualified grouping that must be present, must not be present, or may or may not be present.

8. The method of claim 7, wherein each pattern of said first set of patterns is represented by a pair of bitmaps with bit positions that correspond to group-by columns of said result set.

9. The method of claim 5,

wherein said criteria is based on one or more expressions in said particular query that are based on a plurality of predicates;

and

wherein the step of determining includes;

generating a predicate tree based on said one or more expressions;

wherein said predicate tree includes leaf nodes and parent nodes, wherein each leaf node of said leaf nodes corresponds to a particular predicate of said plurality of predicates and each parent node of said parent nodes corresponds to a particular expression of said one or more expressions;

generating for each leaf node of said leaf nodes a pattern describing one or more groupings that qualify for the predicate corresponding to said each leaf node;

generating for each parent node of said parent nodes one or more patterns describing one or more groupings that qualify for the expression corresponding to said each parent node; and

wherein said parent nodes include a root node that corresponds to said first set of patterns.

10. The method of claim 1, wherein said aggregate query is an inner query of said particular query.

11. The method of claim 1, wherein said aggregate query includes one or more functions for specifying groupings including the rollup function, cube function, or grouping set function.

12. A method for processing queries, the method comprising the steps of:

receiving a particular query that includes an outer query that references the result set of an aggregate query;

wherein said aggregate query specifies a set of groupings;

wherein said outer query includes one or more predicates; and

rewriting said particular query to produce a rewritten query that omits one or more groupings from said set of groupings that only produce rows that can never satisfy said one or more predicates of the outer query.

13. A computer-readable medium carrying one or more sequences of instructions for processing queries, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

receiving a particular query that operates on a result set of an aggregate query, wherein the aggregate query specifies an operation for computing the result set such that the result set groups rows by groupings of columns that include a first grouping;

determining whether the particular query specifies criteria that qualifies a subset of said groupings that does not include said first grouping; and

if the particular query specifies criteria that qualifies a subset of said groupings that does not include said first grouping, then rewriting said aggregate query to produce a rewritten query that generates a result set that groups rows by said subset of groupings.

14. The computer-readable medium of claim 13,

wherein said criteria is based on one or more expressions in said particular query that are based on a plurality of predicates;

and

wherein the step of determining includes examining said plurality of predicates to determine whether the particular query specifies criteria that qualifies said subset of said groupings.

15. The computer-readable medium of claim 14, the steps further including the step of generating another set of expressions representing a disjunctive normal form of said one or more expressions;

wherein said set of expressions includes one or more conjunctions;

wherein the subset of groupings includes a second grouping; and

wherein the step of determining whether the particular query specifies criteria that qualifies a subset of said groupings includes the step of determining that said second grouping is qualified by at least one of said one or more conjunctions.

16. The computer-readable medium of claim 15, wherein the step of determining whether the particular query specifies criteria that qualifies a subset of said groupings includes determining that no conjunction of said one or more conjunctions qualifies said first grouping.

17. The computer-readable medium of claim 13, wherein the step of determining includes the step of generating a first set of patterns that describe one or more groupings that are qualified by said criteria.

18. The computer-readable medium of claim 17, wherein the step of determining includes determining that each grouping of said subset of groupings is qualified by at least one of pattern of said first set of patterns.

19. The computer-readable medium of claim 17, wherein each pattern of said first set of patterns indicates the particular columns in a qualified grouping that must be present, must not be present, or may or may not be present.

20. The computer-readable medium of claim 19, wherein each pattern of said first set of patterns is represented by a pair of bitmaps with bit positions that correspond to group-by columns of said result set.

21. The computer-readable medium of claim 17,

wherein said criteria is based on one or more expressions in said particular query that are based on a plurality of predicates;

and

wherein the step of determining includes;

generating a predicate tree based on said one or more expressions;

wherein said predicate tree includes leaf nodes and parent nodes, wherein each leaf node of said leaf nodes corresponds to a particular predicate of said plurality of predicates and each parent node of said parent nodes corresponds to a particular expression of said one or more expressions;

generating for each leaf node of said leaf nodes a pattern describing one or more groupings that qualify for the predicate corresponding to said each leaf node;

generating for each parent node of said parent nodes one or more patterns describing one or more groupings that qualify for the expression corresponding to said each parent node; and

wherein said parent nodes include a root node that corresponds to said first set of patterns.

22. The computer-readable medium of claim 13, wherein said aggregate query is an inner query of said particular query.

23. The computer-readable medium of claim 13, wherein said aggregate query includes one or more functions for specifying groupings including the rollup function, cube function, or grouping set function.

24. A computer-readable medium carrying one or more sequences of instructions for processing queries, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

receiving a particular query that includes an outer query that references the result set of an aggregate query;

wherein said aggregate query specifies a set of groupings;

wherein said outer query includes one or more predicates; and

rewriting said particular query to produce a rewritten query that omits one or more groupings from said set of groupings that only produce rows that can never satisfy said one or more predicates of the outer query.