Cardinality estimation of joins

• US 20040260675A1
• Filed: 06/19/2003
• Published: 12/23/2004
• Est. Priority Date: 06/19/2003
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chaudhuri, Surajit, Bruno, Nicolas, Wu, Ming-Chuan, Krishna, Murali
• Granted Patent: US 7,299,226 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2264 Multidimensional index structures
• CPC Class Codes: G06F 16/24545 Selectivity estimation or determination
• CPC Class Codes: Y10S 707/962 Entity-attribute-value
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

A method of estimating cardinality of a join of tables using multi-column density values and additionally using coarser density values of a subset of the multi-column density attributes. In one embodiment, the subset of attributes for the coarser densities is a prefix of the set of multi-column density attributes. A number of tuples from each table that participate in the join may be estimated using densities of the subsets. The cardinality of the join can be estimated using the multi-column density for each table and the estimated number of tuples that participate in the join from each table.

Claims

1. A method of estimating cardinality of a join of tables using multi-column density values, comprising:

a) identifying a multi-column density over a set of attributes for each table;

b) identifying a density of a subset of said set of attributes for each table;

c) estimating a number of tuples from each table that participate in the join using densities of the subsets;

d) estimating the cardinality of the join using the multi-column density for each table and the estimated number of tuples that participate in the join from each table.

2. The method of claim 1 wherein estimating a number of tuples of one of the tables that participate in the join comprises estimating a number of distinct values of a subset of said set of attributes in a first table, estimating a number of distinct values of a subset of said set of attributes in a second table, and multiplying a density of the subset of attributes in each table by a minimum of the estimated numbers of distinct values.

3. The method of claim 2 wherein the number of distinct values of a subset of said set of attributes in a table is calculated by dividing the cardinality of the table by the density of the subset of attributes in the table.

4. The method of claim 1 wherein said estimating cardinality comprises selecting the minimum of an estimated number of tuples from a first table that participate in the join divided by a multi-column density over a set of attributes for the first table and an estimated number of tuples from a second table that participate in the join divided by a multi-column density over a set of attributes for the second table and multiplying said minimum, said multi-column density over a set of attributes for the first table, and said multi-column density over a set of attributes for the second table.

5. The method of claim 1 wherein said subset comprises prefixes of said set of attributes.

6. The method of claim 1 wherein densities of a plurality of subsets of the set of attributes are used to calculate a plurality of cardinality estimations and a minimum of the plurality of cardinality estimations is selected as the cardinality estimation for the join.

7. A method of estimating cardinality of a join of tables using multi-column density values, comprising:

a) identifying a multi-column density over a set of attributes for each table;

b) identifying a density of a subset of said set of attributes for each table;

c) identifying a cardinality of each table;

d) estimating the cardinality of the join using the multi-column density for each table, the density of said subset of said set of attributes for each table, and the cardinality of each table.

8. The method of claim 7 further comprising estimating a number of tuples from each table that participate in the join using densities of the subsets and cardinalities of the tables and wherein the cardinality of the join is estimated using the multi-column density for each table and the estimated number of tuples that participate in the join from each table.

9. The method of claim 8 wherein estimating a number of tuples of one of the tables that participate in the join comprises estimating a number of distinct values of a subset of said set of attributes in a first table, estimating a number of distinct values of a subset of said set of attributes in a second table, and multiplying a density of the subset of attributes in each table by a minimum of the estimated numbers of distinct values.

10. The method of claim 8 wherein the number of distinct values of a subset of said set of attributes in a table is calculated by dividing the cardinality of the table by the density of the subset of attributes in the table.

11. The method of claim 8 wherein said estimating cardinality comprises selecting a minimum of an estimated number of tuples from a first table that participate in the join divided by a multi-column density over a set of attributes for the first table and an estimated number of tuples from a second table that participate in the join divided by a multi-column density over a set of attributes for the second table and multiplying said minimum, said multi-column density over a set of attributes for the first table, and said multi-column density over a set of attributes for the second table.

12. The method of claim 7 wherein said subset comprises prefixes of said set of attributes.

13. The method of claim 7 wherein estimating the cardinality comprises identifying a first minimum of a cardinality of a first table divided by a density of a subset of said set of attributes for the first table and a cardinality of a second table divided by a density of a subset of said set of attributes for the second table, identifying a second minimum of said density of said subset of said set of attributes for the first table divided by a multi-column density over said set of attributes for the first table and said density of said subset of said set of attributes for the second table divided by a multi-column density over said set of attributes for the second table, and multiplying said first minimum, said second minimum, said multi-column density over said set of attributes for the first table, and said multi-column density over said set of attributes for the second table.

14. The method of claim 7 wherein densities of a plurality of subsets of the set of attributes are used to calculate a plurality of cardinality estimations and a minimum of the plurality of cardinality estimations is selected as the cardinality estimation for the join.

15. In a method of estimating cardinality of a join of tables using a multi-column density over a set of attributes is identified for each table and the cardinality of each table, the improvement comprising additionally using a density of a subset of said set of attributes for each table to estimate the cardinality of the join.

16. The method of claim 15 wherein densities of said subsets are used to estimate a number of tuples from each table that participate in the join and the cardinality of the join is estimated using the multi-column density for each table and the estimated number of tuples that participate in the join from each table.

17. The method of claim 16 wherein estimating a number of tuples of each of the tables that participate in the join comprises estimating a number of distinct values of a subset of said set of attributes in a first table, estimating a number of distinct values of a subset of said set of attributes in a second table, and multiplying a density of the subset of attributes in each table by a minimum of the estimated numbers of distinct values.

18. The method of claim 17 wherein the number of distinct values of a subset of said set of attributes in a table is calculated by dividing the cardinality of the table by the density of the subset of attributes in the table.

19. The method of claim 16 wherein said estimating cardinality comprises selecting the minimum of an estimated number of tuples from a first table that participate in the join divided by a multi-column density over a set of attributes for the first table and an estimated number of tuples from a second table that participate in the join divided by a multi-column density over a set of attributes for the second table and multiplying said minimum, said multi-column density over a set of attributes for the first table, and said multi-column density over a set of attributes for the second table.

20. The method of claim 15 wherein said subset comprises prefixes of said set of attributes.

21. A method of estimating cardinality of a join of tables using multi-column density values and histograms, comprising:

a) identifying a multi-column density over a set of attributes for each table;

b) identifying a histogram over an attribute from said set of attributes for each table;

c) aligning buckets of each histogram

d) estimating for each bucket in a pair of aligned buckets a number of tuples from each table that participate in the join using densities of the buckets; and

e) estimating the cardinality of the join of a pair of buckets using the multi-column density for each table and the estimated number of tuples that participate in the join from each bucket in the pair of aligned buckets.

22. The method of claim 21 wherein the cardinality is estimated for each pair of buckets and is summed to estimate the cardinality of the join of tables.

23. A method of estimating cardinality of a join of tables using multi-column density values, comprising:

a) identifying a multi-column density over a set of attributes for each table;

b) identifying a histogram over an attribute from said set of attributes for each table;

c) aligning buckets of each histogram;

d) identifying a number of tuples in each bucket of a pair of aligned buckets;

e) estimating the cardinality of the join of the pair of buckets using the multi-column density for each table, the density of each bucket of the pair of buckets, and the number of tuples in each bucket of the pair of buckets.

24. The method of claim 23 wherein the cardinality is estimated for each pair of buckets and is summed to estimate the cardinality of the join of tables.

25. A computer readable medium having computer executable instructions stored thereon for performing a method of estimating cardinality of a join of tables using multi-column density values, the method comprising:

a) identifying a multi-column density over a set of attributes for each table;

b) identifying a density of a subset of said set of attributes for each table;

c) estimating a number of tuples from each table that participate in the join using densities of the subsets;

d) estimating the cardinality of the join using the multi-column density for each table and the estimated number of tuples that participate in the join from each table.

26. The computer readable medium of claim 25 wherein estimating a number of tuples of one of the tables that participate in the join comprises estimating a number of distinct values of a subset of said set of attributes in a first table, estimating a number of distinct values of a subset of said set of attributes in a second table, and multiplying a density of the subset of attributes in each table by a minimum of the estimated numbers of distinct values.

27. The computer readable medium of claim 26 wherein the number of distinct values of a subset of said set of attributes in a table is calculated by dividing the cardinality of the table by the density of the subset of attributes in the table.

28. The computer readable medium of claim 25 wherein said estimating cardinality comprises selecting the minimum of an estimated number of tuples from a first table that participate in the join divided by a multi-column density over a set of attributes for the first table and an estimated number of tuples from a second table that participate in the join divided by a multi-column density over a set of attributes for the second table and multiplying said minimum, said multi-column density over a set of attributes for the first table, and said multi-column density over a set of attributes for the second table.

29. The computer readable medium of claim 25 wherein said subset comprises prefixes of said set of attributes.

30. The computer readable medium of claim 25 wherein densities of a plurality of subsets of the set of attributes are used to calculate a plurality of cardinality estimations and a minimum of the plurality of cardinality estimations is selected as the cardinality estimation for the join.

31. A computer readable medium having computer executable instructions stored thereon for performing a method of estimating cardinality of a join of tables using multi-column density values, the method comprising:

a) identifying a multi-column density over a set of attributes for each table;

b) identifying a density of a subset of said set of attributes for each table;

c) identifying a cardinality of each table;

d) estimating the cardinality of the join using the multi-column density for each table, the density of said subset of said set of attributes for each table, and the cardinality of each table.

32. The computer readable medium of claim 31 wherein the method further comprises estimating a number of tuples from each table that participate in the join using densities of the subsets and cardinalities of the tables and wherein the cardinality of the join is estimated using the multi-column density for each table and the estimated number of tuples that participate in the join from each table.

33. The computer readable medium of claim 32 wherein estimating a number of tuples of each of the tables that participate in the join comprises estimating a number of distinct values of a subset of said set of attributes in a first table, estimating a number of distinct values of a subset of said set of attributes in a second table, and multiplying a density of the subset of attributes in each table by a minimum of the estimated numbers of distinct values.

34. The computer readable medium of claim 32 wherein the number of distinct values of a subset of said set of attributes in a table is calculated by dividing the cardinality of the table by the density of the subset of attributes in the table.

35. The computer readable medium of claim 32 wherein said estimating cardinality comprises selecting a minimum of an estimated number of tuples from a first table that participate in the join divided by a multi-column density over a set of attributes for the first table and an estimated number of tuples from a second table that participate in the join divided by a multi-column density over a set of attributes for the second table and multiplying said minimum, said multi-column density over a set of attributes for the first table, and said multi-column density over a set of attributes for the second table.

36. The computer readable medium of claim 31 wherein said subset comprises prefixes of said set of attributes.

37. The computer readable medium of claim 31 wherein estimating the cardinality comprises identifying a first minimum of a cardinality of a first table divided by a density of a subset of said set of attributes for the first table and a cardinality of a second table divided by a density of a subset of said set of attributes for the second table, identifying a second minimum of said density of said subset of said set of attributes for the first table divided by a multi-column density over said set of attributes for the first table and said density of said subset of said set of attributes for the second table divided by a multi-column density over said set of attributes for the second table, and multiplying said first minimum, said second minimum, said multi-column density over said set of attributes for the first table, and said multi-column density over said set of attributes for the second table.

38. The computer readable medium of claim 31 wherein densities of a plurality of subsets of the set of attributes are used to calculate a plurality of cardinality estimations and a minimum of the plurality of cardinality estimations is selected as the cardinality estimation for the join.

39. A computer readable medium having computer executable instructions stored thereon for performing a method of estimating cardinality of a join of tables using multi-column density values histograms, the method comprising:

a) identifying a multi-column density over a set of attributes for each table;

b) identifying a histogram over an attribute from said set of attributes for each table;

c) aligning buckets of each histogram

d) estimating for each bucket in a pair of aligned buckets a number of tuples from each table that participate in the join using densities of the buckets; and

e) estimating the cardinality of the join of a pair of buckets using the multi-column density for each table and the estimated number of tuples that participate in the join from each bucket in the pair of aligned buckets.

40. The computer readable medium of claim 39 wherein the cardinality is estimated for each pair of buckets and is summed to estimate the cardinality of the join of tables.

41. A computer readable medium having computer executable instructions stored thereon for performing a method of estimating cardinality of a join of tables using multi-column density values histograms, the method comprising:

a) identifying a multi-column density over a set of attributes for each table;

b) identifying a histogram over an attribute from said set of attributes for each table;

c) aligning buckets of each histogram;

d) identifying a number of tuples in each bucket of a pair of aligned buckets;

e) estimating the cardinality of the join of the pair of buckets using the multi-column density for each table, the density of each bucket of the pair of buckets, and the number of tuples in each bucket of the pair of buckets.

42. The computer readable medium of claim 41 wherein the cardinality is estimated for each pair of buckets and is summed to estimate the cardinality of the join of tables.