Chain: operator scheduling for memory minimization in data stream systems

In many applications involving continuous data streams, data ar-rival is bursty and data rate fluctuates over time. Systems that seek to give rapid or real-time query responses in such an environment must be prepared to deal gracefully with bursts in data arrival with-out compromising system performance. We discuss one strategy for processing bursty streams — adaptive, load-aware scheduling of query operators to minimize resource consumption during times of peak load. We show that the choice of an operator schedul-ing strategy can have significant impact on the run-time system memory usage. We then present Chain scheduling, an operator scheduling strategy for data stream systems that is near-optimal in minimizing run-time memory usage for any collection of single-stream queries involving selections, projections, and foreign-key joins with stored relations. Chain scheduling also performs well for queries with sliding-window joins over multiple streams, and multiple queries of the above types. A thorough experimental eval-uation is provided where we demonstrate the potential benefits of Chain scheduling, compare it with competing scheduling strategies, and validate our analytical conclusions. 1