ESTIMATION OF UNIQUE DATABASE VALUES

• US 20120084287A1
• Filed: 09/30/2010
• Published: 04/05/2012
• Est. Priority Date: 09/30/2010
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Lakshminarayan, Choudur, Kosuru, Ramakumar
• Granted Patent: US 8,549,004 B2
• Time in Patent Office: Days
• US Class Current: 707/737
• CPC Class Codes: G06F 16/24545 Selectivity estimation or determination
• CPC Class Codes: G06F 16/2462 Approximate or statistical queries

Abstract

Estimation of unique values in a database can be performed where a data field having multiple information values is provided in the database. The data field can be partitioned into multiple intervals such that each interval includes a range of information values. An interval specific Bloom filter can be calculated for each of the multiple intervals. A binary Bloom filter value can be calculated for an information value within an interval specific Bloom filter. The binary Bloom filter value can represent whether the information value is unique. A number of unique values in the database can be determined based on calculated binary Bloom filter values.

Claims

1. A method for estimating unique values in a database, comprising:

providing a data field in the database, the data field comprising a plurality of information values;

partitioning the data field into a plurality of intervals, each interval comprising a range of information values from the plurality of information values;

computing an interval specific Bloom filter for each of the plurality of intervals using a processor;

calculating a binary Bloom filter value for an information value within an interval specific Bloom filter, wherein the binary Bloom filter value represents whether information values are unique; and

determining a number of unique values in the database based on calculated binary Bloom filter values.

2. A method as in claim 1, further comprising storing the interval specific Bloom filter for each of the plurality of intervals.

3. A method as in claim 2, further comprising:

adding a second data field to the database;

partitioning the second data field into intervals;

loading a corresponding interval specific Bloom filter;

calculating a binary Bloom filter value for an information value within an interval associated with an interval specific Bloom filter from the second data field, wherein the binary Bloom filter value represents whether the information value is unique; and

determining a number of unique values in the database based on calculated binary Bloom filter values.

4. A method as in claim 1, further comprising generating a histogram based on the number of unique values.

5. A method as in claim 1, further comprising incrementally determining a number of unique values in the database when a second data field is added to the database.

6. A method as in claim 1, further comprising:

loading the data field into the database using a data loader performing a load process; and

estimating the number of unique values in the data field during the load process.

7. A method as in claim 1, further comprising calculating a false positive probability of whether the binary Bloom filter value is accurate.

8. A system for estimating unique values in a database, comprising:

a database in communication with the information server and configured to store the information values received over a computing network;

a data loader configure load the information values from the computing network to the database to be stored;

a data partitioning module configured to partition the information values into intervals;

a Bloom filter module configured to compute an interval specific Bloom filter for the intervals;

a unique value calculation module configured to calculate a binary Bloom filter value for an information value within an interval specific Bloom filter, wherein the binary Bloom filter value represents whether the information value is unique; and

an estimation module configured to estimate a number of unique values in the database based on calculated binary Bloom filter values.

9. A system as in claim 8, further comprising a histogram module configured to generate a histogram based on the estimation of the number of unique values.

10. A system as in claim 8, wherein the estimation module further comprises an incrementation module configured to incrementally estimate a number of unique values in the database when additional data values are added to the database.

11. A system as in claim 8, further comprising a Bloom filter repository in communication with the information server and configured to store the interval specific Bloom filters.

12. A system as in claim 11, wherein the Bloom filter module is further configured to reuse a stored interval specific Bloom filter when additional data values are added to the intervals in the database.

13. A method for estimating unique values in a database, comprising:

storing a data field in the database, the data field comprising a plurality of information values;

partitioning the data field into a plurality of intervals, each interval comprising a range of information values from the plurality of information values;

applying a hash function on an information value in an interval;

evaluating whether a result of the hash function returns a value of zero;

determining whether the information value when subjected to a Bloom filter is a unique value based on the result of the hash function returning a value of one;

calculating a false positive probability of the information value being a unique value.

14. A method as in claim 13, further comprising determining the number of bits to include in the Bloom filter.

15. A method as in claim 14, further comprising increasing an available computing memory used by the Bloom filter to increase accuracy of the Bloom filter.