Automating statistics management for query optimizers

In a database system, a method for evaluating the utility of at least one candidate statistic in the estimation of the selectivity of a query, comprising the steps of:

• a) generating a first execution plan based on an existing set of database statistics;
• b) assigning a first selectivity value to the at least one candidate statistic;
• c) determining a first projected query plan by executing the execution plan with the at least one candidate statistic having the first selectivity value;
• d) assigning a second selectivity value to the at least one candidate statistic;
• e) determining a second projected query plan by executing the execution plan with the at least one candidate statistic having the second selectivity value;
• f) comparing the first projected query plan to the second projected query plan;
• and
• g) assigning a degree of utility to the at least one candidate statistic based on the results of the comparison between the first and second projected query plans.

In a database system, a method for determining a set of statistics with respect to a query workload comprising the steps of:

• a) compiling a set of potentially relevant statistics for a user query comprising a plurality of operators;
• b) determining which potentially relevant statistics have not yet been constructed by the database system;
• c) assigning a first selectivity value to the unconstructed statistics;
• d) computing a first projected query plan for the query wherein the unconstructed statistics have the first value;
• e) assigning a second selectivity value to the unconstructed statistics;
• f) computing a second projected query plan for the query wherein the unconstructed statistics have the second value;
• g) comparing the first and second projected query plans;
• h) discontinuing the determination of a set of statistics if the first and second projected query plans are equivalent;
• i) selecting an unconstructed statistic to build if the first and second projected query plans are not equivalent;
• j) building the unconstructed statistic selected in step (i);
• and
• k) repeating steps (b) through (j) until the first and projected query plans are equivalent or all the unconstructed potentially relevant statistics compiled in step (a) have been constructed.

In a database system, a method for providing automated database statistics management for creating and maintaining a set of essential statistics with respect to a query workload comprising the steps of:

• a) creating an initial set of statistics by
• i) compiling a set of potentially relevant statistics with respect to a query;
• ii) calculating a plurality of projected query plans by assigning a variety of predetermined selectivity values to at least one of the potentially relevant statistics, developing an execution plan for each of the selectivity value assignments and evaluating its cost;
• and
• iii) determining a set of statistics based on the plurality of projected query plans;
• b) eliminating any non-essential statistics by
• i) identifying a subset of the initial set of statistics equivalent to the initial set of statistics with respect to each query, wherein the subset of statistics is equivalent to the initial set of statistics:
• A) if an execution plan for each query using the subset of statistics is the same as an execution plan for that query using the initial set of statistics, and/or
• B) if a cost estimate to execute each query against the database using the subset of statistics is within a predetermined amount of a cost estimate to execute that query against the database using the initial set of statistics.

A computer readable medium having computer-executable instructions for determining a set of statistics with respect to a query workload comprising the steps of:

• a) compiling a set of potentially relevant statistics with respect to a query,
• b) calculating a plurality of projected query plans by assigning a variety of predetermined selectivity values to at least one of the potentially relevant statistics, developing an execution plan for each of the selectivity value assignments and evaluating its cost;
• and
• c) determning a set of statistics based on the plurality of projected query plans.

A computer readable medium having computer-executable instructions for evaluating the utility of at least one candidate statistic in the estimation of the selectivity of a query, comprising the steps of:

• a) generating a first execution plan including the at least one candidate;
• b) assigning a first selectivity value to the at least one candidate statistic;
• c) determining a first projected query plan by executing the execution plan with the at least one candidate statistic having the first selectivity value;
• d) assigning a second selectivity value to the at least one candidate statistic;
• e) determining a second projected query plan by executing the execution plan with the at least one candidate statistic having the second selectivity value;
• f) comparing the first projected query plan to the second projected query plan;
• and
• g) assigning a degree of utility to the at least one candidate statistic based on the results of the comparison between the first and second projected query plans.

A computer readable medium having computer-executable instructions for determining a set of statistics with respect to a query workload comprising the steps of:

• a) compiling a set of potentially relevant statistics for a user query comprising a plurality of operators;
• b) determining which potentially relevant statistics have not yet been constructed by the database system;
• c) assigning a first selectivity value to the unconstructed statistics;
• d) computing a first projected query plan for the query wherein the unconstructed statistics have the first value;
• e) assigning a second selectivity value to the unconstructed statistics;
• f) computing a second projected query plan for the query wherein the unconstructed statistics have the second value;
• g) comparing the first and second projected query plans;
• h) discontinuing the determination of a set of statistics if the first and second projected query plans are equivalent;
• i) selecting an unconstructed statistic to build if the first and second projected query plans are not equivalent;
• j) building the unconstructed statistic selected in step (i);
• and
• k) repeating steps (b) through (j) until the first and projected query plans are similar to within the threshold amount or all the unconstructed potentially relevant statistics compiled in step (a) have been constructed.

A computer readable medium having computer-executable instructions for providing automated database statistics management for creating and maintaining a set of essential statistics with respect to a query workload comprising the steps of:

• a) creating an initial set of statistics by
• i) compiling a set of potentially relevant statistics with respect to a query;
• ii) calculating a plurality of projected query plans by assigning a variety of selectivity values to at least one of the potentially relevant statistics, developing an execution plan for each of the selectivity value assignments and evaluating its cost;
• and
• iii) determining a set of statistics based on the plurality of projected query plans;
• and
• b) eliminating any non-essential statistics by
• i) identifying a subset of the initial set of statistics equivalent to the initial set of statistics with respect to each query, wherein the subset of statistics is equivalent to the initial set of statistics:
• A) if an execution plan for each query using the subset of statistics is the same as an execution plan for that query using the initial set of statistics, and/or
• B) if a cost estimate to execute each query against the database using the subset of statistics is within a predetermined amount of a cost estimate to execute that query against the database using the initial set of statistics.

In a database system, an apparatus for determining a set of statistics with respect to a query workload comprising:

• a) means for compiling a set of potentially relevant statistics with respect to a query;
• b) means for calculating a plurality of projected query plans by assigning a variety of predetermined selectivity values to at least one of the potentially relevant statistics, developing an execution plan for each of the selectivity value assignments and evaluating its cost;
• and
• c) means for determining a set of statistics based on the plurality of projected query plans.

In a database system, an apparatus for evaluating the utility of at least one candidate statistic in the estimation of the selectivity of a query, comprising:

• a) means for generating an execution based on an existing set of database statistics;
• b) means for assigning a first selectivity value to the at least one candidate statistic;
• c) means for determining a first projected query plan by executing the estimation plan with the at least one candidate statistic having the first value;
• d) means for assigning a second selectivity value to the at least one candidate statistic;
• e) means for determining a second projected query plan by executing the estimation plan with the at least one candidate statistic having the second selectivity value;
• f) means for comparing the first projected query plan to the second projected query plan;
• and
• g) means for assigning a degree of utility to the at least one candidate statistic based on the results of the comparison between the first and projected query plans.

In a database system, an apparatus for determining a set of statistics with respect to a query workload comprising:

• a) means for compiling a set of potentially relevant statistics for a user query comprising a plurality of operators;
• b) means for determining which potentially relevant statistics have not yet been constructed by the database system;
• c) means for assigning a first selectivity value to the unconstructed statistics;
• d) means for computing a first projected query plan for the query wherein the unconstructed statistics have the first selectivity value;
• e) means for assigning a second selectivity value to the unconstructed statistics;
• f) means for computing a second projected query plan for the query wherein the unconstructed statistics have the second selectivity value;
• g) means for comparing the first and second projected query plans;
• h) means for discontinuing the determination of a set of statistics if the first and second projected query plans are equivalent;
• i) means for selecting an unconstructed statistic to build if the first and second projected query plans are not equivalent;
• j) means for building the unconstructed statistic selected in step (i);
• and
• k) means for repeating steps (b) through (j) until the first and second projected query plans are equivalent or all the unconstructed potentially relevant statistics compiled in step (a) have been constructed.

In a database system, an apparatus for providing automated database statistics management for creating and maintaining a set of essential statistics with respect to a query workload comprising:

• a) means for creating an initial set of statistics by
• i) means for compiling a set of potentially relevant statistics with respect to a query;
• ii) means for calculating a plurality of projected query plans by assigning a variety of selectivity values to at least one of the potentially relevant statistics, developing an execution plan for each of the selectivity value assignments and evaluating its cost;
• and
• iii) means for determining a set of statistics based on the plurality of projected query plans;
• and
• b) means for eliminating any non-essential statistics by
• i) identifying a subset of the initial set of statistics equivalent to the initial set of statistics with respect to each query, wherein the subset of statistics is equivalent to the initial set of statistics:
• A) if an execution plan for each query using the subset of statistics is the same as an execution plan for that query using the initial set of statistics, and/or
• B) if a cost estimate to execute each query against the database using the subset of statistics is within a predetermined amount of a cost estimate to execute that query against the database using the initial set of statistics.