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: hd969a3f15c613b2a
Venue: VLDB
Year: 2025
Pagerank: 4.9769913e-05
Overall Rank: 11,284 | 24.16%
DOI: 10.14778/3742728.3742741
PDF: Download (CC BY-NC-ND 4.0)

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.0023943337
15	How Good Are Query Optimizers, Really?	2016	VLDB	0.00061067652
272	An Overview of Query Optimization in Relational Systems	1998	PODS	0.0002251422
325	The Dataflow Model: A Practical Approach to Balancing Correctness, Latency, and Cost in Massive-Scale, Unbounded, Out-of-Order Data Processing	2015	VLDB	0.0002095522
379	Apache Calcite: A Foundational Framework for Optimized Query Processing Over Heterogeneous Data Sources	2018	SIGMOD	0.00019507406
1,030	Rate-Based Query Optimization for Streaming Information Sources	2002	SIGMOD	0.00012402072
1,431	Approximate Join Processing Over Data Streams	2003	SIGMOD	0.00010676907
2,782	Scheduling for shared window joins over data streams	2003	VLDB	8.0214634e-05
4,623	Join Query Optimization Techniques for Complex Event Processing Applications	2018	VLDB	6.4957114e-05
4,886	One SQL to Rule Them All – an Efficient and Syntactically Idiomatic Approach to Management of Streams and Tables	2019	SIGMOD	6.3680255e-05
5,349	The NebulaStream Platform: Data and Application Management for the Internet of Things	2020	CIDR	6.1679453e-05
6,125	Parallel Index-based Stream Join on a Multicore CPU	2020	SIGMOD	5.8761704e-05
6,444	Grizzly: Efficient Stream Processing Through Adaptive Query Compilation	2020	SIGMOD	5.7807677e-05
6,601	AStream: Ad-hoc Shared Stream Processing	2019	SIGMOD	5.737728e-05
7,251	Efficient Adaptive Detection of Complex Event Patterns	2018	VLDB	5.5719214e-05
7,980	Rethinking Stateful Stream Processing with RDMA	2022	SIGMOD	5.4120499e-05
8,778	CLASH: A High-Level Abstraction for Optimized, Multi-Way Stream Joins over Apache Storm	2019	SIGMOD	5.2789044e-05
9,744	MuSE Graphs for Flexible Distribution of Event Stream Processing in Networks	2021	SIGMOD	5.1325223e-05

Semantically Similar Papers

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