Query selectivity estimation with confidence interval

• US 7,636,707 B2
• Filed: 04/06/2004
• Issued: 12/22/2009
• Est. Priority Date: 04/06/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Babcock, Brian Frederick, Chaudhuri, Surajit
• Primary Examiner(s): Jalil; Neveen Abel
• Assistant Examiner(s): Pulliam; Christyann R
• Application Number:
  US10/818,730
• Publication Number:
  US 20050228779A1
• Time in Patent Office: 2,086 Days
• Field of Search: 707/3
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24545 Selectivity estimation or determination
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

Selectivity estimates are produced that meet a desired confidence threshold. To determine the confidence level of a given selectivity estimate for a query expression, the query expression is evaluated on a sample tuples. A probability density function is derived based on the number of tuples in the sample that satisfy the query expression. The cumulative distribution for the probability density function is solved for the given threshold to determine a selectivity estimate at the given confidence value.

Claims

1. A method implemented at least in part by a processor executing computer-executable instructions stored in computer-readable storage media for selecting a query plan from at least two query plans, each of the at least two query plans having a query expression on a database, the method comprising:

computing a uniform random sample of database tuples by randomly sampling tuples from the database;

for each of the at least two query plans, deriving, by the processor, a probability distribution for possible selectivity values of the query expression by evaluating each query expression on the sample of database tuples to determine an observed selectivity for the sample of database tuples;

forming a probability density function based on the observed selectivity using Bayes'"'"'s rule;

receiving a desired selectivity confidence threshold from a user input, wherein the desired selectivity confidence threshold represents a tradeoff between predictability and performance for query execution time;

evaluating, by the process, each of the derived probability distributions using the desired selectivity confidence threshold to derive an estimated selectivity for the derived probability distribution, wherein the estimated selectivity is derived by inverting a cumulative distribution function for the probability distribution and applying the inverted cumulative distribution function to the desired selectivity confidence threshold;

selecting one of the query plans from the at least two query plans based on the estimated selectivities and at least one crossover point, each at least one crossover point defining a selectivity where query execution time of one query plan is estimated to equal query execution time of another query plan of the at least two query plans; and

executing the selected query plan to retrieve and store records from a database.

2. The method of claim 1 wherein the uniform random sample of database tuples is updated periodically when a predetermined number of database modifications have occurred.

3. The method of claim 1 wherein the probability density function is derived assuming a uniform prior distribution.

4. The method of claim 1 the probability density function is derived assuming a Jeffreys prior distribution.

5. The method of claim 1 wherein the uniform random sample is precomputed by:

uniformly randomly sampling tuples from a first relation in the database to form a first sample;

joining the first sample with tuples from one or more other relations in the database to which the first relation is connected transitively via foreign joins; and

wherein when a query expression includes a join of the first and the one or more other relations, the query expression is evaluated on the join of the first sample and the one or more other relations.

6. One or more computer readable media comprising computer-executable instructions that when executed cause a computer to perform the method of claim 1.

7. A system for selecting a query plan from at least two query plans, each of the at least two query plans having a query expression executed on a database comprising:

a processor; and

memory including software components that are executed by the processor, the memory including

a query expression evaluator that evaluates for each of the at least two query plans the query expression on a sample of database tuples to determine an observed selectivity;

a probability distribution derivation module that derives a probability distribution of possible selectivity values for each of the query expressions based on the observed selectivity;

a probability distribution resolver that receives a user input indicating a desired selectivity confidence threshold determines estimated selectivities for the at least two query plans based on the desired selectivity confidence and the probability distribution, wherein the desired selectivity confidence threshold represents a tradeoff between predictability and performance for query execution time;

a query optimizer that selects one of the query plans from the at least two query plans based on the estimated selectivities and at least one crossover point, each at least one crossover point defining a selectivity at which query execution time of one query plan is estimated to equal query execution time of another query plan; and

an execution engine that executes the selected query plan to retrieve and stores record from the database.

8. The system of claim 7 further comprising a database tuple sampler that samples tuples from the database to precompute the sample.

9. The system of claim 8 wherein the database tuple sampler randomly samples tuples from the database, wherein the sample of database tuples is updated periodically when a predetermined number of database modifications have occurred.

10. The system of claim 8 wherein the database tuple sampler includes a join sampling module that uniformly randomly samples tuples from a first relation in the database to form a first sample;

joins the first sample with tuples from one or more other relations in the database to which the first relation is connected transitively via foreign joins; and

wherein when a query expression includes a join of the first and the one or more other relations, the query expression is evaluated on the join of the first sample and the one or more other relations.

11. The system of claim 7 wherein the probability density derivation module forms a probability density function based the observed selectivity using Bayes'"'"'s rule.

12. The system of claim 11 wherein the probability density function is derived assuming a uniform prior distribution.

13. The system of claim 11 wherein the probability density function is derived assuming a Jeffreys prior distribution.

14. The system of claim 7 wherein the probability distribution resolver determines the estimated selectivities by inverting a cumulative distribution function for the probability distribution and applying the cumulative distribution function on the desired selectivity confidence threshold.

15. One or more computer readable media having computer-executable instructions stored thereon for selecting a query plan from at least two query plans, each of the at least two query plans having a query expression executed on a database, the instructions, when executed on a computer execute steps comprising:

evaluating, for each of the at least two query plans, the query expression on a sample of database tuples to determine an observed selectivity;

for each of the at least two query plans, deriving a probability distribution of possible selectivity values of the query expression based on the observed selectivity;

receiving a desired selectivity threshold from a user input, wherein the confidence threshold provides user control over a tradeoff between predictability and performance for query execution time;

determining estimated selectivities for the at least two query plans based on the desired selectivity confidence threshold and the derived probability distributions, wherein the estimated selectivities are determined by inverting a cumulative distribution function for the probability distribution and applying the cumulative distribution function on the desired selectivity confidence threshold;

selecting one of the query plans from the at least two query plans based on the estimated selectivities and at least one crossover point, each at least one crossover point defining a selectivity at which query execution time of one query plan is estimated to equal query execution time of another query plan, and

executing the selected query plan to retrieve and store records from the database.

16. The computer readable media of claim 15 wherein the instructions further comprise sampling tuples from the database to precompute the sample.

17. The computer readable media of claim 16 wherein the instructions comprise randomly sampling tuples from the database, wherein the sample of database tuples is updated periodically when a predetermined number of database modifications have occurred.

18. The computer readable media of claim 16 wherein the instructions further comprise uniformly randomly sampling tuples from a first relation in the database to form a first sample;

joining the first sample with tuples from one or more other relations in the database to which the first relation is connected transitively via foreign joins; and

wherein when a query expression includes a join of the first and the one or more other relations, the evaluating the query expression on the join of the first sample and the one or more other relations.

19. The computer readable medium of claim 15 wherein the probability distribution is derived by forming a probability density function based on the observed selectivity using Bayes'"'"'s rule.