DATABASE CONFIGURATION ANALYSIS

• US 20070174335A1
• Filed: 01/20/2006
• Published: 07/26/2007
• Est. Priority Date: 01/20/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Umesh Nabar, Shubha, Konig, Arnd
• Granted Patent: US 7,805,443 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/217 Database tuning G06F16/2282 takes precedence; database performance monitoring G06F11/3409

Abstract

To determine a configuration for a database system, a plurality of queries may be sampled from a representative workload using statistical inference to compute the probability of correctly selecting one of a plurality of evaluation configurations. The probability of correctly selecting may determine which and/or how many queries to sample, and/or may be compared to a target probability threshold to determine if more queries must be sampled. The configuration from the plurality of configurations with the lowest estimated cost of executing the representative workload may be determined based on the probability of selecting correctly. Estimator variance may be reduced through a stratified sampling scheme that leverages commonality, such as an average cost of execution, between queries based on query templates. The applicability of the Central Limit Theorem may be verified and used to determine which and/or how many queries to sample.

Claims

1. A method comprising:

a) determining at least two configurations of a database system, each configuration containing one or more tables, indices, and/or views;

b) sampling a first configuration and a second configuration from the at least two configurations;

c) determining a representative workload containing at least one query executable against the database system;

d) sampling a sample workload from at least a portion of the representative workload;

e) estimating a cost of executing the configuration workload based on the first configuration and the second configuration;

f) determining a probability of correct selection of the first configuration and the second configuration;

g) determining a probability of correct selection of the sample workload based at least in part on the probability of correct selection of the first configuration and the second configuration;

h) updating the sample workload if the probability of correct selection of the sample workload does not exceed a target probability threshold; and

i) if the probability of correct selection of the sample workload exceeds the target probability threshold, configuring the data store based on a best configuration of the first configuration and the second configuration based on the estimated cost.

2. The method of claim 1, wherein sampling a sample workload includes using independent sampling.

3. The method of claim 1, wherein estimating a cost of executing includes estimating a first cost of executing the sample workload based on the first configuration and estimating a second cost of executing for the sample workload based on the second configuration.

4. The method of claim 3, wherein updating the sample workload includes adding one more queries from the representative workload to the sample workload such that the sum of the variances of the estimated cost is reduced.

5. The method of claim 1, wherein sampling a sample workload includes using delta sampling.

6. The method of claim 1, wherein estimating a cost of executing includes estimating a difference in cost of executing the sample workload based on the first configuration and the second configuration.

7. The method of claim 1, further comprising stratifying the representative workload into at least two strata including a first stratum and a second stratum, and determining a minimum number of queries to achieve the probability of correct selection of the sample workload, and wherein updating the sample workload includes selecting the minimum number of queries from the first stratum.

8. The method of claim 7, wherein updating the sample workload includes selecting the minimum number of queries from each of the at least two strata.

9. The method of claim 7, wherein stratifying the representative workload includes determining a query template for each query contained in the representative workload, determining an average cost of execution for each determined query template;

and ordering the queries of the representative workload based on the average cost per template, and splitting the representative workload based on a split point of the ordered queries.

10. The method of claim 1, further comprising estimating an upper cost bound and a lower cost bound for queries in the representative workload which are not included in the sample workload, verifying an assumption in determining the probability of correct selection of the first configuration and the second configuration based on the upper and lower cost bounds, and returning to updating the sample workload if the assumption is not verified.

11. The method of claim 10, wherein verifying an assumption includes verifying that a sufficient number of queries have been included in the sample workload by determining an upper bound on a skew of the queries in the representative workload which are not included in the sample workload, and based on the upper bound of the skew, determining a minimum sample size of queries from the representative workload to be included in the sample workload.

12. The method of claim 11, wherein determining an upper bound on the skew includes rounding a plurality of cost variables to multiples of a factor k.

13. The method of claim 10, wherein verifying an assumption includes verifying that a variance of sampled queries in the sample workload represents a true variance by determining an upper bound on a variance of the estimated cost and determining a probability of correct selection based on the determined upper bound on the variance.

14. The method of claim 13, wherein determining an upper bound on the variance includes rounding a plurality of cost variables to multiples of a factor ρ

.

15. A computer readable medium having computer executable components comprising:

a) a data store component for storing a data store against which queries may be executed;

b) an optimizer component for determining a cost of executing a query against the data store component having a given configuration;

c) a workload module for determining a sample workload containing a plurality of queries sampled from a representative workload for the data store component;

d) a configuration module for determining a plurality of evaluation configurations from within a configuration space to be evaluated in configuring the data store component;

e) a cost module for determining an estimated cost of executing the sample workload based on the evaluation configurations and a sampling method; and

f) a probability module for determining a probability of correct selection of the sample workload and outputting the best configuration from the evaluation configurations such that the probability of correct selection of the sample workload is greater than a target probability threshold.

16. The one or more computer readable media of claim 15, wherein the workload module stratifies the representative workload based on an average cost of queries having an identical query template.

17. The one or more computer readable media of claim 15, wherein the probability module verifies applicability of the Central Limit Theorem.

18. The one or more computer readable media of claim 15, further comprising modifying the data store component to have the determined best configuration.

19. A database configuration system comprising:

a) a data store for storing query information;

b) a memory in which machine instructions are stored; and

c) a processor that is coupled to the memory and the data store, the processor executing the machine instructions to carry out a plurality of functions, the machine instructions including;

i) means for determining a sample workload from a representative workload containing a plurality of queries;

ii) means for determining a plurality of evaluation configurations from a configuration space for a database system, each evaluation configuration including any combination of one or more tables, indices, and/or views;

iii) means for estimating a cost of executing the representative workload against the database system having an indicated configuration from the evaluation configurations; and

iv) means for determining a probability of selecting a correct workload such that the probability of selecting a correct workload exceeds a target probability threshold.

20. The system of claim 19, wherein the machine instructions include means for stratifying the representative workload based on an average cost of queries in each identical template.