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: 13894
Venue: VLDB
Year: 2025
Pagerank: 4.1905499e-05
Overall Rank: 10,624 | 26.17%
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.0040465394
71	How Good Are Query Optimizers, Really?	2016	VLDB	0.00059446482
454	An Overview of Query Optimization in Relational Systems	1998	PODS	0.00022796106
536	The Dataflow Model: A Practical Approach to Balancing Correctness, Latency, and Cost in Massive-Scale, Unbounded, Out-of-Order Data Processing	2015	VLDB	0.00020651621
542	Apache Calcite: A Foundational Framework for Optimized Query Processing Over Heterogeneous Data Sources	2018	SIGMOD	0.00020522627
1,220	Rate-Based Query Optimization for Streaming Information Sources	2002	SIGMOD	0.00013214188
1,712	Approximate Join Processing Over Data Streams	2003	SIGMOD	0.00010786152
3,138	Scheduling for shared window joins over data streams	2003	VLDB	7.4919127e-05
5,091	Join Query Optimization Techniques for Complex Event Processing Applications	2018	VLDB	5.7010894e-05
5,131	One SQL to Rule Them All – an Efficient and Syntactically Idiomatic Approach to Management of Streams and Tables	2019	SIGMOD	5.6704313e-05
5,438	The NebulaStream Platform: Data and Application Management for the Internet of Things	2020	CIDR	5.5041764e-05
6,469	Parallel Index-based Stream Join on a Multicore CPU	2020	SIGMOD	5.0448159e-05
6,649	Grizzly: Efficient Stream Processing Through Adaptive Query Compilation	2020	SIGMOD	4.9724735e-05
6,760	AStream: Ad-hoc Shared Stream Processing	2019	SIGMOD	4.9304882e-05
7,316	Efficient Adaptive Detection of Complex Event Patterns	2018	VLDB	4.7594979e-05
8,004	Rethinking Stateful Stream Processing with RDMA	2022	SIGMOD	4.6048388e-05
8,618	CLASH: A High-Level Abstraction for Optimized, Multi-Way Stream Joins over Apache Storm	2019	SIGMOD	4.479438e-05
9,419	MuSE Graphs for Flexible Distribution of Event Stream Processing in Networks	2021	SIGMOD	4.3399748e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,163	Computing Complex Temporal Join Queries Efficiently	2022	SIGMOD	4.5685178e-05
6,871	State-Slice: New Paradigm of Multi-query Optimization of Window-based Stream Queries	2006	VLDB	4.8966771e-05
1,712	Approximate Join Processing Over Data Streams	2003	SIGMOD	0.00010786152
3,138	Scheduling for shared window joins over data streams	2003	VLDB	7.4919127e-05
4,139	Memory-Limited Execution of Windowed Stream Joins	2004	VLDB	6.4126764e-05
1,233	Maximizing the Output Rate of Multi-Way Join Queries over Streaming Information Sources	2003	VLDB	0.0001312635
4,526	Simplicity Done Right for Join Ordering	2021	CIDR	6.1079584e-05
11,710	Improving Join Reorderability with Compensation Operators	2018	SIGMOD	4.1905499e-05
2,124	Semantics and Evaluation Techniques for Window Aggregates in Data Streams	2005	SIGMOD	9.4824543e-05
3,664	Processing Sliding Window Multi-Joins in Continuous Queries over Data Streams	2003	VLDB	6.8645092e-05