Optimizing database queries using query execution plans derived from automatic summary table determining cost based queries

• US 7,080,062 B1
• Filed: 02/11/2000
• Issued: 07/18/2006
• Est. Priority Date: 05/18/1999
• Status: Expired due to Term

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Simmen, David E., Leung, Ting Yu, Sun, Yang
• Primary Examiner(s): Channavajjala, Srirama
• Application Number:
  US09/502,820
• Time in Patent Office: 2,349 Days
• Field of Search: 707 1- 10, 707100-1041, 707200-206, 706 45- 50
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24542 Plan optimisation
• 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
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

A method, apparatus, and article of manufacture for optimizing database queries using automatic summary tables. Query execution plans derived from an automatic summary table can be used to generate results for the query if a comparison of the query requirements with an automatic summary table definition determines that the automatic summary table overlaps the query, and if an optimization process determines that using the summary table will lower the cost of the query. The optimization process involves enumerating a plurality of query execution plans for the query, wherein the query execution plans enumerated include those that access combinations of query and summary tables. Each such query execution plan is assigned a cost representing an estimation of its execution characteristics, and the least costly query execution plan is selected for the query.

Claims

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

(a) identifying one or more automatic summary tables (ASTs) that overlap the query by matching definitions of the ASTs with requirements of the query, wherein the requirements of the query satisfied by an AST are encapsulated as a set of properties;

(b) enumerating one or more alternative query execution plans (QEPs) for the query, including at least one QEP that represents one or more access paths of the identified ASTs;

(c) assigning a cost to each of the alternative QEPs; and

(d) choosing a most efficient one of the alternative QEPs based upon the assigned costs.

2. The method of claim 1, wherein the identifying step comprises comparing the requirements of the query and the definitions of at least one of the ASTs to determine whether the AST and the query overlap.

3. The method of claim 2, wherein the comparing step comprises determining the requirements of the query satisfied by the AST and characterizing the requirements as properties.

4. The method of claim 3, wherein the properties are selected from a group comprising tables referenced, columns supplied, expressions computed, predicates applied, unique keys and functional dependencies in effect, aggregation performed, and column mapping information.

5. The method of claim 1, wherein the enumerating step comprises using dynamic programming to exhaustively enumerate the alternative QEPs, thereby obtaining an optimal result for the query.

6. The method of claim 1, wherein the enumerating step comprises:

invoking at least one optimization rule R with requirements R₁, . . . , R_M to generate a set of QEPs, RQ, wherein the properties of each QEP in RQ satisfies the requirements R₁, . . . , R_M;

supplementing the QEPs in RQ with QEPs that access at least one of the ASTs and have properties A.P₁, . . . , A.P_M that overlap the requirements R₁, . . . , R_M; and

pruning the QEPS in RQ using a multi-dimensional pruning metric.

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

determining a set of processing requirements AR₁, . . . , AR_M for an AST;

invoking an access rule for the AST with the processing requirements AR₁, . . . , AR_M to obtain a set of QEPs, QA, for accessing the AST; and

adding the set of QEPs, QA, to the set of QEPs, RQ.

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

reducing the requirements R₁, . . . , R_M to requirements RR₁, . . . , RR_M by removing components of each requirement R_i already satisfied by a corresponding property A.P_i of the AST;

determining whether each of the reduced requirements RRI overlaps with the corresponding property A.P_i of the AST; and

mapping each of the reduced requirements RR₁, . . . , RR_M to processing requirements AR₁, . . . , AR_M of the AST by substituting table and column references in RR_i with corresponding table and column reference of the AST using matching information QA encapsulated as a property of the AST.

9. The method of claim 8, herein the reducing step comprises iteratively reducing the requirements R₁, . . . , R_M to reduced requirements RR₁, . . . , RR_M until no further reduction is possible.

10. The method of claim 7, wherein the invoking step comprises computing properties of at least one QEP operator O representing an access to the AST.

11. The method of claim 10, wherein the computing step comprises:

initializing each property O.P_i of the operator O with the corresponding property A.P_i of the AST;

mapping each of the processing requirements AR₁, . . . , AR_M to query requirements R1, . . . , RM by substituting table and column references in ARi with corresponding table and column reference of the query as described in the matching information QA encapsulated as a property of the AST; and

invoking a property function for the operator O with the initialized properties O.P₁, . . . , O.P_N and the processing requirements R₁, . . . , R_M.

12. The method of claim 1, wherein the enumerating step comprises:

invoking at least one optimization rule with the requirements of the query to generate a set of QEPs, wherein the properties of each QEP in the set of QEPs satisfies the requirements of the query;

supplementing the QEPs in the set of QEPs with additional QEPs that access at least one of the ASTs and have properties that overlap the requirements of the query; and

pruning the QEPs in the set.

13. The method of claim 12, wherein the supplementing step comprises:

determining a set of processing requirements for an AST;

invoking an access rule for the AST with the processing requirements of the AST to obtain the additional QEPs that access the ASTs; and

supplementing the QEPs in the set of QEPs with the additional QEPs.

14. The method of claim 13, wherein the determining step comprises:

reducing the requirements of the query by removing components of each requirement already satisfied by a corresponding property of the AST;

determining whether each of the reduced requirements of the query overlaps with the corresponding property of the AST; and

mapping each of the reduced requirements of the query to the processing requirements of the AST by substituting table and column references in the reduced requirement with corresponding table and column references of the AST using matching information encapsulated as a property of the AST.

15. The method of claim 14, wherein the reducing step comprises iteratively reducing the requirements of the query until no further reduction is possible.

16. The method of claim 13, wherein the invoking step comprises computing properties of at least one QEP operator representing an access path of the AST.

17. The method of claim 16, wherein the computing step comprises:

initializing each property of the operator with the corresponding property of the AST;

mapping each of the processing requirements of the AST to the requirements of the query by substituting table and column references in the processing requirements of the AST with corresponding table and column references of the query as described in matching information encapsulated as a property of the AST; and

invoking a property function for the operator with the initialized properties of the operator and the processing requirements of the AST.

18. A computer-implemented apparatus for optimizing a query, wherein the query is performed by the computer to retrieve data from a database stored on the computer, the apparatus comprising:

(a) a computer;

(b) logic, performed by the computer, for;

(1) identifying one or more automatic summary tables (ASTs) that overlap the query by matching definitions of the ASTs with requirements of the query, wherein the requirements of the query satisfied by an AST are encapsulated as a set of properties;

(2) enumerating one or more alternative query execution plans (QEPs) for the query, including at least one QEP that represents one or more access paths of the identified ASTs;

(3) assigning a cost to each of the alternative QEPs; and

(4) choosing a most efficient one of the alternative QEPs based upon the assigned costs.

19. The apparatus of claim 18, wherein the logic for identifying comprises logic for comparing the requirements of the query and the definitions of at least one of the ASTs to determine whether the AST and the query overlap.

20. The apparatus of claim 19, wherein the logic for comparing comprises logic for determining requirements of the query satisfied by the AST and characterizing the requirements as properties.

21. The apparatus of claim 20, wherein the properties are selected from a group comprising tables referenced, columns supplied, expressions computed, predicates applied, unique keys and functional dependencies in effect, aggregation performed, and column mapping information.

22. The apparatus of claim 18, wherein the logic for enumerating comprises logic for using dynamic programming to exhaustively enumerate the alternative QEPs, thereby obtaining an optimal result for the query.

23. The apparatus of claim 18, wherein the logic for enumerating comprises logic for:

invoking at least one optimization rule R with requirements R₁, . . . , R_M to generate a set of QEPs, RQ, wherein the properties of each QEP in RQ satisfies the requirements R₁, . . . , R_M;

supplementing the QEPs in RQ with QEPs that access at least one of the ASTs and have properties A.P₁, . . . , A.P_M that overlap the requirements R₁, . . . , R_M; and

pruning the QEPS in RQ using a multi-dimensional pruning metric.

24. The apparatus of claim 23, wherein the logic for supplementing comprises logic for:

determining a set of processing requirements AR₁, . . . , AR_M for an AST;

invoking an access rule for the AST with the processing requirements AR₁, . . . , AR_M to obtain a set of QEPs, QA, for accessing the AST; and

adding the set of QEPs, QA, to the set of QEPs, RQ.

25. The apparatus of claim 24, wherein the logic for determining comprises logic for:

reducing the requirements R₁, . . . , R_M to requirements RR₁, . . . , RR_M by removing components of each requirement R_i already satisfied by a corresponding property A.P_i of the AST;

determining whether each of the reduced requirements RRI overlaps with the corresponding property A.P_i of the AST; and

mapping each of the reduced requirements RR₁, . . . , RR_M to processing requirements AR₁, . . . , AR_M of the AST by substituting table and column references in RR_i with corresponding table and column reference of the AST using matching information QA encapsulated as a property of the AST.

26. The apparatus of claim 25, wherein the logic for reducing comprises logic for iteratively reducing the requirements R₁, . . . , R_M to reduced requirements RR₁, . . . , RR_M until no further reduction is possible.

27. The apparatus of claim 24, wherein the logic for invoking comprises logic for computing properties of at least one QEP operator O representing an access to the AST.

28. The apparatus of claim 27, wherein the logic for computing comprises logic for:

initializing each property O.PI of the operator O with the corresponding property A.P_i of the AST;

mapping each of the processing requirements AR₁, . . . , AR_M to query requirements R₁, . . . , R_M by substituting table and column references in AR_i with corresponding table and column reference of the query as described in the matching information QA encapsulated as a property of the AST; and

invoking a property function for the operator O with the initialized properties O.P₁, . . . , O.P_N and the processing requirements R₁, . . . , R_M.

29. The apparatus of claim 18, wherein the logic for enumerating comprises logic for:

invoking at least one optimization rule with the requirements of the query to generate a set of QEPs, wherein the properties of each QEP in the set of QEPs satisfies the requirements of the query;

supplementing the QEPs in the set of QEPs with additional QEPs that access at least one of the ASTs and have properties that overlap the requirements of the query; and

pruning the QEPs in the set.

30. The apparatus of claim 29, wherein the logic for supplementing comprises logic for:

determining a set of processing requirements for an AST;

invoking an access rule for AST with the processing requirements of the AST to obtain the additional QEPs that access the ASTs; and

supplementing the QEPs in the set of QEPs with the additional QEPs.

31. The apparatus of claim 30, wherein the logic for determining comprises logic for:

reducing the requirements of the query by removing components of each requirement already satisfied by a corresponding property of the AST;

determining whether each of the reduced requirements of the query overlaps with the corresponding property of the AST; and

mapping each of the reduced requirements of the query to the processing requirements of the AST by substituting table and column references in the reduced requirement with corresponding table and column references of the AST using matching information encapsulated as a property of the AST.

32. The apparatus of claim 31, wherein the logic for reducing comprises logic for iteratively reducing the requirements of the query until no further reduction is possible.

33. The apparatus of claim 30, wherein the logic for invoking comprises logic for computing properties of at least one QEP operator representing an access path of the AST.

34. The apparatus of claim 33, wherein the logic for computing comprises logic for:

initializing each property of the operator with the corresponding property of the AST;

mapping each of the processing requirements of the AST to the requirements of the query by substituting table and column references in the processing requirements of the AST with corresponding table and column references of the query as described in matching information encapsulated as a property of the AST; and

invoking a property function for the operator with the initialized properties of the operator and the processing requirements of the AST.

35. 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:

(a) identifying one or more automatic summary tables (ASTs) that the query by matching definitions of the ASTs with requirements of the query, wherein the requirements of the query satisfied by an AST are encapsulated as a set of properties;

(b) enumerating one or more alternative query execution plans (QEPS) for the query, including at least one QEP that represents one or more access of the identified ASTs;

(c) assigning a cost to each of the alternative QEPs; and

(d) choosing a most efficient one of the alternative QEPs based upon the assigned costs.

36. The method of claim 35, wherein the identifying step comprises comparing the requirements of the query and the definitions of at least one of the ASTs to determine whether the AST and the query overlap.

37. The method of claim 36, wherein the comparing step comprises determining requirements of the query satisfied by the AST and characterizing the requirements as properties.

38. The method of claim 37, wherein the properties are selected from a group comprising tables referenced, columns supplied, expressions computed, predicates applied, unique keys and functional dependencies in effect, aggregation performed, and column mapping information.

39. The method of claim 35, wherein the enumerating step comprises using dynamic programming to exhaustively enumerate the alternative QEPs, thereby obtaining an optimal result for the query.

40. The method of claim 35, wherein the enumerating step comprises:

invoking at least one optimization rule R with requirements R₁, . . . , R_M to generate a set of QEPs, RQ, wherein the properties of each QEP in RQ satisfies the requirements R₁, . . . , R_M;

supplementing the QEPs in RQ with QEPs that access at least one of the ASTs and have properties A.P₁, . . . , A.P_M that overlap the requirements R₁, . . . , R_M; and

pruning the QEPs in RQ using a multi-dimensional pruning metric.

41. The method of claim 40, wherein the supplementing step comprises:

determining a set of processing requirements AR₁, . . . , AR_M for an AST;

invoking an access rule for the AST with the processing requirements AR₁, . . . , AR_M to obtain a set of QEPs, QA, for accessing the AST; and

adding the set of QEPs, QA, to the set of QEPs, RQ.

42. The method of claim 41, wherein the determining step comprises:

reducing the requirements R₁, . . . , R_M to requirements RR₁, . . . , RR_M by removing components of each requirement R_i already satisfied by a corresponding property A.P_i of the AST;

determining whether each of the reduced requirements RR_i overlaps with the corresponding property A.P_i of the AST; and

mapping each of the reduced requirements RR₁, . . . , RR_M to processing requirements AR₁, . . . , AR_M of the AST by substituting table and column references in RR₁ with corresponding table and column reference of the AST using matching information QA encapsulated as a property of the AST.

43. The method of claim 42, wherein the reducing step comprises iteratively reducing the requirements R₁, . . . , R_M to reduced requirements RR₁, . . . , RR_M until no further reduction is possible.

44. The method of claim 41, wherein the invoking step comprises computing properties of at least one QEP operator O representing an access to the AST.

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

initializing each property O.P_i of the operator O with the corresponding property A.P_i of the AST;

mapping each of the processing requirements AR₁, . . . , AR_M to query requirements R₁, . . . , R_M by substituting table and column references in AR_i with corresponding table and column reference of the query as described in the matching information QA encapsulated as a property of the AST; and

invoking a property function for the operator O with the initialized properties O.P₁, . . . , O.P_N and the processing requirements R₁, . . . , R_M.

46. The method of claim 35, wherein the enumerating step comprises:

invoking at least one optimization rule with the requirements of the query to generate a set of QEPs, wherein the properties of each QEP in the set of QEPs in the set of QEPs satisfies the requirements of the query;

supplementing the QEPs in the set of QEPs with additional QEPs that access at least one of the ASTs and have properties that overlap the requirements of the query; and

pruning the QEPs in the set.

47. The method of claim 46, wherein the supplementing step comprises:

determining a set of processing requirements of an AST;

invoking an access rule for the AST with the processing requirements of the AST to obtain the additional QEPs that access the ASTs; and

supplementing the QEPs in the set of QEPs with the additional QEPs.

48. The method of claim 47, wherein the determining step comprises:

reducing the requirements of the query by removing components of each requirement already satisfied by a corresponding property of the AST;

determining whether each of the reduced requirements of the query overlap with the corresponding property of the AST; and

mapping each of the reduced requirements of the query to the processing requirements of the AST by substituting table and column references in the reduced requirement with corresponding table and column references of the AST using matching information encapsulated as a property of the AST.

49. The method of claim 48, wherein the reducing step comprises iteratively reducing the requirements of the query until no further reduction is possible.

50. The method of claim 47, wherein the invoking step comprises computing properties of at least one QEP operator representing an access path of AST.

51. The method of claim 50, wherein the computing step comprises:

initializing each property of the operator with the corresponding property of the AST;

mapping each of the processing requirements of the AST to the requirements of the query by substituting table and column references in the processing requirements of the AST with corresponding table and column references of the query as described in matching information encapsulated as a property of the AST; and

invoking a property function for the operator with the initialized properties of the operator and the processing requirements of the AST.

52. The method of claim 35, wherein the enumerating step comprises:

invoking at least one optimization rule having requirements to generate a set of QEPs, wherein the properties of each QEP in the set of QEPs satisfies the requirements;

supplementing the QEPs in the set of QEPs with additional QEPs that access at least one of the ASTs and have properties that overlap the requirements of the optimization rules; and

pruning the QEPs in the set using a multi-dimensional pruning metric.

53. The method of claim 52, wherein the supplementing step comprises:

determining a set of processing requirements for an AST;

invoking an access rule for the AST with the processing requirements of the query to obtain the additional QEPs that access the ASTs; and

supplementing the QEPs in the set of QEPs with the additional QEPs.

54. The method of claim 53, wherein the determining step comprises:

reducing the requirements of the query by removing components of each requirement already satisfied by a corresponding property of the AST;

determining whether each of the reduced requirements of the query overlaps with the corresponding property of the AST; and

mapping each of the reduced requirements of the query to the processing requirements of the AST by substituting table and column references in the reduced requirement with corresponding table and column reference of the AST using matching information encapsulated as a property of the AST.

55. The method of claim 54, wherein the reducing step comprises iteratively reducing the requirements of the query until no further reduction is possible.

56. The method of claim 53, wherein the invoking step comprises computing properties of at least one QEP operator representing an access to the AST.

57. The method of claim 56, wherein the computing step comprises:

initializing each property of the operator with the corresponding property of the AST;

mapping each of the processing requirements of the AST to the requirements of the query by substituting table and column references in the processing requirements of the AST with corresponding table and column references of the query as described in the matching information encapsulated as a property of the AST; and

invoking a property function for the operator with the initialized properties of the operator and the processing requirements of the AST.