Query selectivity estimation with confidence interval

• US 20050228779A1
• Filed: 04/06/2004
• Published: 10/13/2005
• Est. Priority Date: 04/06/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chaudhuri, Surajit, Babcock, Brian Frederick
• Granted Patent: US 7,636,707 B2
• Time in Patent Office: Days
• 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 that estimates a selectivity of a query expression on a database comprising:

deriving a probability distribution for possible selectivity values for the query expression; and

evaluating the probability distribution using a desired selectivity confidence to derive the estimated selectivity.

2. The method of claim 1 comprising deriving the probability distribution for possible selectivity values by evaluating the query expression on a sample of database tuples to determine an observed selectivity.

3. The method of claim 2 wherein the sample of database tuples is precomputed by randomly sampling tuples from the database.

4. The method of claim 2 comprising deriving the probability distribution by forming a probability density function based on the observed selectivity using Bayes'"'"'s rule.

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

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

7. The method of claim 3 wherein the 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.

8. The method of claim 1 wherein the probability distribution is evaluated by inverting a cumulative distribution function for the probability distribution and solving the cumulative distribution function for the desired confidence threshold.

9. One or more computer readable media comprising computer-executable instructions for performing the method of claim 1.

10. A system for estimating a selectivity of a query expression executed on a database given a desired selectivity confidence comprising:

a query expression evaluator that evaluates the query expression on a sample of database tuples to determine a an observed selectivity;

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

a probability distribution resolver that determines an estimated selectivity based on the desired selectivity confidence and the probability distribution.

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

12. The system of claim 11 wherein the database tuple sampler randomly samples tuples from the database.

13. The system of claim 11 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.

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

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

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

17. The system of claim 10 wherein the probability distribution resolver determines a selectivity by inverting a cumulative distribution function for the probability distribution and solving the cumulative distribution function for the desired confidence threshold.

18. An apparatus for estimating a selectivity of a query expression executed on a database that stores tuples given a desired selectivity confidence comprising:

means for evaluating the query expression on a sample of database tuples to determine an observed selectivity;

means for deriving a probability distribution of possible selectivity values for the query expression based on the observed selectivity; and

means for determining a selectivity based on the desired selectivity confidence and the probability distribution.

19. The apparatus of claim 18 further comprising means for sampling tuples from the database to precompute the sample.

20. The apparatus of claim 19 wherein the means for sampling randomly samples tuples from the database.

21. The apparatus of claim 19 wherein the means for sampling includes a means for uniformly randomly sampling tuples from a first relation in the database to form a first sample and means for 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 means for evaluating evaluates the query on the join of the first sample and the one or more other relations

22. The apparatus of claim 18 wherein the means for deriving probability density forms a probability density function based on the observed selectivity.

23. The apparatus of claim 18 wherein the means for determining a selectivity determines a selectivity by inverting a cumulative distribution function for the probability distribution and solving the cumulative distribution function for the desired confidence threshold.

24. One or more computer readable media having computer-executable instructions stored thereon for estimating a selectivity with a desired selectivity confidence for a query expression executed on a database, the instructions comprising:

evaluating the query expression on a sample of database tuples to determine an observed selectivity;

deriving a probability distribution of possible selectivity values for the query expression based on the observed selectivity; and

determining a selectivity based on the desired selectivity confidence and the probability distribution.

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

26. The computer readable media of claim 25 wherein the instructions comprise randomly sampling tuples from the database.

27. The computer readable media of claim 25 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.

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

29. The computer readable medium of claim 24 wherein the selectivity is determined by inverting a cumulative distribution function for the probability distribution and solving the cumulative distribution function for the desired confidence threshold.