Scheduling for shared window joins over data streams

This chapter focuses on a fundamental problem that arises in Continuous Query (CQ) processing over data streams. It investigates the problem of scheduling multiple windowed joins over a common set of data streams. As in traditional query processing systems, join is a fundamental operator. In streaming systems, joins allow data from multiple streams to be combined for further processing, aggregation, and analysis. The role of joins in emerging CQ systems is further enhanced by the use of “selection pull up.” As demonstrated in the NiagaraCQ system, the traditional heuristic of pushing selection predicates below joins is often inappropriate for CQ systems because early selection destroys the ability to share subsequent join processing. Given the high cost of joins, it is often most efficient to process a join once and then send those results to the selection operators. Similar arguments also hold for group by and aggregation operators. The chapter describes and evaluates three scheduling algorithms that prioritize such shared execution to reduce the average response time per query while preserving their original semantics.