Database configuration analysis

• US 7,805,443 B2
• Filed: 01/20/2006
• Issued: 09/28/2010
• Est. Priority Date: 01/20/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Konig, Arnd Christian, Nabar, Shubha Umesh
• Primary Examiner(s): Mahmoudi; Tony
• Assistant Examiner(s): Hu; Jensen
• Application Number:
  US11/275,657
• Publication Number:
  US 20070174335A1
• Time in Patent Office: 1,712 Days
• Field of Search: 707/104.1
• US Class Current: 707/736
• 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 of configuring a database through a database configuration system, the database configuration system having a computing device, the 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 sample 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 and a sensitivity parameter that represents an estimated difference in cost between the first configuration and the second configuration;

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

i) when 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 or 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, and further eliminating an individual configuration as an incorrect choice where the difference in estimated costs is less than 0 and a true difference in costs is greater than the sensitivity parameter.

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 when 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 storage medium having computer executable components comprising:

a) a data store component configured to store a data store against which queries may be executed;

b) an optimizer component configured to determine a cost of executing a query against the data store component having a given configuration;

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

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

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

f) a probability module configured to determine a probability of correct selection of the sample workload and to output the best configuration, that satisfies a sensitivity parameter, from the evaluation configurations without determining a true difference in costs between the evaluation configurations, such that the probability of correct selection of the sample workload is greater than a target probability threshold.

16. The computer readable medium 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 computer readable medium of claim 15, wherein the probability module verifies applicability of the Central Limit Theorem.

18. The computer readable medium 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, individual evaluation configurations including any combination of one or more tables, indices, and/or views;

iii) means for estimating a cost of executing the sample workload against the database system having an individual evaluation configuration, the cost of executing the sample workload is a time to execute the plurality of queries and includes an upper bound and a lower bound, the means for estimating further configured to employ a sensitivity parameter to avoid sampling a large fraction of the sample workload for evaluation configurations with similar costs; and

iv) means for determining a probability of selecting a correct workload, based on the upper and lower bounds of the cost of executing, 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.