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

Summary: Window joins (WJs) lose commutativity/associativity due to temporal window semantics, so SPSs resort to a fixed join order and forgo optimization. We propose three semantics-preserving transformations and WJR to enumerate equivalent WJ orders, finding better plans and achieving up to 10× speedups across window types and workload rates. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 13893
Venue: VLDB
Year: 2025
Pagerank: 4.1945683e-05
Overall Rank: 10,616 | 26.15%
DOI: 10.14778/3742728.3742741

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 18 of 18 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
1	Access Path Selection in a Relational Database Management System	1979	SIGMOD	0.0040449103
71	How Good Are Query Optimizers, Really?	2016	VLDB	0.00059038975
454	An Overview of Query Optimization in Relational Systems	1998	PODS	0.00022734812
538	The Dataflow Model: A Practical Approach to Balancing Correctness, Latency, and Cost in Massive-Scale, Unbounded, Out-of-Order Data Processing	2015	VLDB	0.00020678804
544	Apache Calcite: A Foundational Framework for Optimized Query Processing Over Heterogeneous Data Sources	2018	SIGMOD	0.00020521965
1,219	Rate-Based Query Optimization for Streaming Information Sources	2002	SIGMOD	0.00013223888
1,717	Approximate Join Processing Over Data Streams	2003	SIGMOD	0.00010793312
3,126	Scheduling for shared window joins over data streams	2003	VLDB	7.5046934e-05
5,097	Join Query Optimization Techniques for Complex Event Processing Applications	2018	VLDB	5.7011496e-05
5,130	One SQL to Rule Them All – an Efficient and Syntactically Idiomatic Approach to Management of Streams and Tables	2019	SIGMOD	5.6755067e-05
5,427	The NebulaStream Platform: Data and Application Management for the Internet of Things	2020	CIDR	5.509468e-05
6,476	Parallel Index-based Stream Join on a Multicore CPU	2020	SIGMOD	5.0496617e-05
6,648	Grizzly: Efficient Stream Processing Through Adaptive Query Compilation	2020	SIGMOD	4.9771723e-05
6,759	AStream: Ad-hoc Shared Stream Processing	2019	SIGMOD	4.9352213e-05
7,318	Efficient Adaptive Detection of Complex Event Patterns	2018	VLDB	4.7638874e-05
8,001	Rethinking Stateful Stream Processing with RDMA	2022	SIGMOD	4.6092573e-05
8,621	CLASH: A High-Level Abstraction for Optimized, Multi-Way Stream Joins over Apache Storm	2019	SIGMOD	4.4837361e-05
9,413	MuSE Graphs for Flexible Distribution of Event Stream Processing in Networks	2021	SIGMOD	4.3441378e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,159	Computing Complex Temporal Join Queries Efficiently	2022	SIGMOD	4.5729025e-05
6,753	State-Slice: New Paradigm of Multi-query Optimization of Window-based Stream Queries	2006	VLDB	4.9387235e-05
1,717	Approximate Join Processing Over Data Streams	2003	SIGMOD	0.00010793312
3,126	Scheduling for shared window joins over data streams	2003	VLDB	7.5046934e-05
4,133	Memory-Limited Execution of Windowed Stream Joins	2004	VLDB	6.4196026e-05
1,233	Maximizing the Output Rate of Multi-Way Join Queries over Streaming Information Sources	2003	VLDB	0.0001313363
4,523	Simplicity Done Right for Join Ordering	2021	CIDR	6.1135504e-05
11,705	Improving Join Reorderability with Compensation Operators	2018	SIGMOD	4.1945683e-05
2,101	Semantics and Evaluation Techniques for Window Aggregates in Data Streams	2005	SIGMOD	9.5429492e-05
3,656	Processing Sliding Window Multi-Joins in Continuous Queries over Data Streams	2003	VLDB	6.8714509e-05