Cube indices for relational database management systems

• US 6,560,594 B2
• Filed: 09/22/1999
• Issued: 05/06/2003
• Est. Priority Date: 05/13/1999
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Sun, Yang, Zaharioudakis, Markos, Pirahesh, Mir Hamid, Leung, Ting Yu, Lapis, George, Cochrane, Roberta Jo
• Primary Examiner(s): Alam, Hosain T.
• Assistant Examiner(s): Ly, Anh
• Application Number:
  US09/401,474
• Publication Number:
  US 20020138460A1
• Time in Patent Office: 1,322 Days
• Field of Search: 707/1-10
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2264 Multidimensional index structures
• 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

Abstract

A method, apparatus, and article of manufacture for optimizing database queries using subsumption tests between the query and at least one summary table that comprises a cube index to determine whether an expression in the query can be subsumed in the summary table. The summary table stores at least one materialized view involving at least one GROUP BY operation that computes at least one of the following: (1) a cube, (2) a rollup, (3) a grouping set, and (4) a concatenation of cubes, rollups, grouping sets, and one or more grouping items. When the expression in the query can be subsumed in the summary table, the query is rewritten to use the summary table.

Claims

1. A method of optimizing a query in a computer system, the query being performed by the computer system to retrieve data from a database stored on the computer system, the method comprising the steps of:

(a) analyzing a query in the computer system using subsumption tests between the query and at least one summary table that comprises a cube index to determine whether an expression in the query can be subsumed by the summary table, wherein the summary table stores at least one materialized view involving at least one GROUP BY operation that computes at least one of the following;

(1) a cube, (2) a rollup, (3) a grouping set; and

(4) a concatenation of cubes, rollups, grouping sets and one or more grouping items; and

(b) when the expression in the query can be subsumed in the summary table, rewriting the query using a slice of the cube index.

2. The method of claim 1, further comprising the step of executing the rewritten query.

3. The method of claim 1, wherein the rewriting step further comprises the step of rerouting the query using the slice of the cube index.

4. The method of claim 3, further comprising the step of selecting the slice from the cube index that contains columns required to evaluate any predicates in the query that are not subsumed by the summary table and reapplying the predicate to produce answers for the query.

5. The method of claim 1, further comprising the step of regrouping to produce answers for the query.

6. The method of claim 1, wherein QBS is a query block in a definition of the summary table and QBQ is a query block in the query.

7. The method of claim 6, wherein the analyzing step further comprises:

if QBQ and QBS are GROUP BYs, then QBQ must not reference columns that are not derivable from the results of QBS, and the grouping items in QBS must contain a slice that supports the grouping items in QBQ.

8. The method of claim 7, wherein an aggregate function in QBQ must be computable using a set of columns in the result of QBS as intermediate results.

9. The method of claim 8, wherein the QBS is a simple GROUP BY, and the analyzing step further comprises:

if QBQ computes a distinct aggregate function, then an argument for the distinct aggregate function must be a grouping item in QBS.

10. The method of claim 7, wherein a “

simple”

GROUP BY clause contains one or more grouping sets comprised of single expression elements in the GROUP BY clause.

11. The method of claim 10, wherein a “

non-simple”

GROUP BY clause is a GROUP BY clause with a grouping sets specification or a GROUP BY clause whose elements include those that specify a CUBE or ROLLUP operation.

12. The method of claim 11, wherein the analyzing step further comprises:

if QBS is a non-simple GROUP BY clause and QBQ is a simple GROUP BY clause, then QBS contains a slice that supports the grouping items in QBQ if the resulting grouping sets of QBS contains a grouping set whose elements are a superset of the grouping items in QBQ and any columns required in QBQ to apply predicates that are not in QBS.

13. The method of claim 11, wherein the analyzing step further comprises:

if QBS is a non-simple GROUP BY clause and QBQ is a non-simple GROUP BY clause, then QBS contains a slice that supports QBQ if the resulting grouping sets of QBS contains a grouping set whose elements are a superset of the grouping items in the QBQ and any columns required in the QBQ to apply predicates that are not in QBS.

14. The method of claim 13, wherein QBQ is computed by applying all the grouping operations of QBQ applied to the minimum slice of QBS that contains the elements in the GROUP BY clause of QBQ plus any predicates that QBQ contains and QBS does not.

15. The method of claim 13, wherein the analyzing step further comprises:

if QBQ and QBS are defined with exactly the same grouping sets with exactly the same input, then QBQ results are computed as a simple select of the corresponding columns from QBS that are in the output of QBQ.

16. The method of claim 13, wherein the analyzing step further comprises:

if QBQ is a simple GROUP BY clause and QBQ does not have any predicates that QBS does not have or the predicates only involve columns in the GROUP BY elements of QBQ, then QBQ is computed from QBS by constructing a slice from QBS of the elements in the simple GROUP BY clause of QBQ.

17. The method of claim 13, wherein the analyzing step further comprises:

if QBQ is a simple GROUP BY clause with elements <

E1, E2, . . . , EN>

that contains predicates P1, . . . , PK that QBS does not have, and <

F1, F2, . . . , FM>

are the columns different from <

E1, . . . , EN>

required to compute those predicates, then QBQ is computed from QBS by constructing a slice from QBS for elements <

E1, . . . , EN, F1, . . . , FM>

, applying the predicates P1, PK to the results of this slice, and then applying the GROUP BY clause of QBQ with appropriately substituted re-aggregations.

18. The method of claim 13, wherein the analyzing step further comprises:

if QBQ is a non-simple GROUP BY clause that differs from the non-simple GROUP BY clause of QBS only in that the rollups contained in the GROUP BY clause of QBQ are order sensitive prefixes of their corresponding rollups in QBS, and QBQ does not contain predicates that are not also contained in QBS, then QBQ is computed from QBS by constructing a slice of QBS that contains only collapsed clauses for the elements in the rollups of QBS that are not in the prefixes of the corresponding rollups in QBQ.

19. The method of claim 13, wherein the analyzing step further comprises:

if QBQ is a non-simple GROUP BY clause with elements <

E1, E2, . . . , EN>

that contains predicates P1, . . . , PK that QBS does not have, and <

F1, F2, . . . , FM>

are the columns different from <

E1, . . . , EN>

required to compute those predicates and no other optimizations apply, then QBQ is computed from QBS by constructing a slice from QBS for elements <

E1, . . . , EN, F1, . . . , FM>

, applying the predicates P1, . . . , PK to the results of this slice, and then applying the GROUP BY clause of QBQ with appropriately substituted re-aggregations.

20. A computer-implemented apparatus for optimizing a query, comprising:

(a) a computer system;

(b) means, performed by the computer system, for analyzing a query using subsumption tests between the query and at least one summary table that comprises a cube index to determine whether an expression in the query can be subsumed by the summary table, wherein the summary table stores at least one materialized view involving at least one GROUP BY operation that computes at least one of the following;

(1) a cube, (2) a rollup, (3) a grouping set; and

(4) a concatenation of cubes, rollups, grouping sets and one or more grouping items; and

(b) means, performed by the computer system, for rewriting the query using a slice of the cube index, when the expression in the query can be subsumed in the summary table.

21. The apparatus of claim 20, further comprising means for executing the rewritten query.

22. The apparatus of claim 20, wherein the means for rewriting further comprises means for rerouting the query using the slice of the cube index.

23. The apparatus of claim 22, further comprising means for selecting the slice from the cube index that contains columns required to evaluate any predicates in the query that are not subsumed by the summary table and for reapplying the predicate to produce answers for the query.

24. The apparatus of claim 20, further comprising means for regrouping to produce answers for the query.

25. The apparatus of claim 20, wherein QBS is a query block in a definition of the summary table and QBQ is a query block in the query.

26. The apparatus of claim 25, wherein the means for analyzing further comprises:

if QBQ and QBS are GROUP BYs, then QBQ must not reference columns that are not derivable from the results of QBS, and the grouping items in QBS must contain a slice that supports the grouping items in QBQ.

27. The apparatus of claim 26, wherein an aggregate function in QBQ must be computable using a set of columns in the result of QBS as intermediate results.

28. The apparatus of claim 27, wherein the QBS is a simple GROUP BY, and the means for analyzing further comprises:

if QBQ computes a distinct aggregate function, then an argument for the distinct aggregate function must be a grouping item in QBS.

29. The apparatus of claim 26, wherein a “

simple”

GROUP BY clause contains one or more grouping sets comprised of single expression elements in the GROUP BY clause.

30. The apparatus of claim 29, wherein a “

non-simple”

GROUP BY clause is a GROUP BY clause with a grouping sets specification or a GROUP BY clause whose elements include those that specify a CUBE or ROLLUP operation.

31. The apparatus of claim 30, wherein the means for analyzing further comprises:

if QBS is a non-simple GROUP BY clause and QBQ is a simple GROUP BY clause, then QBS contains a slice that supports the grouping items in QBQ if the resulting grouping sets of QBS contains a grouping set whose elements are a superset of the grouping items in QBQ and any columns required in QBQ to apply predicates that are not in QBS.

32. The apparatus of claim 31, wherein the means for analyzing further comprises:

if QBS is a non-simple GROUP BY clause and QBQ is a non-simple GROUP BY clause, then QBS contains a slice that supports QBQ if the resulting grouping sets of QBS contains a grouping set whose elements are a superset of the grouping items in the QBQ and any columns required in the QBQ to apply predicates that are not in QBS.

33. The apparatus of claim 32, wherein QBQ is computed by applying all the grouping operations of QBQ applied to the minimum slice of QBS that contains the elements in the GROUP BY clause of QBQ plus any predicates that QBQ contains and QBS does not.

34. The apparatus of claim 32, wherein the means for analyzing further comprises:

if QBQ and QBS are defined with exactly the same grouping sets with exactly the same input, then QBQ results are computed as a simple select of the corresponding columns from QBS that are in the output of QBQ.

35. The apparatus of claim 32, wherein the means for analyzing further comprises:

if QBQ is a simple GROUP BY clause and QBQ does not have any predicates that QBS does not have or the predicates only involve columns in the GROUP BY elements of QBQ, then QBQ is computed from QBS by constructing a slice from QBS of the elements in the simple GROUP BY clause of QBQ.

36. The apparatus of claim 32, wherein the means for analyzing further comprises:

if QBQ is a simple GROUP BY clause with elements <

E1, E2, . . . , EN>

that contains predicates P1, . . . , PK that QBS does not have, and <

F1, F2, . . . , FM>

are the columns different from <

E1, . . . , EN>

required to compute those predicates, then QBQ is computed from QBS by constructing a slice from QBS for elements <

E1, . . . , EN, F1, . . . , FM>

, applying the predicates P1, . . . , PK to the results of this slice, and then applying the GROUP BY clause of QBQ with appropriately substituted re-aggregations.

37. The apparatus of claim 32, wherein the means for analyzing further comprises:

if QBQ is a non-simple GROUP BY clause that differs from the non-simple GROUP BY clause of QBS only in that the rollups contained in the GROUP BY clause of QBQ are order sensitive prefixes of their corresponding rollups in QBS, and QBQ does not contain predicates that are not also contained in QBS, then QBQ is computed from QBS by constructing a slice of QBS that contains only collapsed clauses for the elements in the rollups of QBS that are not in the prefixes of the corresponding rollups in QBQ.

38. The apparatus of claim 32, wherein the means for analyzing further comprises:

if QBQ is a non-simple GROUP BY clause with elements <

E1, E2, . . . , EN>

that contains predicates P1, . . . , PK that QBS does not have, and <

F1, F2, . . . , FM>

are the columns different from <

E1, . . . , EN>

required to compute those predicates and no other optimizations apply, then QBQ is computed from QBS by constructing a slice from QBS for elements <

E1, . . . , EN, F1, . . . , FM>

, applying the predicates P1, . . . , PK to the results of this slice, and then applying the GROUP BY clause of QBQ with appropriately substituted re-aggregations.

39. An article of manufacture embodying logic for performing method steps for optimizing a query, the query being performed by a computer system to retrieve data from a database stored in a data storage device coupled to the computer system, the method comprising the steps of:

(a) analyzing a query in the computer system using subsumption tests between the query and at least one summary table that comprises a cube index to determine whether an expression in the query can be subsumed by the summary table, wherein the summary table stores at least one materialized view involving at least one GROUP BY operation that computes at least one of the following;

(1) a cube, (2) a rollup, (3) a grouping set; and

(4) a concatenation of cubes, rollups, grouping sets and one or more grouping items; and

(b) when the expression in the query can be subsumed in the summary table, rewriting the query using a slice of the cube index.

40. The method of claim 39, further comprising the step of executing the rewritten query.

41. The method of claim 39, wherein the rewriting step further comprises the step of rerouting the query using the slice of the cube index.

42. The method of claim 41, further comprising the step of selecting the slice from the cube index that contains columns required to evaluate any predicates in the query that are not subsumed by the summary table and reapplying the predicate to produce answers for the query.

43. The method of claim 39, further comprising the step of regrouping to produce answers for the query.

44. The method of claim 39, wherein QBS is a query block in a definition of the summary table and QBQ is a query block in the query.

45. The method of claim 44, wherein the analyzing step further comprises:

if QBQ and QBS are GROUP BYs, then QBQ must not reference columns that are not derivable from the results of QBS, and the grouping items in QBS must contain a slice that supports the grouping items in QBQ.

46. The method of claim 45, wherein an aggregate function in QBQ must be computable using a set of columns in the result of QBS as intermediate results.

47. The method of claim 46, wherein the QBS is a simple GROUP BY, and the analyzing step further comprises:

if QBQ computes a distinct aggregate function, then an argument for the distinct aggregate function must be a grouping item in QBS.

48. The method of claim 45, wherein a “

simple”

GROUP BY clause contains one or more grouping sets comprised of single expression elements in the GROUP BY clause.

49. The method of claim 48, wherein a “

non-simple”

GROUP BY clause is a GROUP BY clause with a grouping sets specification or a GROUP BY clause whose elements include those that specify a CUBE or ROLLUP operation.

50. The method of claim 49, wherein the analyzing step further comprises:

if QBS is a non-simple GROUP BY clause and QBQ is a simple GROUP BY clause, then QBS contains a slice that supports the grouping items in QBQ if the resulting grouping sets of QBS contains a grouping set whose elements are a superset of the grouping items in QBQ and any columns required in QBQ to apply predicates that are not in QBS.

51. The method of claim 49, wherein the analyzing step further comprises:

if QBS is a non-simple GROUP BY clause and QBQ is a non-simple GROUP BY clause, then QBS contains a slice that supports QBQ if the resulting grouping sets of QBS contains a grouping set whose elements are a superset of the grouping items in the QBQ and any columns required in the QBQ to apply predicates that are not in QBS.

52. The method of claim 51, wherein QBQ is computed by applying all the grouping operations of QBQ applied to the minimum slice of QBS that contains the elements in the GROUP BY clause of QBQ plus any predicates that QBQ contains and QBS does not.

53. The method of claim 51, wherein the analyzing step further comprises:

if QBQ and QBS are defined with exactly the same grouping sets with exactly the same input, then QBQ results are computed as a simple select of the corresponding columns from QBS that are in the output of QBQ.

54. The method of claim 51, wherein the analyzing step further comprises:

if QBQ is a simple GROUP BY clause and QBQ does not have any predicates that QBS does not have or the predicates only involve columns in the GROUP BY elements of QBQ, then QBQ is computed from QBS by constructing a slice from QBS of the elements in the simple GROUP BY clause of QBQ.

55. The method of claim 51, wherein the analyzing step further comprises:

if QBQ is a simple GROUP BY clause with elements <

E1, E2, . . . , EN>

that contains predicates P1, . . . , PK that QBS does not have, and <

F1, F2, . . . , FM>

are the columns different from <

E1, . . . , EN>

required to compute those predicates, then QBQ is computed from QBS by constructing a slice from QBS for elements <

E1, . . . , EN, F1, . . . , FM>

, applying the predicates P1, . . . , PK to the results of this slice, and then applying the GROUP BY clause of QBQ with appropriately substituted re-aggregations.

56. The method of claim 51, wherein the analyzing step further comprises:

if QBQ is a non-simple GROUP BY clause that differs from the non-simple GROUP BY clause of QBS only in that the rollups contained in the GROUP BY clause of QBQ are order sensitive prefixes of their corresponding rollups in QBS, and QBQ does not contain predicates that are not also contained in QBS, then QBQ is computed from QBS by constructing a slice of QBS that contains only collapsed clauses for the elements in the rollups of QBS that are not in the prefixes of the corresponding rollups in QBQ.

57. The method of claim 51, wherein the analyzing step further comprises:

if QBQ is a non-simple GROUP BY clause with elements <

E1, E2, . . . , EN>

that contains predicates P1, . . . , PK that QBS does not have, and <

F1, F2, . . . , FM>

are the columns different from <

E1, . . . , EN>

required to compute those predicates and no other optimizations apply, then QBQ is computed from QBS by constructing a slice from QBS for elements <

E1, . . . , EN, F1, . . . , FM>

, applying the predicates P1, . . . , PK to the results of this slice, and then applying the GROUP BY clause of QBQ with appropriately substituted re-aggregations.