System and method for analyzing data records

• US 9,405,808 B2
• Filed: 02/28/2012
• Issued: 08/02/2016
• Est. Priority Date: 06/18/2004
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Ghemawat, Sanjay, Pike, Robert C., Quinlan, Sean, Dorward, Sean M., Dean, Jeffrey
• Primary Examiner(s): Trujillo, James
• Assistant Examiner(s): CHEUNG, HUBERT G
• Application Number:
  US13/407,632
• Publication Number:
  US 20120215787A1
• Time in Patent Office: 1,617 Days
• US Class Current: 1/1
• 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 computer-implemented 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, application-specific and application-independent 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, by using one or more application-specific data processing operators provided by an application programmer;

applying a multi-step script comprising a plurality of information processing commands applied sequentially to the extracted information to produce one or more values, wherein at least one step in the multi-step script includes selecting a respective application-independent emit operator on an application-specific basis and applying the respective application-independent emit operator to the information extracted from the at least one data record; and

storing 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 computer-implemented 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 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.

7. 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.

8. The computer-implemented method of claim 1, wherein selecting a respective application-independent emit operator on an application-specific basis is performed by a user.

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, application-specific and application-independent 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, by using one or more application-specific data processing operators provided by an application programmer;

applying a multi-step script comprising a plurality of information processing commands applied sequentially to the extracted information to produce one or more values, wherein at least one step in the multi-step script includes selecting a respective application-independent emit operator on an application-specific basis and applying the respective application-independent emit operator to the information extracted from the at least one data record; and

storing 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 instructions further comprising initializing the table, wherein the table comprises a plurality of indices that are statically generated when the table is initialized.

14. 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, application-specific and application-independent 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, by using one or more application-specific data processing operators provided by an application programmer;

applying a multi-step script comprising a plurality of information processing commands applied sequentially to the extracted information to produce one or more values, wherein at least one step in the multi-step script includes selecting a respective application-independent emit operator on an application-specific basis and applying the respective application-independent emit operator to the information extracted from the at least one data record; and

storing 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.

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

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

17. The non-transitory computer readable storage medium of claim 14, 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.

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