Deriving uniqueness for indices on summary tables

• US 6,513,034 B1
• Filed: 12/21/1999
• Issued: 01/28/2003
• Est. Priority Date: 04/16/1999
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Simmen, David E., Leung, Ting Yu
• Primary Examiner(s): RONES, CHARLES
• Application Number:
  US09/469,711
• Time in Patent Office: 1,134 Days
• Field of Search: 707/2, 707/3
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2228 Indexing 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 a query by deriving uniqueness for indices on the summary tables. The query is analyzed to determine whether a summary table can be used to answer the query or a summary table is directly referenced in the query. A determination is made whether a non-unique index of the summary table is unique based on a query definition of the summary table. If the non-unique index of the summary table is unique, then query optimization techniques can be applied.

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:

(a) determining whether a non-unique index of a summary table is unique based on a query definition of the summary table; and

(b) generating at least one query execution plan using the non-unique index of the summary table, when the non-unique index of a summary table has been determined to be unique based on a query definition of the summary table.

2. The method of claim 1, further comprising analyzing the query to determine whether the summary table can be used to answer the query, and performing the determining step (a) when the summary table can be used to answer the query.

3. The method of claim 1, further comprising analyzing the query to determine whether the summary table is directly referenced in the query, and performing the determining step (a) when the summary table is directly referenced in the query.

4. The method of claim 1, wherein the generating step (b) further comprises generating a plurality of query execution plans that use query tables and summary tables, and unique and non-unique indexes on the query tables and summary tables.

5. The method of claim 4, further comprising selecting a most efficient one of the query execution plans and then executing the selected query execution plan.

6. The method of claim 1, wherein if the summary table can be used to answer the query, then rewriting the query to use the summary table.

7. The method of claim 1, wherein the determining step comprises:

(1) for each column in the non-unique index, determining if the columns are materialized using a simple expression;

(2) invoking a generalized 1-TUPLE-CONDITION function for a set of columns materialized using a simple expression, by assuming that the columns are bound to constants; and

(3) if the 1-TUPLE-CONDITION function returns a true value for the set of columns, then the set of columns form a key in the query definition of the summary table and the non-unique index is indeed unique.

8. The method of claim 1, wherein the determining step comprises:

(1) examining the query definition of the summary table to determine whether any columns referenced in the query definition are bound;

(2) examining the query definition to determine whether a set of bound columns prohibit duplicate rows in the summary table; and

(3) examining non-index columns of the summary table to determine whether the non-index columns form a unique key in the query definition of the summary table.

9. The method of claim 8, wherein the bound column is bound to a constant value.

10. The method of claim 8, wherein the bound column is bound to a column that is already bound.

11. The method of claim 1, wherein the determining step comprises:

(1) finding a set of bindings (BINDCOL) including constants that appear in the query definition (Q) of the summary table (ST);

(2) finding a set of columns (BCOL) that are assumed bound to a single constant value as follows;

(a) a set of columns (BCOL) is initialized to empty,

(b) for each column (C) referenced in the creation of the non-unique index (I) on the summary table ST;

(i) finding the corresponding column definition using Q;

(ii) if the corresponding column definition in Q is HXP-strong, then adding this column C into the BCOL set;

(3) invoking the 1-TUPLE-CONDITION function passing as parameters;

the query Q, the BCOL set and the BINDCOL set;

(4) if the 1-TUPLE-CONDITION function returns a “

true”

value indicating that the 1-tuple condition exists, then the index I is unique; and

(5) if the 1-TUPLE-CONDITION function returns a “

false”

value indicating that the 1-tuple condition does not exist, then the index I is non-unique.

12. The method of claim 11, wherein the column definition is HXP-strong when its head expression is a simple head expression, and no two different values from the column reference in the head expression produce the same output column value.

13. The method of claim 12, wherein the simple head expression contains only a column reference.

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

(a) a computer system;

(b) means, performed by the computer system, for determining whether a non-unique index of a summary table is unique based on a query definition of the summary table; and

(c) means, performed by the computer system, for generating at least one query execution plan using the non-unique index of the summary table, when the non-unique index of a summary table has been determined to be unique based on a query definition of the summary table.

15. The apparatus of claim 14, further comprising means for analyzing the query to determine whether the summary table can be used to answer the query, and performing the means for determining (b) when the summary table can be used to answer the query.

16. The apparatus of claim 14, further comprising means for analyzing the query to determine whether the summary table is directly referenced in the query;

and performing the means for determining (b) when the summary table is directly referenced in the query.

17. The apparatus of claim 14, wherein the means for generating (c) further comprises means for generating a plurality of query execution plans that use query tables and summary tables, and unique and non-unique indexes on the query tables and summary tables.

18. The apparatus of claim 17, further comprising means for selecting a most efficient one of the query execution plans and then executing the selected query execution plan.

19. The apparatus of claim 14, wherein if the summary table can be used to answer the query, then the query is rewritten to use the summary table.

20. The apparatus of claim 14, wherein the means for determining comprises:

(1) for each column in the non-unique index, means for determining if the columns are materialized using a simple expression;

(2) means for invoking a generalized 1-TUPLE-CONDITION function for a set of columns materialized using a simple expression, by assuming that the columns are bound to constants; and

(3) if the 1-TUPLE-CONDITION function returns a true value for the set of columns, then the set of columns form a key in the query definition of the summary table and the non-unique index is indeed unique.

21. The apparatus of claim 14, wherein the means for determining comprises:

(1) means for examining the query definition of the summary table to determine whether any columns referenced in the query definition are bound;

(2) means for examining the query definition to determine whether a set of bound columns prohibit duplicate rows in the summary table; and

(3) means for examining non-index columns of the summary table to determine whether the non-index columns form a unique key in the query definition of the summary table.

22. The apparatus of claim 21, wherein the bound column is bound to a constant value.

23. The apparatus of claim 21, wherein the bound column is bound to a column that is already bound.

24. The apparatus of claim 14, wherein the means for determining comprises:

(1) means for finding a set of bindings (BINDCOL) including constants that appear in the query definition (Q) of the summary table (ST);

(2) means for finding a set of columns (BCOL) that are assumed bound to a single constant value as follows;

(a) a set of columns (BCOL) is initialized to empty,

(b) for each column (C) referenced in the creation of the non-unique index (I) on the summary table ST;

(i) means for finding the corresponding column definition using Q;

(ii) if the corresponding column definition in Q is HXP-strong, then means for adding this column C into the BCOL set;

(3) means for invoking the 1-TUPLE-CONDITION function passing as parameters;

the query Q, the BCOL set and the BINDCOL set;

(4) if the 1-TUPLE-CONDITION function returns a “

true”

value indicating that the 1-tuple condition exists, then the index I is unique; and

(5) if the 1-TUPLE-CONDITION function returns a “

false”

value indicating that the 1-tuple condition does not exist, then the index I is non-unique.

25. The apparatus of claim 24, wherein the column definition is HXP-strong when its head expression is a simple head expression, and no two different values from the column reference in the head expression produce the same output column value.

26. The apparatus of claim 25, wherein the simple head expression contains only a column reference.

27. An article of manufacture embodying logic for performing a method 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:

(a) determining whether a non-unique index of a summary table is unique based on a query definition of the summary table; and

(b) generating at least one query execution plan using the non-unique index of the summary table, when the non-unique index of a summary table has been determined to be unique based on a query definition of the summary table.

28. The method of claim 27, further comprising analyzing the query to determine whether the summary table can be used to answer the query, and performing the determining step (a) when the summary table can be used to answer the query.

29. The method of claim 27, further comprising analyzing the query to determine whether the summary table is directly referenced in the query;

and performing the determining step (a) when the summary table is directly referenced in the query.

30. The method of claim 27, wherein the generating step (b) further comprises generating a plurality of query execution plans that use query tables and summary tables, and unique and non-unique indexes on the query tables and summary tables.

31. The method of claim 30, further comprises selecting a most efficient one of the query execution plans and then executing the selected query execution plan.

32. The method of claim 27, wherein if the summary table can be used to answer the query, then rewriting the query to use the summary table.

33. The method of claim 27, wherein the determining step comprises:

(1) for each column in the non-unique index, determining if the columns are materialized using a simple expression;

(2) invoking a generalized 1-TUPLE-CONDITION function for a set of columns materialized using a simple expression, by assuming that the columns are bound to constants; and

(3) if the 1-TUPLE-CONDITION function returns a true value for the set of columns, then the set of columns form a key in the query definition of the summary table and the non-unique index is indeed unique.

34. The method of claim 27, wherein the determining step comprises:

(1) examining the query definition of the summary table to determine whether any columns referenced in the query definition are bound;

(2) examining the query definition to determine whether a set of bound columns prohibit duplicate rows in the summary table; and

(3) examining non-index columns of the summary table to determine whether the non-index columns form a unique key in the query definition of the summary table.

35. The method of claim 34, wherein the bound column is bound to a constant value.

36. The method of claim 34, wherein the bound column is bound to a column that is already bound.

37. The method of claim 27, wherein the determining step comprises:

(1) finding a set of bindings (BINDCOL) including constants that appear in the query definition (Q) of the summary table (ST);

(2) finding a set of columns (BCOL) that are assumed bound to a single constant value as follows;

(a) a set of columns (BCOL) is initialized to empty;

(b) for each column (C) referenced in the creation of the non-unique index (I)on the summary table ST;

(i) finding the corresponding column definition using Q;

(ii) if the corresponding column definition in Q is HXP-strong, then adding this column C into the BCOL set;

(3) invoking the 1-TUPLE-CONDITION function passing as parameters;

the query Q, the BCOL set and the BINDCOL set;

(4) if the 1-TUPLE-CONDITION function returns a “

true”

value indicating that the 1-tuple condition exists, then the index I is unique; and

(5) if the 1-TUPLE-CONDITION function returns a “

false”

value indicating that the 1-tuple condition does not exist, then the index I is non-unique.

38. The method of claim 37, wherein the column definition is HXP-strong when its head expression is a simple head expression, and no two different values from the column reference in the head expression produce the same output column value.

39. The method of claim 38, wherein the simple head expression contains only a column reference.