Method and apparatus for re-evaluating execution strategy for a database query

• US 8,046,354 B2
• Filed: 09/30/2004
• Issued: 10/25/2011
• Est. Priority Date: 09/30/2004
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Jameson, Lee William, Day, Paul Reuben, Muras, Brian Robert, Mittelstadt, Roger Alan
• Primary Examiner(s): Mofiz; Apu
• Assistant Examiner(s): Le; Hung
• Application Number:
  US10/955,737
• Publication Number:
  US 20060074874A1
• Time in Patent Office: 2,581 Days
• Field of Search: None
• US Class Current: 707/720
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 16/24547 Optimisations to support specific applications; Extensibility of optimisers
• CPC Class Codes: G06F 16/24549 Run-time optimisation

Abstract

A query facility for database queries saves and re-uses query execution strategies, and automatically detects that a strategy should be re-optimized as a result of changes to an indexed variable value. Preferably, the number of records evaluated and selected by the index value condition is dynamically monitored during execution, and an alternative query strategy is initiated when this number appears to be out of proportion to expectations. In an exemplary embodiment, an indexed search strategy is changed to a table scan strategy (or vice versa) as a result of a change to the number of records eliminated by the indexed value, although other examples are possible. Preferably, the query engine initiates an alternative search strategy and concurrently continues to execute the original search strategy as separate threads. Search results are obtained from whichever thread completes first.

Claims

1. A method for executing a database query in a computer system, comprising the steps of:

invoking a database query, said database query containing at least one imported variable, said step of invoking a database query comprising specifying a respective value of each said at least one imported variable;

automatically selecting a primary query execution strategy for executing the database query from among a plurality of different query execution strategies for executing the database query, each said query execution strategy being generated by an automated query optimizer and optimized for a different respective set of values of said at least one imported variable;

executing said database query according to said primary execution strategy;

automatically monitoring execution of said primary execution strategy while performing said execution step to detect a condition from the set of conditions consisting of;

(a) a number of records evaluated using said primary execution strategy exceeds a high water mark, said high water mark being a dynamically maintained value indicating the highest number of records evaluated during any of previous successful executions of said primary execution strategy, and

(b) a projected number of records to be evaluated using said primary execution strategy will be less than a low water mark, said projected number of records being projected during execution of said primary execution strategy using at least some results from execution of said primary execution strategy, said low water mark being a dynamically maintained value indicating the lowest number of records evaluated during any of previous successful executions of said primary execution strategy;

responsive to detecting a condition from said set of conditions, automatically initiating an alternate execution strategy of said plurality of query execution strategies for executing said database query; and

outputting results of executing said database query to a user.

2. The method for executing a database query of claim 1, wherein said step of automatically initiating an alternate execution strategy comprises initiating said alternate execution strategy as a separate concurrently executing thread while continuing to execute said database query according to said primary execution strategy.

3. The method for executing a database query of claim 1, wherein said primary execution strategy is an index search strategy.

4. The method for executing a database query of claim 3, wherein said step of automatically monitoring execution of said primary execution strategy comprises monitoring to detect condition (a).

5. The method for executing a database query of claim 3, wherein said alternate execution strategy is a table scan strategy.

6. The method for executing a database query of claim 3, wherein said alternate execution strategy is an index search strategy, said alternate execution strategy using an indexed field other than an indexed field used by said primary search strategy.

7. The method for executing a database query of claim 1, wherein said primary execution strategy is a table scan strategy, and said step of automatically monitoring execution of said primary execution strategy comprises monitoring to detect condition (b).

8. The method of claim 1, further comprising the step of:

if condition (a) is detected during said step of dynamically monitoring execution and it is subsequently determined that said primary execution strategy was successful, then dynamically adjusting said high water mark to a new value indicating a number of records evaluated during execution using said primary execution strategy.

9. The method of claim 1, further comprising the step of:

if condition (b) is detected during said step of dynamically monitoring execution and it is subsequently determined that said primary execution strategy was successful, then dynamically adjusting said low water mark to a new value indicating a number of records evaluated during execution using said primary execution strategy.

18. The method of claim 1, further comprising the step of generating and saving a plurality of said different query execution strategies for executing said database query with said automated query optimizer, each saved query execution strategy including respective condition data indicating at least one condition for which the respective query is optimized.

19. The method of claim 18, wherein each said saved query execution strategy further includes a respective dynamically maintained high water mark, each respective high water mark indicating the highest number of records evaluated during any of previous successful executions of the query execution strategy with which it is associated.

10. A computer program product for database query optimization comprising:

a plurality of computer executable instructions recorded on tangible computer-readable media, wherein said instructions, when executed by at least one computer system, cause the at least one computer system to perform the steps of;

receiving an invocation of a database query;

assigning a primary query execution strategy to the database query, wherein said primary execution strategy is a table scan strategy;

executing said database query according to said primary execution strategy;

monitoring execution of said primary execution strategy while performing said execution step to detect a condition indicating that said primary execution strategy is sub-optimal, said monitoring execution step including using a non-empty subset of records of a database table already scanned during execution of said database query according to said primary execution strategy to project, at least once during execution of said database query according to said primary execution strategy, whether a number of records selected by a logical condition having an indexed record field within said query will be less than a pre-determined value;

responsive to detecting a condition indicating that said primary execution strategy is sub-optimal, initiating an alternate execution strategy for executing said database query.

11. The computer program product of claim 10, wherein said step of initiating an alternate execution strategy comprises initiating said alternate execution strategy as a separate concurrently executing thread while continuing to execute said database query according to said primary execution strategy.

12. The computer program product of claim 10, wherein said alternate execution strategy is an index search strategy.

13. The computer program product of claim 10, wherein said pre-determined value is a dynamically maintained low water mark indicating a minimum number of records evaluated during any of previous successful executions of said primary execution strategy.

14. The computer program product of claim 10, wherein said step of monitoring execution of said primary execution strategy comprises maintaining separate counts of a number of records evaluated for a first condition of said query using said primary execution strategy and a number of records satisfying said first condition of said query using said primary execution strategy.

15. The computer program product of claim 14, wherein said projecting a number of records selected by a logical condition having an indexed record field within said query comprises computing a ratio of said number of records evaluated for said first condition of said query using said primary execution strategy to said number of records satisfying said first condition of said query using said primary execution strategy.

16. A computer system, comprising:

at least one processor;

a data storage for storing a database; and

a database management facility embodied as a plurality of instructions executable on said at least one processor, said database management facility including a query engine which executes logical queries against said database and a query optimizer for generating execution strategies for execution logical queries against said database, wherein for a first said logical query containing at least one imported variable, said query optimizer generates a plurality of different query execution strategies, each said query execution strategy being optimized for a different respective set of values of said at least one imported variable;

wherein said database management facility automatically selects a primary execution strategy from among said plurality of different query execution strategies generated by said query optimizer for executing an invoked database query, monitors execution of said primary execution strategy to detect a condition indicating that said primary execution strategy is sub-optimal, and initiates an alternate execution strategy from among said plurality of different query execution strategies generated by said query optimizer responsive to detecting a condition indicating that said primary execution strategy is sub-optimal

wherein said condition indicating that said primary execution strategy is sub-optimal comprises a condition from the set of conditions consisting of;

(a) a number of records evaluated using said primary execution strategy exceeds a high water mark, said high water mark being a dynamically maintained value indicating the highest number of records evaluated during any of previous successful executions of said primary execution strategy, and

(b) a projected number of records to be evaluated using said primary execution strategy will be less than a low water mark, said projected number of records being projected during execution of said primary execution strategy using at least some results from execution of said primary execution strategy, said low water mark being a dynamically maintained value indicating the lowest number of records evaluated during any of previous successful executions of said primary execution strategy.

17. The computer system of claim 16, wherein a respective high water mark is associated with each said query execution strategy generated by said automated query optimizer, each respective high water mark indicating the highest number of records evaluated during any of previous successful executions of the query execution strategy with which it is associated.