SQL execution plan verification

• US 8,700,608 B2
• Filed: 08/08/2008
• Issued: 04/15/2014
• Est. Priority Date: 10/17/2007
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Belknap, Peter, Dageville, Benoit, Das, Dinesh, Yagoub, Khaled, Zait, Mohamed, Ziauddin, Mohamed
• Primary Examiner(s): Chen, Susan
• Application Number:
  US12/188,683
• Publication Number:
  US 20090106219A1
• Time in Patent Office: 2,076 Days
• Field of Search: None
• US Class Current: 707/719
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 16/24545 Selectivity estimation or determination

Abstract

Approaches, techniques, and mechanisms are disclosed for ensuring that a database command is executed according to a query plan that has been verified to be actually optimal. Except in rare circumstances, a database server does not execute a query plan unless it is first verified by the database server. The database server receives a request to execute a database command. The database server determines an unverified plan is the best plan for satisfying the request. Rather than risk the unknown behavior of an unverified plan, the database server instead satisfies the request according to a verified plan. Subsequently—for example as part of a scheduled job—the database server executes the unverified plan to determine performance statistics. Based at least on the performance statistics, the database server determines whether or not to verify the unverified plan. Techniques for concurrent and optimistic verifications are also disclosed.

Claims

1. A method comprising:

maintaining, at a database server, plan verification data that identifies one or more query execution plans that have been designated as acceptable for use by the database server to execute a database commands, the database command being a query statement that instructs the database server to perform one or more operations on data stored in a database;

receiving, at the database server, a first request to execute a database command;

at the database server, identifying a plurality of alternative query execution plans for executing the database command in response to the first request, the plurality of alternative query execution plans including at least a first query execution plan and a second query execution plan that is different than the first query execution plan;

the database server selecting, from the plurality of alternative query execution plans identified by the database server, a query execution plan to execute the database command in response to the first request, wherein the database server selects the second query execution plan based at least in part on determining;

a) that the plan verification data indicates that the second query execution plan has been designated as acceptable for executing the database command, and b) that the plan verification data does not yet indicate that the first query execution plan has been designated as acceptable for executing the database command;

subsequent to responding to the first request, the database server testing actual performance of the first query execution plan by executing the first query execution plan to determine actual performance statistics for the first query execution plan;

based at least on the determined actual performance statistics, the database server determining to update the plan verification data to designate the first query execution plan as acceptable for executing the database command;

subsequent to updating the plan verification data to indicate that the first query execution plan has been verified, the database server receiving a second request to execute the same database command;

at the database server, identifying the plurality of alternative query execution plans for executing the database command in response to the second request; and

based at least in part on determining that the updated verification data indicates that the first query execution plan has been verified, the database server selecting the first query execution plan to execute the database command in response to the second request;

wherein the method is performed by one or more computing devices.

2. The method of claim 1, wherein selecting the query execution plan to execute the database command in response to the first request comprises:

generating the plurality of alternative query execution plans;

estimating, for each particular query execution plan in the plurality of alternative query execution plans, predicted costs for responding to the first request by executing the particular execution plan; and

wherein the predicted costs for the first query execution plan are lower than for any other query execution plan in the plurality of alternative query execution plans.

3. The method of claim 2, wherein selecting the first query execution plan to execute the database command in response to the second request comprises:

generating the plurality of alternative query execution plans for responding to the second request to execute the database command;

estimating, for each particular query execution plan in the plurality of alternative query execution plans, predicted costs for responding to the second request according to the particular query execution plan; and

based on the predicted costs for each particular query execution plan in the plurality of alternative query execution plans, selecting the first query execution plan from the plurality of alternative query execution plans because the predicted costs for the first query execution plan are lower than predicted costs for any other query execution plan in the plurality of alternative query execution plans.

4. The method of claim 1, wherein selecting the second query execution plan comprises:

estimating, for each particular query execution plan in the one or more query execution plans that have been designated as acceptable, predicted costs for responding to the first request according to the particular query execution plan; and

selecting the second query execution plan because the predicted costs for the second query execution plan are lower than the predicted costs for any other query execution plan that has been designated as acceptable.

5. The method of claim 4, wherein predicted costs for the second query execution plan are higher than predicted costs for the first query execution plan.

6. The method of claim 1, wherein executing the first query execution plan to determine the actual performance statistics for the first query execution plan occurs in response to a scheduled job occurring at a particular interval.

7. The method of claim 1, wherein executing the first query execution plan to determine the actual performance statistics for the first query execution plan occurs in response to a command received from a user.

8. The method of claim 1, wherein determining to designate the first query execution plan as acceptable for executing the database command is further based on comparing the determined actual performance statistics for the first query execution plan to actual performance statistics for the one or more query execution plans that were already designated as acceptable for executing the database command.

9. The method of claim 8, further comprising:

obtaining the actual performance statistics for the one or more query execution plans that were already designated as acceptable for executing the database command by executing the one or more query execution plans in a particular execution context;

wherein executing the first query execution plan to determine the actual performance statistics for the first query execution plan also occurs in the particular execution context.

10. The method of claim 1, further comprising:

selecting a particular verified query execution plan from the one or more query execution plans that have been designated as acceptable, the particular verified query execution plan having a lower predicted cost in a particular execution context than any other query execution plan that has been designated as acceptable;

obtaining actual performance statistics for the particular verified query execution plan by executing the particular verified query execution plan in the particular execution context;

executing the first query execution plan to determine the actual performance statistics for the first query execution plan in the particular execution context; and

determining to designate the first query execution plan as acceptable for executing the database command further based on comparing the determined actual performance statistics for the first query execution plan to the actual performance statistics for the particular verified query execution plan.

11. The method of claim 1, wherein determining to designate the first query execution plan as acceptable for executing the database command is further based on comparing the determined actual performance statistics with predicted costs for executing the first query execution plan.

12. The method of claim 1, wherein:

executing the first query execution plan to determine the actual performance statistics for the first query execution plan occurs in a first execution context;

further comprising, subsequent to responding to the first request, but prior to executing the first query execution plan to determine the actual performance statistics for the first query execution plan in the first execution context;

executing the first query execution plan to determine the actual performance statistics for the first query execution plan in one or more other execution contexts, the one or more other execution contexts being different than the first execution context;

failing to verify the first query execution plan based at least on the actual performance statistics in the one or more other execution contexts.

13. The method of claim 1, further comprising, subsequent to responding to the first request, but prior to executing the first query execution plan to determine the actual performance statistics for the first plan:

at approximately a particular interval, unsuccessfully attempting to verify the first query execution plan.

20. A non-transitory computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 1.

21. A non-transitory computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 2.

22. A non-transitory computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 3.

23. A non-transitory computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 4.

24. A non-transitory computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 5.

25. A non-transitory computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 6.

26. A non-transitory computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 7.

27. A non-transitory computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 8.

28. A non-transitory computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 9.

29. A non-transitory computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 10.

30. A non-transitory computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 11.

31. A non-transitory computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 12.

32. A non-transitory computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 13.

14. A method comprising:

maintaining, at a database server, plan verification data that identifies one or more query execution plans that have been designated as acceptable for use by the database server to execute a database commands, the database command being a query statement that instructs the database server to perform one or more operations on data stored in a database;

receiving, at the database server, a first request to execute a database command;

at the database server, identifying a first query execution plan for executing the database command in response to the first request;

in response to the first request, and further in response to determining that the plan verification data does not yet indicate whether the first query execution plan has been designated as acceptable for use by the database server to execute the database command, the database server executing the database command according to the first query execution plan concurrent to executing the database command according to a second query execution plan, the second query execution plan being different than the first query execution plan and having been previously designated as acceptable for use by the database server to execute the database command;

the database server responding to the first request using results returned from one of the concurrently executed first query execution plan and second query execution plan; and

responsive to the executing of the first query execution plan completing before the executing of the second query execution plan completes, the database server updating the plan verification data to indicate that the first query execution plan has been designated as acceptable for use by the database server to execute the database command;

wherein the method is performed by one or more computing devices.

15. The method of claim 14, wherein:

determining the first query execution plan for executing the database command comprises;

generating a first set of query execution plans for satisfying the first request to execute the database command;

estimating, for each query execution plan in the first set of query execution plans, predicted costs for satisfying the first request;

based on the predicted costs for each query execution plan in the first set of query execution plans, selecting the first query execution plan from the first set of query execution plans, wherein the predicted costs for the first query execution plan are lower than the predicted costs for any other query execution plan in the first set of query execution plans;

the first set of query execution plans comprises verified query execution plans and unverified query execution plans; and

determining the verified query execution plan comprises;

based on the predicted costs for each query execution plan in the first set of query execution plans, selecting a verified query execution plan from the first set of query execution plans, wherein the predicted costs for the verified query execution plan are lower than predicted costs for any other verified query execution plan in the first set of query execution plans.

33. A non-transitory computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 14.

34. A non-transitory computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 15.

16. A method comprising:

maintaining, at a database server, plan verification data that identifies one or more query execution plans that have been designated as acceptable for use by the database server to execute a database commands, the database command being a query statement that instructs the database server to perform one or more operations on data stored in a database;

receiving, at the database server, a first request to execute a database command;

at the database server, identifying at least a first query execution plan for executing the database command in response to the first request;

based at least in part on determining that the first query execution plan is a new query execution plan, for which no plan verification data is maintained, responding to the first request by executing the database command according to the first query execution plan;

collecting actual performance statistics while executing the database command according to the first query execution plan;

based at least on the actual performance statistics, the database server updating the plan verification data to designate the first query execution plan as unacceptable for executing the database command;

subsequent to updating the plan verification data, the database server receiving a second request to execute the same database command;

at the database server, identifying the first query execution plan for executing the database command in response to the second request; and

based at least in part on determining that the updated verification data designates that (a) the first query execution plan is unacceptable for executing the database command and (b) that a second query execution plan has been designated as acceptable for executing the database command, responding to the second request by executing the database command according to the second query execution plan, the second query execution plan being different than the first query execution plan;

wherein the method is performed by one or more computing devices.

17. The method of claim 16, wherein determining to store verification data for the first query execution plan designating that the first query execution plan is unacceptable is further based on comparing the performance statistics to at least one of predicted costs for the first query execution plan or performance statistics collected from one or more verified query execution plans.

18. The method of claim 16, wherein collecting actual performance statistics for the first query execution plan comprises collecting actual performance statistics from multiple executions of the first query execution plan.

19. The method of claim 16, further comprising:

in response to determining that the first query execution plan is a new query execution plan, for which no plan verification data is maintained, storing verification data indicating that the first query execution plan is preliminary acceptable.

35. A non-transitory computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 16.

36. A non-transitory computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 17.

37. A non-transitory computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 18.

38. A non-transitory computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 19.