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

Summary: Introduces three semantics-preserving rewrite rules for reordering sliding, session, and interval window joins despite weakened algebraic properties. WJR enumerates equivalent multiway join orders, yielding up to 10× speedups over fixed-order stream plans. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 14081
Venue: VLDB
Year: 2025
Pagerank: 5.093636e-05
Overall Rank: 10,873 | 25.41%
DOI: 10.14778/3742728.3742741

Incoming Non-self Citations Over Time

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

Authors

1. Ariane Ziehn (Berlin Institute for the Foundations of Learning and Data; Technical University of Berlin)
2. Jan Szlang (Snowflake)
3. Steffen Zeuch (Berlin Institute for the Foundations of Learning and Data; Technical University of Berlin)
4. Volker Markl (Berlin Institute for the Foundations of Learning and Data; Technical University of Berlin)

BibTeX Citation

@article{ziehn_vldb25,
        title = {{Unraveling the Impact of Window Semantics: Optimizing Join Order for Efficient Stream Processing}},
        author = {Ziehn, Ariane and Szlang, Jan and Zeuch, Steffen and Markl, Volker},
        journal = {PVLDB},
        series = {{VLDB} '25},
        volume = {18},
        number = {8},
        pages = {2468--2481},
        doi = {10.14778/3742728.3742741},
        url = {https://doi.org/10.14778/3742728.3742741},
        year = {2025}
}

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.0024089429
18	How Good Are Query Optimizers, Really?	2016	VLDB	0.00059284255
290	An Overview of Query Optimization in Relational Systems	1998	PODS	0.0002227038
361	The Dataflow Model: A Practical Approach to Balancing Correctness, Latency, and Cost in Massive-Scale, Unbounded, Out-of-Order Data Processing	2015	VLDB	0.00020138717
445	Apache Calcite: A Foundational Framework for Optimized Query Processing Over Heterogeneous Data Sources	2018	SIGMOD	0.00018336751
1,016	Rate-Based Query Optimization for Streaming Information Sources	2002	SIGMOD	0.00012645699
1,397	Approximate Join Processing Over Data Streams	2003	SIGMOD	0.00010906135
2,735	Scheduling for shared window joins over data streams	2003	VLDB	8.1896124e-05
4,588	Join Query Optimization Techniques for Complex Event Processing Applications	2018	VLDB	6.6167545e-05
4,907	One SQL to Rule Them All – an Efficient and Syntactically Idiomatic Approach to Management of Streams and Tables	2019	SIGMOD	6.4494002e-05
5,215	The NebulaStream Platform: Data and Application Management for the Internet of Things	2020	CIDR	6.3124972e-05
6,012	Parallel Index-based Stream Join on a Multicore CPU	2020	SIGMOD	6.0102675e-05
6,349	Grizzly: Efficient Stream Processing Through Adaptive Query Compilation	2020	SIGMOD	5.9049304e-05
6,482	AStream: Ad-hoc Shared Stream Processing	2019	SIGMOD	5.8668582e-05
7,103	Efficient Adaptive Detection of Complex Event Patterns	2018	VLDB	5.7023779e-05
7,814	Rethinking Stateful Stream Processing with RDMA	2022	SIGMOD	5.5389009e-05
8,607	CLASH: A High-Level Abstraction for Optimized, Multi-Way Stream Joins over Apache Storm	2019	SIGMOD	5.4026249e-05
9,564	MuSE Graphs for Flexible Distribution of Event Stream Processing in Networks	2021	SIGMOD	5.2528121e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,235	Computing Complex Temporal Join Queries Efficiently	2022	SIGMOD
2	6,528	State-Slice: New Paradigm of Multi-query Optimization of Window-based Stream Queries	2006	VLDB
3	1,397	Approximate Join Processing Over Data Streams	2003	SIGMOD
4	2,735	Scheduling for shared window joins over data streams	2003	VLDB
5	3,657	Memory-Limited Execution of Windowed Stream Joins	2004	VLDB
6	1,093	Maximizing the Output Rate of Multi-Way Join Queries over Streaming Information Sources	2003	VLDB
7	3,959	Simplicity Done Right for Join Ordering	2021	CIDR
8	11,909	Improving Join Reorderability with Compensation Operators	2018	SIGMOD
9	1,703	Semantics and Evaluation Techniques for Window Aggregates in Data Streams	2005	SIGMOD
10	3,255	Processing Sliding Window Multi-Joins in Continuous Queries over Data Streams	2003	VLDB