System and Method for Analyzing Data Records

• US 20120215787A1
• Filed: 02/28/2012
• Published: 08/23/2012
• Est. Priority Date: 06/18/2004
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Pike, Robert C., Quinlan, Sean, Dorward, Sean M., Dean, Jeffrey, Ghemawat, Sanjay
• Granted Patent: US 9,405,808 B2
• Time in Patent Office: Days
• US Class Current: 707/741
• CPC Class Codes: G06F 11/1482 by means of middleware or OS functionality
• CPC Class Codes: G06F 16/1858 Parallel file systems, i.e. file systems supporting multiple processors
• CPC Class Codes: G06F 16/24561 Intermediate data storage techniques for performance improvement
• CPC Class Codes: G06F 16/2471 Distributed queries
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

A method and system for analyzing data records includes allocating groups of records to respective processes of a first plurality of processes executing in parallel. In each respective process of the first plurality of processes, for each record in the group of records allocated to the respective process, a query is applied to the record so as to produce zero or more values. Zero or more emit operators are applied to each of the zero or more produced values so as to add corresponding information to an intermediate data structure. Information from a plurality of the intermediate data structures is aggregated to produce output data.

Claims

1. A computer-implemented method of processing a plurality of data records, performed on a system having one or more processors and memory storing one or more programs for execution by the one or more processors to perform the method, comprising:

allocating subgroups of the plurality of data records to respective processes of a first plurality of processes;

after the allocating, executing in parallel, in each respective process of the first plurality of processes, operations comprising;

for at least one data record in at least a subset of the subgroups of data records allocated to the respective process;

extracting information from the at least one data record;

applying a script to the information to produce one or more values; and

storing the one or more values, or a calculation based upon the one or more values, in one or more intermediate data structures in a plurality of intermediate data structures; and

in each process of a second plurality of processes, aggregating values from a subset of the plurality of intermediate data structures to produce output data.

2. The computer-implemented method of claim 1, wherein an intermediate data structure in the plurality of intermediate data structures is a table having a plurality of indices.

3. The computer-implemented method of claim 1, wherein a data record in the plurality of data records comprises a log file, a transaction record or a document.

4. The computer-implemented method of claim 1, wherein an intermediate data structure in the plurality of intermediate data structures is a table having a plurality of indices, wherein at least a subset of the plurality of indices is dynamically generated when one or more values are stored in the intermediate data structure.

5. The computer-implemented method of claim 1, wherein an intermediate data structure in the plurality of intermediate data structures is a table, the method further comprising initializing the table, wherein the table comprises a plurality of indices that are statically generated when the table is initialized.

6. The computer-implemented method of claim 1, wherein the script comprises a processing function that is applied to the information.

7. The computer-implemented method of claim 6, wherein the processing function performs one or more of the following:

(i) collects or concatenates the one or more values,

(ii) analyzes the one or more values to obtain a predetermined number of highest-weighted items or values in the information for a predetermined key,

(iii) analyzes the one or more values to produce a sample of a predetermined number of the lowest-weighted items or values in the information for a predetermined key,

(iv) analyzes the one or more values to provide a statistical sampling of data for a predetermined key,

(v) analyzes the one or more values to derive a set of unique elements containing at most a predetermined number of items or values in the information for a predetermined key,

(vi) provides an arithmetic sum of the one or more values,

(vii) analyzes the one or more values to obtain a statistical estimate of a predetermined number of most frequent items or values in the information for a predetermined key, and

(viii) analyzes the one or more values to obtain a total number of unique items or values in the information for a predetermined key.

8. The computer-implemented method of claim 1, wherein

a first process in the first plurality of processes generates a first intermediate data structure in the plurality of intermediate data structure, the first intermediate data structure having a first key,

a second process in the first plurality of processes generates a second intermediate data structure in the plurality of intermediate data structures, the second intermediate data structure having a second key, wherein the first key and the second key are the same, and

a process in the second plurality of processes aggregates (i) values from the first intermediate data structure indexed to the first key and (ii) values from the second intermediate data structure indexed to the second key to produce all or a portion of the output data.

9. A system for processing data records, comprising:

one or more processors; and

memory storing one or more programs to be executed by the one or more processors;

the one or more programs comprising instructions for;

allocating subgroups of the plurality of data records to respective processes of a first plurality of processes;

after the allocating, executing in parallel, in each respective process of the first plurality of processes, operations comprising;

for at least one data record in at least a subset of the subgroups of data records allocated to the respective process;

extracting information from the at least one data record;

applying a script to the information to produce one or more values; and

storing the one or more values, or a calculation based upon the one or more values, in one or more intermediate data structures in a plurality of intermediate data structures; and

in each process of a second plurality of processes, aggregating values from a subset of the plurality of intermediate data structures to produce output data.

10. The system of claim 9, wherein an intermediate data structure in the plurality of intermediate data structures is a table having a plurality of indices.

11. The system of claim 9, wherein a data record in the plurality of data records comprises a log file, a transaction record or a document.

12. The system of claim 9, wherein an intermediate data structure in the plurality of intermediate data structures is a table having a plurality of indices, wherein at least a subset of the plurality of indices is dynamically generated when one or more values are stored in the intermediate data structure.

13. The system of claim 9, wherein an intermediate data structure in the plurality of intermediate data structures is a table, the method further comprising initializing the table, wherein the table comprises a plurality of indices that are statically generated when the table is initialized.

14. The system of claim 9, wherein the script comprises a processing function that is applied to the information.

15. A non-transitory computer readable storage medium storing one or more programs configured for execution by a computer, the one or more programs comprising instructions for:

allocating subgroups of the plurality of data records to respective processes of a first plurality of processes;

after the allocating, executing in parallel, in each respective process of the first plurality of processes, operations comprising;

for at least one data record in at least a subset of the subgroups of data records allocated to the respective process;

extracting information from the at least one data record;

applying a script to the information to produce one or more values; and

storing the one or more values, or a calculation based upon the one or more values, in one or more intermediate data structures in a plurality of intermediate data structures; and

in each process of a second plurality of processes, aggregating values from a subset of the plurality of intermediate data structures to produce output data.

16. The non-transitory computer readable storage medium of claim 15, wherein an intermediate data structure in the plurality of intermediate data structures is a table having a plurality of indices.

17. The non-transitory computer readable storage medium of claim 15, wherein a data record in the plurality of data records comprises a log file, a transaction record or a document.

18. The non-transitory computer readable storage medium of claim 15, wherein an intermediate data structure in the plurality of intermediate data structures is a table having a plurality of indices, wherein at least a subset of the plurality of indices is dynamically generated when one or more values are stored in the intermediate data structure.

19. The non-transitory computer readable storage medium of claim 15, wherein an intermediate data structure in the plurality of intermediate data structures is a table, the method further comprising initializing the table, wherein the table comprises a plurality of indices that are statically generated when the table is initialized.

20. The non-transitory computer readable storage medium of claim 15, wherein the script comprises a processing function that is applied to the information.