Patent ID: 8572067

Claim:
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.