An Overview of Large-Scale Stream Processing Engines - Large Scale and Big Data: Processing and Management - page 390

Input data
streams

Output to
applications

Operator boxes

Continuous and
ad hoc queries

Historical
storage

FIGURE 12.1 The system of Aurora.

• Filter : This operator is used to route input tuples to alternative streams. It

takes the form Filter ( P 1 ,..., P m )( S ) such that P 1 ,..., P m are predicates over
tuples on the input stream, S . Its output consists of m + 1 streams ( S 1 ,..., S m +1 )
such that the tuples on the input stream that satisfy predicate P 1 are the output
on the first output stream, tuples on the input stream that satisfy predicate P 2
(but not P 1 ) are output on the second output stream, and so on. The ( m + 1)
stream contains all tuples satisfying none of the predicates. The output tuples
of the Filter operator have the same schema and values as input tuples.

• Map : This is a generalized projection operator that takes the form Map ( B 1 =

F 1 ,..., B m = F m )( S ) such that B 1 ,..., B m are names of attributes and F 1 ,..., F m are
functions over tuples on the input stream, S. Map outputs a stream consist-
ing of tuples of the form ( TS = t.TS,B 1 = F 1 ( t ),..., B m = Fm ( t )) for each input
tuple, t . The resulting stream of this operator can have a different schema
than the input stream, but the timestamps of input tuples are preserved in
corresponding output tuples.

• Union : This operator is used to merge two or more streams into a single out-

put stream and takes the form Union ( S 1 ,..., S n ) such that S 1 ,..., S n are streams
with a common schema. Union can output tuples in any order, though one
obvious processing strategy is to emit tuples in the order in which they
arrive regardless of which input stream they arrive on.

• BSort : This is an approximate sort operator that takes the form BSort

(Assuming O) (S)suchthatO = Order (On A, Slack n, GroupBy B 1 ,..., B m ) ,
which is a specification of the assumed ordering over the output stream.
While a complete sort is not possible over an infinite stream with finite time
or space, BSort performs a buffer-based approximate sort equivalent to n
passes of a bubble sort where slack = n . This is achieved by maintaining
a buffer of n + 1 tuples while processing the input stream. Every time the
buffer is filled, a tuple in the buffer with minimal value for A is evicted from
the buffer and emitted as output.

• Aggregate : This operator applies “window functions” to sliding windows

over its input stream. It has the form Aggregate (F, Assuming O, Size s,
Advance i) (S) such that F is a window function, O = Order (On A, Slack
n, GroupBy B 1 ,..., B m ) is an order specification over input stream S , s is the
size of the window, and i is an integer or predicate that specifies how to