Unraveling the Impact of Window Semantics: Optimizing Join Order for Efficient Stream Processing

Download PDF

Abstract

Window joins (WJs) are fundamental operators in stream processing systems (SPSs), enabling continuous, time-aware joins over unbounded data streams. Unlike time-agnostic relational joins, WJs incorporate temporal semantics associated with different window types (i.e., sliding, session, and interval windows), which introduce uncertainty in algebraic properties such as commutativity and associativity. As a result, state-of-the-art SPSs exploit only a single, fixed join order, which limits optimization opportunities and often leads to suboptimal performance. In this work, we eliminate this restriction by introducing three transformation rules that enable WJ reordering while preserving query semantics for those window types. Based on them, we propose WJR , an algorithm that systematically enumerates semantically equivalent join orders, expanding the search space for finding efficient WJ execution plans. Our evaluation shows speedups of up to 10 for multi-way WJ queries under various window configurations and rate ratios, highlighting the performance benefits of flexible join reordering in streaming queries.