Patent ID: 7478083

Claim:
A method for estimating a cardinality for a plurality of columns in a database system comprising: obtaining statistics for the plurality of columns, a first portion of the statistics indicating at least one relationship between at least a portion of the plurality of columns, a second portion of the statistics including single column statistics; and utilizing the first portion and the second portion of the statistics to estimate the cardinality for the plurality of columns, including: using column equivalency to determine which of the first portion and the second portion of the statistics to utilize in estimating the cardinality, including homogenizing the at least the second portion of the statistics if possible; and recursively calculating a key cardinality based upon the statistics, the key cardinality indicating the cardinality of the plurality of columns, the recursively calculating including: setting the key cardinality to a minimum of a previous key cardinality for a first portion of the plurality of columns and a column group statistics value for a second portion of the plurality of columns if the first and second portions are the same; setting the key cardinality to the minimum of the previous key cardinality multiplied by the column cardinality for each of at least one additional column and the column group statistics value for a second portion of the plurality of columns if the second portion of the plurality of columns includes the first portion of the plurality of columns and the at least one additional column; setting the key cardinality to the minimum of the previous key cardinality and the column group statistics value for a second portion of the plurality of columns multiplied by the column cardinality for each of at least one difference column if the first portion includes the second portion plus the at least one difference column; setting the key cardinality to the minimum of the previous key cardinality multiplied by the column cardinality for at least a first other column and the column group statistics value for a second portion of the plurality of columns multiplied by the column cardinality for each of the at least the second other column if the first portion includes a first part of the second portion of the plurality of columns plus at least the second other column and the second portion includes a second part of the first portion of the plurality of columns plus at least the first other column; and setting the key cardinality to the previous key cardinality multiplied by the column group statistics value for a second portion of the plurality of columns if the first and second portions do not intersect.