Method to estimate the number of distinct value combinations for a set of attributes in a database system

1. A method implemented by a computer system including a processor to estimate the number of distinct value combinations for a set of attributes in a table of a database system, the number of distinct value combinations being provided for a number of distinct values of each of the attributes in the set of attributes, the method comprising:

using the processor to utilize frequency information for the set of attributes to provide an estimate for the number of distinct value combinations, wherein the frequency information includes individual frequency statistics for each individual attribute in the set of attributes, the individual frequency statistics indicating the number of times each distinct value appears in each individual attribute in the set of attributes,

wherein using the processor to utilize frequency information includes:

using the individual frequency statistics to determine a probability of occurrence of each specific value combination of the distinct values, and

using the probability of occurrence of each specific value combination to provide the estimate for the number of distinct value combinations, including determining a lower number of distinct value combinations than a maximum number of distinct value combinations for the distinct values, wherein determining a lower number of distinct value combinations includes subtracting from the maximum possible number of distinct value combinations a sum of probabilities that the value combinations do not occur in the table, wherein the sum of probabilities is determined using the individual frequency statistics.

2. The method of claim 1 wherein the utilizing step further includes providing bounds on the distinct value combinations, wherein the bounds are determined utilizing the individual frequency statistics of the set of attributes.

3. The method of claim 2 , wherein a lower bound of the bounds is defined by an equation comprising the greater of:

max

i

=

1

,

m

⁢

{

∑

j

=

1

d

i

⁢

l

ij

}

⁢

⁢

and

⁢

⁢

max

i

=

1

,

m

⁢

{

d

i

}

wherein m is a number of the attributes in the set of attributes;

lij is a minimum number of different distinct values for the individual attributes in the set of attributes that have to be combined with fij given the individual frequency statistics of each individual attribute;

di is the number of distinct values in the attribute i; and

{fij} is a tensor product of frequency vectors of all attributes.

4. The method of claim 2 , wherein an upper bound of the bounds is defined by an equation comprising the lesser of:

max

i

=

1

,

m

⁢

{

∑

j

=

1

d

i

⁢

u

ij

}

⁢

⁢

and

⁢

⁢

min

⁢

{

∏

i

=

1

m

⁢

d

i

,

N

}

wherein m is a number of attributes;

uij is a maximum number of different distinct values for the individual attributes in the set of attributes that can be combined with fij given the individual frequency statistics of each individual attribute;

{di} is a vector consisting of the number of distinct values for the individual attributes in the m number of attributes; and

{fij} is a tensor product of frequency vectors of all attributes.

5. The method of claim 1 further comprising using the processor to utilize the estimate to determine a cost of a query execution plan that includes an access path for a query accessing the table of the database system.

6. The method of claim 2 , wherein the bounds are tighter than trivial bounds, wherein an upper trivial bound is based on a size of the table and a product of the distinct values of the set of attributes, and wherein a lower trivial bound is based on a maximum of a number of distinct values of any of the individual attributes of the set of attributes.

7. A non-transitory computer readable storage medium storing program instructions implemented by a computer system for estimating the number of distinct value combinations for a set of attributes in a table of a database system, the number of distinct value combinations being provided for a number of distinct values of each of the attributes in the set of attributes, the program instructions for:

utilizing frequency information for the set of attributes to provide an estimate for the number of distinct value combinations, wherein the frequency information includes individual frequency statistics for each individual attribute in the set of attributes, the individual frequency statistics indicating the number of times each distinct value appears in each individual attribute in the set of attributes,

wherein utilizing the frequency information includes:

using the individual frequency statistics to determine a probability of occurrence of each specific value combination of the distinct values, and

using the probability of occurrence of each specific value combination to provide the estimate for the number of distinct value combinations, including determining a lower number of distinct value combinations than a maximum number of distinct value combinations for the distinct values, wherein determining a lower number of distinct value combinations includes subtracting from the maximum possible number of distinct value combinations a sum of probabilities that the value combinations do not occur in the table, wherein the sum of probabilities is determined using the individual frequency statistics.

8. The computer readable storage medium of claim 7 wherein the utilizing frequency information further includes providing bounds on the distinct value combinations, wherein the bounds are determined utilizing the individual frequency statistics of the set of attributes, wherein if the estimate is greater than an upper bound then the estimate is set to the upper bound and if the estimate is less than a lower bound then the estimate is set to the lower bound.

9. The computer readable storage medium of claim 8 , wherein the bounds are tighter than trivial bounds, wherein an upper trivial bound is based on a product of the distinct values of the individual values of the set of attributes, and wherein a lower trivial bound is based on a maximum of a number of distinct values of any of the individual attributes of the set of attributes.

10. The computer readable storage medium of claim 7 wherein the program instructions further utilize the estimate to determine a cost of a query execution plan that includes an access path for a query accessing the table of the database system.

11. A data processing system for estimating the number of distinct value combinations for a set of attributes, the number of distinct value combinations being provided for a number of distinct values of each of the attributes in the set of attributes, the data processing system comprising:

at least one storage element storing a table of a database system, the set of attributes applying to the table; and

at least one processor utilizing frequency information for the set of attributes to provide an estimate for the number of distinct value combinations, wherein the frequency information includes individual frequency statistics for each individual attribute in the set of attributes, the individual frequency statistics indicating the number of times each distinct value appears in each individual attribute in the set of attributes.

wherein using the processor utilizing the frequency information includes:

using the individual frequency statistics to determine a probability of occurrence of each specific value combination of the distinct values, and

using the probability of occurrence of each specific value combination to provide the estimate for the number of distinct value combinations, including determining a lower number of distinct value combinations than a maximum number of distinct value combinations for the distinct values, wherein determining a lower number of distinct value combinations includes subtracting from the maximum possible number of distinct value combinations a sum of probabilities that the value combinations do not occur in the table, wherein the sum of probabilities is determined using the individual frequency statistics.

12. The data processing system of claim 11 wherein the at least one processor utilizing frequency information further provides bounds on the distinct value combinations, wherein the bounds are determined utilizing the individual frequency statistics of the set of attributes.

13. The data processing system of claim 12 , wherein the bounds are tighter than trivial bounds, wherein an upper trivial bound is based on a product of the distinct values of the individual values of the set of attributes, and wherein a lower trivial bound is based on a maximum of a number of distinct values of any of the individual attributes of the set of attributes.

14. The data processing system of claim 11 wherein the at least one processor utilizes the estimate to determine a cost of a query execution plan that includes an access path for a query accessing the table of the database system.