METHOD FOR PROCESSING STREAM DATA AND SYSTEM THEREOF

• US 20100106946A1
• Filed: 08/18/2009
• Published: 04/29/2010
• Est. Priority Date: 10/29/2008
• Status: Active Grant

• Current Assignee: Hitachi, Ltd.
• Original Assignee: Hitachi, Ltd.
• Inventors: IMAKI, Tsuneyuki, NISHIZAWA, Itaru, KASHIYAMA, Toshihiko
• Granted Patent: US 8,402,015 B2
• Time in Patent Office: Days
• US Class Current: 712/220
• CPC Class Codes: G06F 16/2453 Query optimisation
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries

Abstract

The present invention provides a method for processing stream data and a system thereof capable of implementing general data processing including recursive processing with low latency. In the system for processing stream data, a single operator graph is prepared from operator trees of a plurality of queries, an execution order of the operators is determined so that execution of a streaming operator is progressed in one way from an input to an output, the ignition time of an external ignition operator that inputs data from the outside of the system and an internal ignition operator that time-limitedly generates data is monitored, and an operator execution control unit repeats processing that completes the processing in the operator graph at the time according to the determined operator execution order, assuming the operator of the earliest ignition time as a start point.

Claims

1. A method for processing stream data assigning time stamps and processing a stream that is a flow of time series data arriving in an ascending order of the time stamps, the method comprising the steps of:

preparing operator trees assuming an operator, which is a basic data processing unit, as a node one by one, with respect to each of a plurality of queries in data processing defined by an interaction of the queries and constructing a single operator graph from the plurality of prepared operator trees;

assigning an operator execution order based on the inter-operator input and output relation so that an execution order assigned to operators on an output side is larger than an execution order of operators on an input side, with respect to all the operators on the operator graph;

extracting an external ignition operator that receives data from the outside of the operator graph and an internal ignition operator that time-limitedly outputs a keeping tuple, from the operator graph and preparing an ignition operator list;

extracting a set of the operators configured of ones having the earliest ignition time of the operator belonging to the ignition operator list and constructing an execution operator list, at an execution timing of the query; and

executing the operator where the operator execution order assigned to the operator is minimized among the operators belonging to the execution operator list.

2. The method for processing stream data according to claim 1, further comprising the steps of:

adding the operator of the output destination of the operator to the execution operator list, when a result tuple is generated by the execution of the operator; and

continuously executing the processing that executes the operator where the assigned operator execution order is minimized among the operators belonging to the execution operator list again until the execution operator list is empty.

3. The method for processing stream data according to claim 2, further comprising the step of continuously executing the repeating processing that extracts a set of the operators configured of ones having the earliest ignition time of the operator, among the operators belonging to the ignition operator list, at a timing when the execution operator list is empty.

4. A method for processing stream data assigning time stamps and processing a stream that is a flow of time series data arriving in an ascending order of the time stamps, the method comprising the steps of:

preparing operator trees assuming an operator, which is a basic data processing unit, as a node, with respect to each of a plurality of queries in data processing defined by an interaction of the queries and constructing a single operator graph from the plurality of prepared operator trees;

when the operator execution order is assigned for all the operators on the operator graph, simulating the operator graph to a directed graph having a directed side from an input side operator to an output side operator based on the inter-operator input and output relation, decomposing the directed graph into a set of strongly connected components and determining so that the operator execution order assigned to all the operators configuring an output side component is larger than the operator execution order assigned to all the operators configuring an input side component, based on the inter-component input and output relation belonging to the set of the strongly connected components;

extracting an external ignition operator that receives data from the outside of the operator graph and an internal ignition operator that time-limitedly outputs a keeping tuple, from the operator graph and preparing an ignition operator list; and

extracting a set of the operators configuring ones having the earliest ignition time of the operator belonging to the ignition operator list and constructing an execution operator list, at an execution timing of the query; and

executing the operator where the operator execution order assigned to the operator is minimized among the operators belonging to the execution operator list.

5. The method for processing stream data according to claim 4, further comprising the steps of:

selecting any one of the plurality of operators with respect to the component configured of the plurality of operators in the set of the strongly connected components and assuming it as a deployment point operator;

decomposing into the set of the strongly connected components, with respect to the directed graph deleting all the directed sides from the set of the strongly connected components to the deployment point operator and determining so that the operator execution order assigned to all the operators configuring the output side component is larger than the operator execution order assigned to any operator configuring the input side component based on the inter-component input and output relation belonging to the set of the strongly connected components; and

recursively determining the operator execution order by the same method until every element of the set of the strongly connected components becomes a single operator.

6. The method for processing stream data according to claim 5, further comprising the step of selecting a delay operator that shifts time stamps of each data of the stream arriving from a data source or the stream that is an output of the streaming operator and the delay operator to the future by a designated time, as the deployment point operator in the strongly connected component.

7. The method for processing stream data according to claim 6, further comprising the step of inserting the delay operator into an output destination of the streaming operator, when there is no delay operator in the plurality of operators, in the strongly connected component.

8. The method for processing stream data according to claim 6, further comprising the step of informing a user of a query definition error, when there is no delay operator in the plurality of operators, in the strongly connected component.

9. The method for processing stream data according to claim 6, wherein the delay operator shifts the time stamps of each data of the stream to the future by a virtual fine time on the data processing, in the strongly connected component.

10. A system for processing stream data assigning time stamps and processing a stream that is time series data arriving in an ascending order of the time stamps, the system comprising:

a network interface that receives the streams and a processing unit that processes the streams,

wherein the processing unit;

for each query, prepares an operator tree assuming an operator, which is a basic data processing unit, as a node one by one and constructs a single operator graph from the plurality of prepared operator trees; and

for all the operators on the operator graph, assigns an operator execution order based on the inter-operator input and output relation so that an execution order assigned to operators on an output side is larger than an execution order of operators on an input side.

11. The system for processing stream data according to claim 10,

wherein the processing unit:

extracts an external ignition operator that receives data from the outside of the operator graph and an internal ignition operator that time-limitedly outputs a keeping tuple from the operator graph, and constructs an ignition operator list;

extracts a set of the operators configured of ones having the earliest ignition time of the operator belonging to the ignition operator list and prepares an execution operator list, at an execution timing of the query; and

among the operators belonging to the execution operator list, executes the operator where the operator execution order assigned to the operator is minimized.

12. The system for processing stream data according to claim 11,

wherein the processing unit:

when a result tuple is generated by the execution of the operator, adds the operator of the output destination of the operator to the execution operator list;

among the operators belonging to the execution operator list, continuously executes the processing that executes the operator where the assigned operator execution order is minimized among the operators belonging to the execution operator list again until the execution operator list is empty; and

at a timing when the execution operator list is empty, among the operators belonging to the ignition operator list, continuously executes the repeating processing that extracts a set of the operators configured of ones having the earliest ignition time of the operator.

13. The system for processing stream data according to claim 11,

wherein the processing unit, when the operator execution order is determined, simulates the operator graph to a directed graph having a directed side from an input side operator to an output side operator based on the inter-operator input and output relation, decomposes the directed graph into a set of strongly connected components, and determines so that the operator execution order assigned to all the operators configuring an output side component is larger than the operator execution order assigned to any operator configuring an input side component, based on the inter-component input and output relation belonging to the set of the strongly connected components.

14. The system for processing stream data according to claim 13, wherein the processing unit selects a delay operator that shifts time stamps of each data of the stream arriving from a data source or the stream that is an output of the streaming operator and the delay operator to the future by a designated time, as the deployment point operator in the strongly connected component.

15. The system for processing stream data according to claim 14, wherein in the strongly connected component, when there is no delay operator in the plurality of operators, the delay operator is inserted into an output destination of the streaming operator.