Runtime query optimization for dynamically selecting from multiple plans in a query based upon runtime-evaluated performance criterion

• US 6,999,958 B2
• Filed: 06/07/2002
• Issued: 02/14/2006
• Est. Priority Date: 06/07/2002
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Kathmann, Kevin James, Carlson, David Glenn, Nash, Lawrence Kenneth
• Primary Examiner(s): Kindred, Alford W.
• Application Number:
  US10/165,025
• Publication Number:
  US 20030229639A1
• Time in Patent Office: 1,348 Days
• Field of Search: 707 1- 5, 707100-101, 707/102
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24549 Run-time optimisation
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• 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

An apparatus, program product and method perform runtime query optimization during execution of a query to select from among multiple available plans, or implementations, capable of implementing the query. The runtime query optimization utilizes a runtime-derived performance criterion to dynamically select from among multiple query implementations. A performance criterion is dynamically evaluated during execution of at least a portion of a query, and one of a plurality of query implementations defined in the query is selected based upon the dynamically-evaluated performance criterion. Once selected, execution of the query is continued using the selected query implementation.

Claims

1. A computer-implemented method of executing a database query, the method comprising:

(a) dynamically evaluating at least one performance criterion for a query during execution of at least a portion of the query;

(b) selecting one of a plurality of query implementations defined in the query based upon the dynamically-evaluated performance criterion; and

(c) continuing execution of the query using the selected query implementation;

wherein dynamically evaluating the performance criterion includes accessing a query data structure that includes the plurality of query implementations to obtain the performance criterion, and wherein continuing execution of the query includes executing the selected query implementation in the query data structure.

2. The method of claim 1, wherein the performance criterion is associated with a runtime-derived parameter.

3. The method of claim 1, wherein the performance criterion is associated with a parameter selected from a group consisting of an attribute, a record count, an environmental statistic, and combinations thereof.

4. The method of claim 1, wherein the query data structure includes a query tree having a switch node and a plurality of child nodes, the switch node configured to evaluate the performance criterion and at least one of the child nodes configured to implement at least a portion of one of the plurality of query implementations.

5. The method of claim 4, wherein the query tree includes a plurality of binary switch nodes, each binary switch node including a performance criterion, wherein each binary switch node includes a left subtree that implements one of the plurality of query implementations that matches the performance criterion.

6. The method of claim 5, wherein each binary switch node other than a last binary switch node references as its right child another of the binary switch nodes, and wherein the last binary switch node includes a right subtree that implements a default query implementation.

7. The method of claim 4, wherein dynamically evaluating the performance criterion includes executing an attribute operation list associated with the switch node.

8. The method of claim 1, wherein dynamically evaluating the performance criterion is performed during absolute positioning.

9. An apparatus, comprising:

(a) a memory within which is resident at least a portion of a database; and

(b) program code configured to execute a database query by dynamically evaluating at least one performance criterion for the query during execution of at least a portion of the query, selecting one of a plurality of query implementations defined in the query based upon the dynamically-evaluated performance criterion, continuing execution of the query using the selected query implementation;

wherein the program code is configured to dynamically evaluate the performance criterion by accessing a query data structure that includes the plurality of query implementations to obtain the performance criterion, and to continue execution of the query by executing the selected query implementation in the query data structure.

10. The apparatus of claim 9, wherein the performance criterion is associated with a runtime-derived parameter.

11. The apparatus of claim 9, wherein the performance criterion is associated with a parameter selected from a group consisting of an attribute, a record count, an environmental statistic, and combinations thereof.

12. The apparatus of claim 9, wherein the query data structure includes a query tree having a switch node and a plurality of child nodes, the switch node configured to evaluate the performance criterion and at least one of the child nodes configured to implement at least a portion of one of the plurality of query implementations.

13. The apparatus of claim 12, wherein the query tree includes a plurality of binary switch nodes, each binary switch node including a performance criterion, wherein each binary switch node includes a left subtree that implements one of the plurality of query implementations that matches the performance criterion.

14. The apparatus of claim 13, wherein each binary switch node other than a last binary switch node references as its right child another of the binary switch nodes, and wherein the last binary switch node includes a right subtree that implements a default query implementation.

15. The apparatus of claim 12, wherein the program code is configured to dynamically evaluate the performance criterion by executing an attribute operation list associated with the switch node.

16. The apparatus of claim 9, wherein the program code is configured to dynamically evaluate the performance criterion during absolute positioning.

17. A program product, comprising:

(a) program code configured to execute a database query by dynamically evaluating at least one performance criterion for the query during execution of at least a portion of the query, selecting one of a plurality of query implementations defined in the query based upon the dynamically-evaluated performance criterion, continuing execution of the query using the selected query implementation; and

(b) a signal bearing medium bearing the program code;

wherein the program code is configured to dynamically evaluate the performance criterion by accessing a query data structure that includes the plurality of query implementations to obtain the performance criterion, and to continue execution of the query by executing the selected query implementation in the query data structure.

18. The program product of claim 17, wherein the signal bearing medium includes at least one of a transmission medium and a recordable medium.

19. A computer-implemented method of generating a query data structure, the method comprising:

(a) identifying a plurality of implementations capable of implementing at least a portion of a query; and

(b) building a query data structure for use in implementing the query, the query data structure including the plurality of implementations and at least one performance criterion for use in selecting one of the plurality of implementations to execute during execution of the query;

wherein building the query data structure includes building a query object, the query object including a query tree having a switch node and a plurality of child nodes, the switch node configured to evaluate the performance criterion and at least one of the child nodes configured to implement at least a portion of one of the plurality of implementations.

20. The method of claim 19, wherein identifying the plurality of implementations and building the query data structure are performed during query optimization.

21. The method of claim 19, further comprising sorting the plurality of implementations to order the plurality of implementations from best to worst.

22. The method of claim 19, wherein building the query data structure includes associating a performance criterion with each of at least a subset of the plurality of implementations.

23. The method of claim 22, wherein associating the performance criterion with each of the subset of the plurality of implementations includes associating a performance criterion with every implementation except for a default implementation.