Determining validity ranges of query plans based on suboptimality
First Claim
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, said first query plan formulated based on a graph of query plan operators connected by directed edges, with each edge d providing a set of rows to an operator o in a given query plan;
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, and said robustness measure for a query operator and a query plan being proportional to a size of a corresponding validity range, with a larger validity range for a query operator or plan indicating a proportionally larger margin of allowable error in cardinality estimation prior to a query plan being deemed sub-optimal, said validity range for each said edge d defined by an upper and lower bound on a cardinality of rows flowing through operator o, such that when said cardinality of rows flowing through operator o falls outside said upper and lower bounds, a given plan becomes sub-optimal;
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;
d. executing a database query based on said selected query plan in step c, 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.
1 Assignment
0 Petitions
Accused Products
Abstract
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.
-
Citations
4 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, said first query plan formulated based on a graph of query plan operators connected by directed edges, with each edge d providing a set of rows to an operator o in a given query plan; 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, and said robustness measure for a query operator and a query plan being proportional to a size of a corresponding validity range, with a larger validity range for a query operator or plan indicating a proportionally larger margin of allowable error in cardinality estimation prior to a query plan being deemed sub-optimal, said validity range for each said edge d defined by an upper and lower bound on a cardinality of rows flowing through operator o, such that when said cardinality of rows flowing through operator o falls outside said upper and lower bounds, a given plan becomes sub-optimal; 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;d. executing a database query based on said selected query plan in step c, 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. - View Dependent Claims (2)
-
-
3. 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 first query plan formulated based on a graph of query plan operators connected by directed edges, with each edge d providing a set of rows to an operator o in a given query plan, 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, said validity range for each said edge d defined by an upper and lower bound on a cardinality of rows flowing through operator o, such that when said cardinality of rows flowing through operator o falls outside said upper and lower bounds, a given plan becomes sub-optimal; c. outputting said developed validity range, and wherein sensitivity of said first query plan is proportional to size of said developed validity range.
-
-
4. An article of manufacture comprising non-transitory computer usable medium having computer readable program code embodied therein which selects an optimal query plan for the execution of a database query, said non-transitory 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, said first query plan formulated based on a graph of query plan operators connected by directed edges, with each edge d providing a set of rows to an operator o in a given query plan; 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 said robustness measure for a query operator and a query plan being proportional to a size of a corresponding validity range, with a larger validity range for a query operator or plan indicating a proportionally larger margin of allowable error in cardinality estimation prior to a query plan being deemed sub-optimal, said validity range for each said edge d defined by an upper and lower bound on a cardinality of rows flowing through operator o, such that when said cardinality of rows flowing through operator o falls outside said upper and lower bounds, a given plan becomes sub-optimal; 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;d. executing a database query based on said chosen query plan in step c, 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.
-
Specification