System and method for data stream processing

• US 8,260,803 B2
• Filed: 10/19/2010
• Issued: 09/04/2012
• Est. Priority Date: 09/23/2010
• Status: Active Grant

• Current Assignee: Micro Focus LLC (Open Text Corporation)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Chen, Qiming, Hsu, Meichun
• Primary Examiner(s): LEROUX, ETIENNE PIERRE
• Application Number:
  US12/907,948
• Publication Number:
  US 20120078951A1
• Time in Patent Office: 686 Days
• Field of Search: 707/4, 707/769, 709/231, 717/115, 710/12
• US Class Current: 707/769
• CPC Class Codes: G06F 16/24532 of parallel queries
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries

Abstract

A method and system for processing a data stream are described. The method executes, until the occurrence of a cut condition, a map function from a set of query processing steps to generate map results for a first portion of the data stream, executes a reduce function from the set of query processing steps to generate history-sensitive data from the map results, and rewinds the set of query processing steps, without termination of processing. The history-sensitive data is maintained for a second execution of the map function and reduce function on a second portion of the data stream.

Claims

1. A method for processing a data stream using a map-reduce process, the method comprising:

executing, until the occurrence of a cut condition defining a partition of the data stream into portions including a first portion, a map function from a set of query processing steps, the map function mapping data into groups to be processed in parallel to generate map results for each group of data in the first portion of the data stream;

executing a reduce function from the set of query processing steps, the reduce function to aggregate the map results to generate history-sensitive data for the first portion; and

rewinding the set of query processing steps, without a termination of processing for a second execution of the map function and reduce function on a second portion of the data stream.

2. The method of claim 1, wherein a structured query language (SQL) query provides an expression of the map-reduce process.

3. The method of claim 2, wherein the SQL query includes an expression for a stream source function with a cut condition.

4. The method of claim 2, wherein the SQL query comprises an expression for a user-defined buffer function referencing a storage element for storing data.

5. The method of claim 1, wherein the history-sensitive data is stored in a storage element.

6. The method of claim 5, wherein the storage element is maintained as part of an application context of a processor of a query engine.

7. The method of claim 1, wherein the cut condition is signaled by a stream source function.

8. The method of claim 1, wherein the occurrence of the cut condition is determined by an item of data within the data stream.

9. The method of claim 1, where the occurrence of the cut condition is determined based on a time condition.

10. The method of claim 1, wherein the occurrence of the cut condition is based on data cardinality.

11. A system for processing a data stream comprising:

a first plurality of processing nodes for receiving a portion of the data stream, for processing a first part of said received portion using a cut condition to signal a halt in processing, and for forwarding processing results after halts in processing have been signaled at all of the first plurality of nodes; and

a second plurality of processing nodes for receiving the forwarded processing results,

wherein at least one of the second plurality of processing nodes generates an output, and processing is rewound at the first and second pluralities of nodes, without terminating processing, to maintain the output for processing a next part.

12. The system of claim 11, wherein each processing node of the first plurality of processing nodes processes the received data stream portion part-by-part in a plurality of parts.

13. The method of claim 11, wherein the first plurality of processing nodes execute a map function as part of a map-reduce process.

14. The method of claim 11, wherein the second plurality of nodes execute a reduce function as part of a mop-reduce process to process the forwarded processing results.

15. The method of claim 11, wherein the halts in processing are signaled by stream source function operators at the first plurality of nodes.

16. The method of claim 11, wherein an operator for a user-defined buffer function is used to maintain the output.

17. The method of claim 11, wherein the output comprises history-sensitive data.

18. The method of claim 11, wherein the portions of the data stream are formed by partitioning.

19. A non-transitory machine-readable medium having stored thereon instructions that if executed by a machine, result in:

executing, until the occurrence of a cut condition defining a partition of the data stream into portions including a first portion, a map function from a set of query processing steps, the map function mapping data into groups to be processed in parallel to generate map results for each group of data in the first portion of the data stream;

executing a reduce function from the set of query processing steps, the reduce function to aggregate the map results to generate history-sensitive data for the first portion; and

rewinding the set of query processing steps, without a termination of processing, for a second execution of the map function and reduce function on a second portion of the data stream using the history-sensitive data.

20. The machine-readable medium of claim 19, wherein said reduce function generates an additional result from the map results that is committed to a database before the second execution of the map function and reduce function.

21. A method for processing a data stream comprising:

extending a query engine to include a rewind function for continuously cycling through a set of set of query processing steps without terminating the cycle;

associating, with a query compiler, program code for a stream source function;

associating, with a query compiler, program code for a user-defined buffer function;

receiving a query containing expressions for the program codes for the stream source function and the user-defined buffer function;

processing the expressions to create a set of executable query processing steps comprising an executable stream source function and an executable user-defined buffer function; and

executing the executable query processing steps to process a data stream.

22. The method of claim 21, wherein the executable stream source function signals a cut condition in a first processing cycle, and the rewind function maintains a storage element of the executable user-defined buffer function while rewinding the query processing steps for a second processing cycle.

23. A method for processing a data stream comprising:

distributing, to a first node of a first plurality of nodes, an executable map function operator for mapping a data stream portion into groups to be processed in parallel and an executable stream source function operator;

distributing, to a second node of a second plurality of nodes, an executable reduce function operator for aggregating the map results of groups in the data stream portion, capable of accessing a storage element; and

processing a data stream according to a cycle,

wherein;

the first node forwards results from an execution of the map function operator to the second node after the stream source operator at the first node signals an occurrence of a cut condition defining a partition of the data stream into a portion,

the executable reduce function operator updates the storage element, and

the processing of the first and second pluralities of nodes is rewound while maintaining the updated storage element.

24. The method of claim 23, wherein the first and second pluralities of nodes are nodes within a parallel processing computer system.

25. The method of claim 23, where at least one of the map function operator, stream source function operator or reduce function operator is distributed in a sub-query.