Self-adjusting database-query optimizer

• US 20060136396A1
• Filed: 11/17/2005
• Published: 06/22/2006
• Est. Priority Date: 12/22/2004
• Status: Active Grant

• Current Assignee: Teradata US, Inc. (Teradata Corporation)
• Original Assignee: NCR Corporation (NCR Voyix Corporation)
• Inventors: Brobst, Stephen
• Granted Patent: US 9,886,492 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 16/24549 Run-time optimisation
• CPC Class Codes: G06F 16/284 Relational databases

Abstract

A database-management system (DBMS) initiates execution of an incoming database query according to an initial query-execution plan that identifies an expected path for execution. Then, at some point after execution of the query has begun, the DBMS concludes that execution has not proceeded along the expected path and, in response, chooses an alternative query-execution plan for continued execution of the query.

Claims

1. A computer-implemented method for use in executing a query in a database system, the method comprising:

initiating execution of the query according to an initial query-execution plan that identifies an expected path for execution of the query; and

at some point after execution of the query has begun;

concluding that execution of the query has not proceeded along the expected path; and

in response, choosing an alternative query-execution plan for continued execution of the query.

2. The method of claim 1, where concluding that execution of the query has not proceeded along the expected path includes concluding that an actual result obtained at an intermediate checkpoint in the initial query-execution plan does not match an expected result.

3. The method of claim 2, where concluding that the actual result does not match the expected result includes concluding that the actual result differs from the expected result by more than an amount equal to a predefined margin-of-error.

4. The method of claim 2, where concluding that the actual result does not match the expected result includes concluding that the actual result differs from the expected result by more than an amount equal to one of at least two predefined margins-of-error.

5. The method of claim 4, where choosing an alternative query-execution plan includes choosing one of at least two alternative query-execution plans, where each of the alternative query-execution plans corresponds to one of the predefined margins-of-error.

6. The method of claim 2, where choosing an alternative query-execution plan includes choosing a plan that differs from the initial query-execution plan only from a point that occurs after the intermediate checkpoint in the initial query-execution plan.

7. The method of claim 2, where choosing an alternative query-execution plan includes choosing a plan that differs from the initial query-execution plan from a point that occurs before the intermediate checkpoint in the initial query-execution plan.

8. The method of claim 2, where choosing an alternative query-execution plan includes abandoning the initial query-execution plan altogether and choosing a plan that begins execution of the query anew.

9. The method of claim 2, where concluding that an actual result does not match an expected result includes concluding that an actual row count for a database table does not match an expected row count.

10. The method of claim 2, further comprising:

concluding that an actual result obtained at a second intermediate checkpoint does not match an expected result for the second intermediate checkpoint; and

choosing another alternative query-execution plan for continued execution of the query.

11. The method of claim 1, where concluding that execution of the query has not proceeded along the expected path includes concluding that database-demographics information gathered during execution of the query does not match expected database-demographics information.

12. A computer-implemented method for use in executing a query in a database system, the method comprising:

initiating execution of the query according to an initial query-execution plan; and

at some point after execution of the query has begun;

concluding that an actual result obtained at a first intermediate checkpoint in the initial query-execution plan matches an expected result for the first intermediate checkpoint;

concluding that an actual result for a second intermediate checkpoint in the initial query-execution plan does not match an expected result for the second intermediate checkpoint; and

in response, choosing an alternative query-execution plan for continued execution of the query.

13. The method of claim 12, where choosing an alternative query-execution plan includes choosing a plan for continued execution of the query from a point that occurs after the first intermediate checkpoint and before the second intermediate checkpoint.

14. The method of claim 12, where choosing an alternative query-execution plan includes choosing a plan for continued execution of the query from a point that occurs after both the first and second intermediate checkpoints.

15. The method of claim 12, where choosing an alternative query-execution plan includes abandoning the initial query-execution plan altogether and choosing a plan that begins execution of the query anew.

16. A computer program, stored on a tangible storage medium, for use in executing a query in a database system, the program comprising computer-readable instructions that, when executed by a computer, cause the computer to:

initiate execution of the query according to an initial query-execution plan that identifies an expected path for execution of the query; and

at some point after execution of the query has begun;

conclude that execution of the query has not proceeded along the expected path; and

in response, choose an alternative query-execution plan for continued execution of the query.

17. The program of claim 16, where, in concluding that execution of the query has not proceeded along the expected path, the computer concludes that an actual result obtained at an intermediate checkpoint in the initial query-execution plan does not match an expected result.

18. The program of claim 17, where, in concluding that the actual result does not match the expected result, the computer concludes that the actual result differs from the expected result by more than an amount equal to a predefined margin-of-error.

19. The program of claim 17, where, in concluding that the actual result does not match the expected result, the computer concludes that the actual result differs from the expected result by more than an amount equal to one of at least two predefined margins-of-error.

20. The program of claim 19, where, in choosing an alternative query-execution plan, the computer chooses one of at least two alternative query-execution plans, where each of the alternative query-execution plans corresponds to one of the predefined margins-of-error.

21. The program of claim 17, where, in choosing an alternative query-execution plan, the computer chooses a plan that differs from the initial query-execution plan only from a point that occurs after the intermediate checkpoint in the initial query-execution plan.

22. The program of claim 17, where, in choosing an alternative query-execution plan, the computer chooses a plan that differs from the initial query-execution plan from a point that occurs before the intermediate checkpoint in the initial query-execution plan.

23. The program of claim 17, where, in choosing an alternative query-execution plan, the computer abandons the initial query-execution plan altogether and chooses a plan that begins execution of the query anew.

24. The program of claim 17, where, in concluding that an actual result does not match an expected result, the computer concludes that an actual row count for a database table does not match an expected row count.

25. The program of claim 17, where the program also causes the computer to:

conclude that an actual result obtained at a second intermediate checkpoint does not match an expected result for the second intermediate checkpoint; and

choose another alternative query-execution plan for continued execution of the query.

26. The program of claim 16, where, in concluding that execution of the query has not proceeded along the expected path, the computer concludes that database-demographics information gathered during execution of the query does not match expected database-demographics information.

27. A signal propagated over a physical medium, the signal carrying computer-readable instructions that, when executed by a computer, cause the computer to:

receive an initial plan for execution of the query that includes an initial cost estimate indicating how one or more database resources are expected to be used in carrying out the initial plan;

start execution of the initial plan; and

at an intermediate checkpoint after execution of the initial plan has started;

receive information about an actual result obtained during execution of the initial plan;

use the actual result to calculate a revised cost estimate indicating how the one or more database resources are expected to be used in carrying out the initial plan from the intermediate checkpoint;

compare the revised cost estimate to the initial cost estimate;

conclude that the revised cost estimate lies beyond a predetermined margin-of-error around the initial cost estimate; and

start execution of an alternative plan for execution of the query.