Patent ID: 7203685
Filing Date: 2007-04-10
Classification: G06F,Y10S

Abstract:
1. An apparatus comprising: at least one processor; a memory coupled to the at least one processor; a database table residing in the memory; a cardinality estimator residing in the memory and executed by the at least one processor, the cardinality estimator estimating cardinality of an intermediate dataset that satisfies a query to the database table in a manner that accounts for data skew in the database table; a query optimizer residing in the memory that uses the estimated cardinality from the cardinality estimator to optimize the query; and a frequent values list residing in the memory that contains a list of values in the database table, each value having a corresponding frequency, wherein the cardinality estimator estimates the cardinality of the intermediate dataset by determining whether a frequency corresponding to a value exceeds a predetermined threshold, and if the frequency exceeds the predetermined threshold, accounting for the corresponding value, and if the frequency does not exceed the predetermined threshold, using a formula to estimate the cardinality of the intermediate dataset, the formula accounting for data skew in the database table by subtracting the frequency of all values above the predetermined threshold in the frequent values list that satisfy the query from the total number of rows in the intermediate dataset.