Determining validity ranges of query plans based on suboptimality

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;
• c. outputting said developed validity range, and
• wherein said sensitivity is proportional to size of said developed validity range, and 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.

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 and outputting said bounds of said validity range based on said estimated cost, wherein said sensitivity is proportional to said adjusted bounds,
• wherein said comparison in step d, determines 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.