Determining validity ranges of query plans based on suboptimality

• US 20050267866A1
• Filed: 05/28/2004
• Published: 12/01/2005
• Est. Priority Date: 05/28/2004
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Raman, Vijayshankar, Markl, Volker G.
• Granted Patent: US 7,353,219 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

“Determining Validity Ranges of Query Plans Based on Suboptimality” A method for approximating a validity range for a domain of cardinalities of input to an optimal query plan is provided. Such a validity range is iteratively approximated using a modified Newton-Raphson method to find roots of cost functions for optimal and alternative query plans, respectively. The Newton-Raphson method is combined with a method of incrementing roots of cost functions, known as input cardinalities, such that discontinuous and non-differentiable points in cost functions are avoided. In this manner, input cardinalities remain within a domain for which a valid range can be specified. Additionally, a robustness measure is determined by a sensitivity analysis performed on an approximated validity range. Using a robustness measure provided by a sensitivity analysis and resultant validity range and, query plan sub-optimality detection is simplified, re-optimization is selectively triggered, and robustness information is provided to a system or user performing corrective actions.

Claims

1. A method for selecting an optimal query plan for the execution of a database query, said method comprising:

a. comparing a first query plan chosen by a query optimizer to at least one structurally equivalent query plan, said comparison made with respect to cost as a function of input row, outer cardinality;

b. developing a robustness measure for each of said first query plan and at least one structurally equivalent query plan, said robustness measured by the probability that each of said first query plan and at least one structurally equivalent query plans is least-cost with respect to cost determined by a database query execution cost model;

c. selectively choosing either of;

said first query plan or one of said at least one structurally equivalent query plans, based on a comparison of said developed robustness measures and,

wherein said developed robustness measure for said chosen query plan is greater in value than each of said developed robustness measures for each of said first query plan and at least one structurally equivalent query plans not chosen in said choosing step.

2. A method for selecting an optimal query plan, as per claim 1, wherein said probability measure of robustness is determined by the sensitivity of said first query plan to inaccurate input cardinality values estimated by said database query execution cost model.

3. A method for selecting an optimal query plan, as per claim 1, wherein each of said at least one structurally equivalent query plans share in common, at least:

joined tables, predicates, and projected columns, and any of;

physical operators between operands, order of operands between operators, and sort order.

4. A method for selecting an optimal query plan, as per claim 2, wherein said sensitivity is based on a validity range of said input row, outer cardinality for each operator in said first query plan, said first query plan being least-cost with respect to each of said at least one structurally equivalent query plans if values for said input row, outer cardinality are within said validity range, said first query plan not being least-cost, otherwise.

5. A method for selecting an optimal query plan, as per claim 4, wherein said validity range is computed by an application of a Newton-Raphson method.

6. A method for determining the sensitivity of a first query plan chosen by a database query optimizer to input row cardinality values inaccurately estimated by a database query execution cost model, said method comprising:

a. comparing said first query plan to at least one structurally equivalent query plan;

said comparison made with respect to cost as a function over a range of input row cardinality values;

b. developing a validity range of said input row cardinalities values for each operator in said first query plan based on results of said comparison such that said first query plan is least-cost within said developed validity range and said first query plan is not least-cost outside of said developed validity range; and

wherein said sensitivity is proportional to size of said developed validity range.

7. A method for determining the sensitivity of a first query plan, as per claim 6, wherein of said development of a validity range comprises incrementally approaching a point at which said first query plan is not least-cost, by iteratively computing roots for the difference of:

a first cost function for said first query plan and a second cost function for one of said at least one structurally equivalent query plans, each of said costs having a functional dependency, determined by said database query execution cost model, on said input row cardinality.

8. A method for determining the sensitivity of a first query plan, as per claim 7, wherein said point is incrementally approached by an application of a Newton-Raphson method.

9. A method for determining the sensitivity of a first query plan, as per claim 7, wherein said input row cardinality is incremented such that discontinuous and non-differentiable cost computations for each of said first and at least one structurally equivalent query plans are avoided.

10. A method for iteratively refining the sensitivity of a first query plan to inaccurate input cardinality values estimated by a database query execution cost model, said sensitivity iteratively refined from an initial approximation of a validity range for bounding the cardinality of at least one input to a first query plan, said first query plan being least-cost for cardinalities of inputs within said range, each of said iterations comprising:

a. computing a first difference between costs, a first cost determined by a cost function for said first query plan and a second cost determined by a cost function for said second, alternative query plan, each of said costs determined as a function of a common input cardinality, each of said cost functions determined by a database query execution cost model;

b. incrementing said common input cardinality;

c. computing a second difference between costs of said first and second query plans, each of said costs determined as a function of said incremented input cardinality;

d. comparing said first and second differences to determine either of;

convergence or divergence between said first and second cost functions,

e. estimating a cost resulting from a cost function determined by said first and second differences, said cost function receiving as input, said incremented cardinality estimate based on said comparison; and

f. adjusting said bounds of said validity range based on said estimated cost, wherein said sensitivity is proportional to said adjusted bounds.

11. A method for determining the sensitivity of a first query plan to inaccurate input, as per claim 10, wherein said first and second query plans are identical in properties with the exception of an innermost, query plan root operator.

12. A method for determining the sensitivity of a first query plan to inaccurate input, as per claim 10, wherein said initial approximation of said validity range is infinitely large.

13. A method for determining the sensitivity of a first query plan to inaccurate input, as per claim 10, wherein said method iterates until either of:

a specified number of iterations is reached or said computed cost for said second plan is less than or equal to, said computed cost for said first plan.

14. A method for determining the sensitivity of a first query plan to inaccurate input, as per claim 10, wherein said comparison determines convergence if said second difference is either less than zero or equal to zero, and determines divergence, otherwise, said determination of convergence terminating iterations and said determination of divergence further incrementing said incremented input cardinality.

15. A method for determining the sensitivity of a first query plan to inaccurate input, as per claim 10, wherein if said upper bound is greater than said estimated cost, then said upper bound is decreased, and if said lower bound is less than said estimated cost, then said lower bound is increased.

16. A method for determining the sensitivity of a first query plan to inaccurate input, as per claim 10, wherein said validity range determined for said first query plan is determined, individually, by said innermost, root operator.

17. A method for determining the sensitivity of a first query plan to inaccurate input, as per claim 10, wherein said method stores in an Automated Summary Table (AST), any of said:

first cost, second cost, first difference between costs, second difference between costs, common input cardinality, and estimated cost.

18. A method for determining the sensitivity of a first query plan to inaccurate input, 5 as per claim 10, wherein said method operates linearly with respect to both processing time and consumption of memory space.

19. A method for optimally processing data with a processing plan, said method comprising:

a. analyzing the sensitivity of operators in said processing plan to a range of input parameter values, said sensitivity analysis determining a robustness measure for said processing plan;

b. detecting sub-optimality of said processing plan when at least one input parameter value is outside of said range of input parameter values, based on said robustness measure;

c. selectively triggering corrective action based on said sub-optimality detection, wherein said corrective action enables continuity in optimality of said processing of data.

20. A method for optimally processing data using a processing plan, as per claim 19, wherein said method executes during either of:

run-time or compile-time.

21. A method for optimally processing data using a processing plan, as per claim 19, wherein said corrective action comprises either of:

re-optimizing said processing plan to minimize execution cost of said processing or choosing an alternative, processing plan that maximizes said robustness measure for said alternative, processing plan.

22. A method for optimally processing data using a processing plan, as per claim 19, wherein said correction action is either of:

automated re-optimization of said plan or alerting as to sub-optimality of a plan and displaying in a graphical user interface, said robustness measure with each operator in a query plan.

23. A article of manufacture comprising computer usable medium having computer readable program code embodied therein which selects an optimal query plan for the execution of a database query, said medium comprising computer readable program code for:

a. comparing a first query plan chosen by a query optimizer to at least one structurally equivalent query plan, said comparison made with respect to cost as a function of input row, outer cardinality;

b. developing a robustness measure for each of said first query plan and at least one structurally equivalent query plans, said robustness measured by the probability that each of said first query plan and at least one structurally equivalent query plans is least-cost with respect to cost determined by a database query execution cost model; and

c. choosing either of;

said first query plan or one of said at least one structurally equivalent query plans, based on a comparison of said developed robustness measures,

wherein said developed robustness measure for said chosen query plan is greater in value than each of said developed robustness measures for each of said first query plan and at least one structurally equivalent query plans not chosen in said choosing step.

24. A article of manufacture comprising computer usable medium having computer readable program code embodied therein which, iteratively refines the sensitivity of a first query plan to inaccurate input cardinality values estimated by a database query execution cost model, said sensitivity iteratively refined from an initial approximation of a validity range for bounding the cardinality of at least one input to a first query plan, said first query plan being least-cost for cardinalities of inputs within said range, said medium comprising computer readable program code for:

a. computing a first difference between costs, a first cost determined by a cost function for said first query plan and a second cost determined by a cost function for said second, alternative query plan, each of said costs determined as a function of a common input cardinality, each of said cost functions determined by a database query execution cost model;

b. incrementing said common input cardinality;

c. computing a second difference between costs of said first and second query plans, each of said costs determined as a function of said incremented input cardinality;

d. comparing said first and second differences to determine either of;

convergence or divergence between said first and second cost functions;

e. estimating a cost resulting from a cost function determined by said first and second differences, said cost function receiving as input, said incremented cardinality estimate based on said comparison; and

f. adjusting said bounds of said validity range based on said estimated cost, wherein said sensitivity is proportional to said adjusted bounds.

25. A article of manufacture comprising computer usable medium having computer readable program code embodied therein which optimally processes data using a processing plan, said medium comprising computer readable program code for:

a. analyzing the sensitivity of operators in said processing plan to a range of input parameter values, said sensitivity analysis determining a robustness measure for said processing plan;

b. detecting sub-optimality of said plan when at least one input parameter value is outside of said range of input parameter values, based on said robustness measure; and

c. selectively triggering corrective action based on said sub-optimality detection.

26. A method of deploying autonomic functionality in a database system as a business service, said method comprising:

a. analyzing the sensitivity of operators in a data processing plan for said database system to a range of input parameter values, said sensitivity analysis determining a robustness measure for said processing plan;

b. detecting sub-optimality of said plan when at least one input parameter value is outside of said range of input parameter values, based on said robustness measure; and

c. selectively triggering corrective action based on said sub-optimality detection,

wherein said selective triggering of corrective action is a service enabled as an option by a user.

27. A method of deploying autonomic functionality in a database system, as per claim 26, wherein said correction action is either of:

automated re-optimization of said plan or alerting as to sub-optimality of a plan and displaying in a graphical user interface, said robustness measure with each operator in a query plan.

28. A method of deploying autonomic functionality in a database system, as per claim 26, wherein said user is a database administrator.