Method and apparatus for estimating the number of occurrences of frequent values in a data set

A method of estimating the most frequently occurring values of query search keys in a data set located in data storage of a digital computer for use by a data base manager of the computer in retrieving values from the data storage in accordance with a user query, the method comprising the steps of:

• (1) for each value in the data set, repeating the processing steps of
• (a) obtaining a data set value from among the values stored in the data storage,
• (b) mapping the value to a bucket in respective hashing tables of data storage that are defined by each of at least two independent hashing functions and incrementing an associated bucket count of each bucket in the data storage,
• (c) designating the bucket a popular bucket if the incremented bucket count is one of the P highest bucket counts in the respective hashing table, where P is a predetermined popularity parameter,
• (d) detecting if the number of buckets in the data storage that are designated popular buckets is greater than the popularity parameter P and removing the designation of a previously designated different bucket as a popular bucket if the bucket count of the different bucket is the lowest among the popular buckets,
• (e) designating the value an active value if all of the buckets to which the value is mapped have been designated popular buckets and adding the value to a list of active values in the data storage that is associated with at least one of the hashing tables,
• (f) collecting predetermined statistical data in the data storage relating to the value if it was designated an active value at the step of designating active values or if it was previously designated an active value,
• until all values in the data set have been processed;
• (2) producing an estimate of the F most frequent values in the data set using the collected statistical data after all values in the data set have been processed, where F is a predetermined frequency estimator parameter;
• and
• (3) providing the estimated most frequent values to the data base manager for use in generating a query plan to retrieve values in the data set and return the retrieved values to an output device.

A computer combination having a central processor unit, data storage having a data set of values, and a data base management system having a data base manager that operates on the data set to retrieve values of query search keys in accordance with a user query, the combination including:

• at least two independent hashing functions maintained by the data base manager in the data storage of the computer that map the values of the data set to buckets of respective hashing tables in the data storage and increment a bucket count associated with each bucket when the respective function maps a value to the bucket;
• a query optimizer that determines a query 7plan to be followed by the data base manager in response to the user query;
• and
• a frequent values estimator, wherein for each value of the data set the frequent values estimator:
• determines if each bucket to which the value is mapped satisfies predetermined criteria for being a popular bucket, determines if the current value has been designated an active value, and maintains statistics on the value if it is active until all values of the data set have been mapped;
• and
• a report generator that determines the most frequent values in the data set and produces a report of the values to the query optimizer.

A frequent values estimator system for use in a computer system having a central processor unit, data storage having a data set of values, and a data base management system having a data base manager that operates on the data set to retrieve values of query search keys in accordance with a user query, the system including:

• at least two independent hashing functions, maintained by the data base manager in the data storage of the computer, that map the values of the data set to buckets of respective hashing tables in the data storage and, increment a bucket count associated with each bucket when a value is mapped to the bucket;
• a query optimizer that determines a search plan to be followed by the data base manager in response to the user query;
• a frequent values estimator, wherein for each value of the data set, the frequent values estimator:
• determines if each bucket to which the value is mapped satisfies predetermined criteria for being a popular bucket,
• determines if the current value has been designated an active value, and
• maintains statistics in the data storage relating to the value, if it is active, until all remaining values of the data set have been mapped;
• and
• a report generator that determines the estimated most frequent values in the data set and provides the determined values to the query optimizer for use by the query optimizer in determining the search plan.

A computer system comprising:

• a computer terminal that receives commands from a terminal user;
• a data storage unit that receives a data set having values of query search keys;
• a data base management system having a data base manager that operates on the data set to retrieve values from among the values in the data storage unit in accordance with a user query and that maintains at least two independent hashing functions that map the values of the data set to buckets of respective hashing tables in the data storage unit and increment a bucket count of the data storage unit associated with each bucket when a value is mapped to the bucket;
• query optimizer means for determining a query plan to be followed by the data base manager in response to the user query;
• frequent values estimator means for determining, for each value of the data set, if each bucket to which the value is mapped satisfies predetermined criteria for being a popular bucket, determining if the current value has been designated an active value, and maintaining statistics on the value if it is active, until all values of the data set have been mapped;
• and
• a report generator that determines the estimated most frequent values in the data set based on the statistics and produces a report of the values to the query optimizer means.