SYSTEM AND METHOD FOR DATA STREAM PROCESSING

• US 20120078951A1
• Filed: 10/19/2010
• Published: 03/29/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: HSU, Meichun, Chen, Qiming
• Granted Patent: US 8,260,803 B2
• Time in Patent Office: Days
• 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, a map function from a set of query processing steps to generate map results for a first portion of the data stream;

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

rewinding the set of query processing steps, without a termination of processing,

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

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 map-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 machine-readable medium having stored thereon instructions that, if executed by a machine, result in:

executing, 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;

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

rewinding the set of query processing steps, without a termination of processing,

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

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;

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 and an executable stream source function operator;

distributing, to a second node of a second plurality of nodes, an executable reduce function operator, 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,

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.