Computing frequency distribution for many fields in one pass in parallel

• US 20070106666A1
• Filed: 11/10/2005
• Published: 05/10/2007
• Est. Priority Date: 11/10/2005
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Callen, Jerry, Beckerle, Michael
• Granted Patent: US 7,565,349 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

Provided are a techniques for determining a frequency distribution for a set of records. A count table of frequency distributions is built in memory for each field in the set of records, wherein each record of each count table includes a field identifier, a field value, and a count of a number of times the field value occurs in the set of records, and wherein the field identifier concatenated with the field value comprises a composite key value. It is determined that at least one count table of frequency distributions is approaching a maximum amount of memory allocated to that count table. The records of the at least one count table that is approaching the maximum amount of memory are sent for sorting and additional counting, wherein the records include composite key values.

Claims

1. A computer-implemented method for determining a frequency distribution for a set of records, comprising:

building a count table of frequency distributions in memory for each field in the set of records, wherein each record of each count table includes a field identifier, a field value, and a count of a number of times the field value occurs in the set of records, and wherein the field identifier concatenated with the field value comprises a composite key value;

determining that at least one count table of frequency distributions is approaching a maximum amount of memory allocated to that count table; and

sending the records of the at least one count table that is approaching the maximum amount of memory for sorting and additional counting, wherein the records include composite key values.

2. The method of claim 1, further comprising:

sorting the composite key values in the sent records based on the field identifier and the field value; and

outputting sorted composite key values.

3. The method of claim 2, further comprising:

for the sorted composite key values, for each composite key, updating a count of the number of times the field value occurs to generate a frequency distribution dataset.

4. The method of claim 1, wherein the building, determining, sending, sorting, and updating is performed in parallel.

5. The method of claim 1, wherein the frequency distribution dataset is generated without a priori knowledge of a number of distinct field values for each field identifier.

6. The method of claim 1, further comprising:

inverting a record from the set of records to form field identifier and field value records;

generating a composite key value for a field identifier and field value by concatenating the field identifier to the field value;

determining a partition for the composite key value by generating a hash value for the composite key value; and

sending the composite key value to a parallel processor based on the partition.

7. The method of claim 1, further comprising:

generating a field summary dataset based on the frequency distribution dataset.

8. The method of claim 1, further comprising:

extracting a field from the frequency distribution dataset; and

creating a new frequency distribution dataset.

9. A computer program product for determining a frequency distribution for a set of records, comprising a computer useable medium including a computer readable program, wherein the computer readable program when executed on a computer causes the computer to:

build a count table of frequency distributions in memory for each field in the set of records, wherein each record of each count table includes a field identifier, a field value, and a count of a number of times the field value occurs in the set of records, and wherein the field identifier concatenated with the field value comprises a composite key value;

determine that at least one count table of frequency distributions is approaching a maximum amount of memory allocated to that count table; and

send the records of the at least one count table that is approaching the maximum amount of memory for sorting and additional counting, wherein the records include composite key values.

10. The computer program product of claim 9, wherein the computer readable program when executed on a computer causes the computer to:

sort the composite key values in the sent records based on the field identifier and the field value; and

output sorted composite key values.

11. The computer program product of claim 10, wherein the computer readable program when executed on a computer causes the computer to:

for the sorted composite key values, for each composite key, update a count of the number of times the field value occurs to generate a frequency distribution dataset.

12. The computer program product of claim 9, wherein the building, determining, sending, sorting, and updating is performed in parallel.

13. The computer program product of claim 9, wherein the frequency distribution dataset is generated without a priori knowledge of a number of distinct field values for each field identifier.

14. The computer program product of claim 9, wherein the computer readable program when executed on a computer causes the computer to:

invert a record from the set of records to form field identifier and field value records;

generate a composite key value for a field identifier and field value by concatenating the field identifier to the field value;

determine a partition for the composite key value by generating a hash value for the composite key value; and

send the composite key value to a parallel processor based on the partition.

15. The computer program product of claim 9, wherein the computer readable program when executed on a computer causes the computer to:

generate a field summary dataset based on the frequency distribution dataset.

16. The computer program product of claim 9, wherein the computer readable program when executed on a computer causes the computer to:

extract a field from the frequency distribution dataset; and

create a new frequency distribution dataset.

17. A system for determining a frequency distribution for a set of records, comprising:

logic capable of performing operations, the operations comprising;

building a count table of frequency distributions in memory for each field in the set of records, wherein each record of each count table includes a field identifier, a field value, and a count of a number of times the field value occurs in the set of records, and wherein the field identifier concatenated with the field value comprises a composite key value;

determining that at least one count table of frequency distributions is approaching a maximum amount of memory allocated to that count table; and

sending the records of the at least one count table that is approaching the maximum amount of memory for sorting and additional counting, wherein the records include composite key values.

18. The system of claim 17, wherein the operations further comprise:

sorting the composite key values in the sent records based on the field identifier and the field value; and

outputting sorted composite key values.

19. The system of claim 18, wherein the operations further comprise:

for the sorted composite key values, for each composite key, updating a count of the number of times the field value occurs to generate a frequency distribution dataset.

20. The system of claim 17, wherein the building, determining, sending, sorting, and updating is performed in parallel.

21. The system of claim 17, wherein the frequency distribution dataset is generated without a priori knowledge of a number of distinct field values for each field identifier.

22. The system of claim 17, wherein the operations further comprise:

inverting a record from the set of records to form field identifier and field value records;

generating a composite key value for a field identifier and field value by concatenating the field identifier to the field value;

determining a partition for the composite key value by generating a hash value for the composite key value; and

sending the composite key value to a parallel processor based on the partition.

23. The system of claim 17, wherein the operations further comprise:

generating a field summary dataset based on the frequency distribution dataset.

24. The system of claim 17, wherein the operations further comprise:

extracting a field from the frequency distribution dataset; and

creating a new frequency distribution dataset.