A Load Shedding Framework and Optimizations for M-way Windowed Stream Joins

Tuple dropping, though commonly used for load shedding in most stream operations, is inadequate for m-way, windowed stream joins. The join output rate can be overly reduced because it fails to exploit the time correlations likely to exist among interrelated streams. In this paper, the authors introduce GrubJoin: An adaptive, m-way, windowed stream join that effectively performs time correlation-aware CPU load shedding. GrubJoin maximizes the output rate by achieving near optimal window harvesting, which picks only the most profitable window segments for the join. Due to combinatorial explosion of possible m-way join sequences involving window segments, m-way, windowed stream joins pose several unique challenges.