Patent ID: 7636731

Claim:
A method comprising: establishing at least a portion of a domain of values as a selected portion of the domain; constructing a synopsis of a portion of a table by performing the following: for each table value in the portion of the table: mapping the table value to a domain value within the domain; and if the domain value to which the table value mapped does not exist in the synopsis and the domain value is within the selected portion of the domain, adding the domain value to the synopsis; while constructing the synopsis, if the number of domain values in the synopsis exceeds a threshold number of domain values, performing the following: reducing the size of the selected portion of the domain; and removing domain values from the synopsis that are outside of the selected portion of the domain; and after constructing the synopsis, estimating the number of distinct values that exist in the portion of the table based on the number of domain values in the synopsis and the size of the selected portion of the domain relative to the size of the domain, where the method is performed by one or more computers.