Parallel processing of continuous queries on data streams

A parallel data stream processing method executing continuous queries on a plurality of processing nodes, wherein a continuous query comprises a plurality of interconnected operators, each operator of the query being selectable between stateless operator and stateful operator, and the method comprises:

• (a) split a continuous query into at least two sub-queries, wherein each sub-query includes one stateful operator followed by at least a stateless operator, except a first sub-query which only contains stateless operators;
• (b) associating each sub-query to at least two processing nodes, wherein the each of the processing nodes is configured to execute an instance of the each sub-query;
• and wherein an executed sub-query generates at least one tuple;
• (c) labeling the tuples with an ordering label comprising a timestamp indicating a relative ordering among the tuples and used for ordering the tuples to a destination sub-query at an input merger located in the destination sub-query;
• (d) sending and receiving tuples across interconnected sub-queries, a source sub-query and a destination sub-query comprising interconnected operators between said sub-queries;
• wherein the sending and receiving of tuples comprise:
• for each processing node executing a source sub-query, a load balancer at an output of each instance of the source sub-query and every instance the source sub-query output is connected to an input of the load balancer and an output of the load balancer is connected to all instances of the destination sub-query;
• for each processing node executing an instance of the destination sub-query, receiving a plurality of generated tuples sent by each load balancer of every instance of the source sub-query by means of an input merger;
• each input merger waits to receive a tuple from the load balancer of the each instance of each source sub-query before forwarding the tuple with a smallest timestamp to the destination sub-query, and each load balancer stores the timestamp from a last generated tuple for each destination sub-query and if no tuple has been sent to the destination sub-query after a maximum prefixed period of time, then the load balancer is configured to send a dummy tuple with the same timestamp as the last tuple sent by the load balancer;
• wherein the load balancer is configured to determine the processing node to which a tuple is sent based at least in part on a key field contained in the tuple, the field called a key field destination sub-query input merger;
• and
• wherein in each sub-query an input merger at the beginning of each operator and a load balancer at the end of each operator are introduced, where the sub-query is executed;
• and
• wherein each load balancer of the source sub-query is connected to each input merger of the destination sub-query respectively to distribute the output tuples from the source sub-query to the destination sub-query, wherein each load balancer is configured to:
• either send tuples with a same key field to a same processing node executing the destination sub-query when the destination sub-query comprises one stateful operator, or
• send tuples to the destination sub-query in a round robin fashion when the destination sub-query comprises only stateless operators.