One Join Order Does Not Fit All: Reducing Intermediate Results with Per-Split Query Plans
Yujun He 1,2∗ , Hangdong Zhao 3 , Simon Frisk 1 , Yifei Yang 1 , Kevin Kristensen 1 Paraschos Koutris 1 , Xiangyao Yu 1 · 2025
Read One Join Order Does Not Fit All: Reducing Intermediate Results with Per-Split Query Plans by Yujun He 1,2∗ , Hangdong Zhao 3 , Simon Frisk 1 , Yifei Yang 1 , Kevin Kristensen 1 Paraschos Koutris 1 , Xiangyao Yu 1 (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-25684.txt.
Introduction
Yujun He led six co-authors presenting SplitJoin. Hangdong Zhao, Simon Frisk, and Yifei Yang helped. Kevin Kristensen, Paraschos Koutris, and Xiangyao Yu joined. Their 2025 paper reduces intermediate results in database joins. Minimizing intermediates is critical for multi-join query processing. The Yannakakis method guarantees acyclic query efficiency. Cyclic queries remain an open challenge for processing.
SplitJoin presents split as first-class query operator. Input tables partition into heavy and light parts. Varied partitions can use distinct query plans. Current binary join engines execute those plans. Intermediate sizes shrink using that partition flexibility. Design space includes thresholds, strategies, and join ordering. Implementation fronts DuckDB and Umbra database systems. On DuckDB, more social network queries completed. Runtime better over twofold on average there. Intermediates shrank nearly eightfold on average too. Umbra showed smaller but consistent improvements overall. Per-split plans beat one universal join order.
Catalog record
| CREATOR | Yujun He 1,2∗ , Hangdong Zhao 3 , Simon Frisk 1 , Yifei Yang 1 , Kevin Kristensen 1 Paraschos Koutris 1 , Xiangyao Yu 1 |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 75 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-25684
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
One Join Order Does Not Fit All: Reducing Intermediate Results with Per-Split Query Plans Thanks: ∗ Work done while interning at the University of Wisconsin–Madison. Yujun He 1,2∗ , Hangdong Zhao 3 , Simon Frisk 1 , Yifei Yang 1 , Kevin Kristensen 1 Paraschos Koutris 1 , Xiangyao Yu 1 Abstract . Minimizing intermediate results is critical for efficient multi-join query processing. Although the seminal Yannakakis algorithm offers strong guarantees for acyclic queries, cyclic queries remain an open challenge. In this paper, we propose SplitJoin , a framework that introduces split as a first-class query operator. By partitioning input tables into heavy and light parts, SplitJoin allows different data partitions to use distinct query plans, with the goal of reducing intermediate sizes using existing binary join engines. We systematically explore the design space for split-based optimizations, including threshold selection, split strategies, and join ordering after splits. Implemented as a front-end to DuckDB and Umbra, SplitJoin achieves substantial improvements: on DuckDB, SplitJoin completes 43 social network queries (vs. 29 natively), achieving 2.1 × \times faster runtime and 7.9 × \times smaller intermediates on average (up to 13.6 × \times and 74 × \times , respectively); on Umbra, it completes 45 queries (vs. 35), achieving 1.3 × \times speedups and 1.2 × \times smaller intermediates on average (up to 6.1 × \times and 2.1 × \times , respectively). † † This work is licensed under the Creative Commons BY-NC-ND 4.0 International License. Visit https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a copy of this license. For any use beyond those covered by this license, obtain permission by emailing [email protected] . Copyright is held by the owner/author(s). Publication rights licensed to the VLDB Endowment. Proceedings of the VLDB Endowment, Vol. 14, No. 1 ISSN 2150-8097. doi:XX.XX/XXX.XX PVLDB Artifact Availability: The source code, data, and/or other artifacts have been made available at https://github.com/hyj2003/SplitJoin . 1. Introduction Minimizing intermediate join results has been a crucial goal for achieving good performance for multi-join queries. For acyclic queries, the seminal Yannakakis algorithm ( Yannakakis 1981 ) can provably guarantee intermediate table sizes of at most O(N+OUT) , where N and OUT are the sizes of query input and output, respectively. This can lead to fast and robust query plans in practical systems ( Yang et al. 2024 ; Zhao et al. 2025 ; Yang and Yu 2025 ; Wang et al. 2025 ) . For cyclic queries, however, the intermediate table sizes can be much larger than the Yannakakis bound, and thus are challenging to minimize in both theory and practical systems. Prior work has extensively studied how to address the inefficiency of binary join plans on cyclic queries and skewed data (i.e., some values appear many times in a column). Worst-case optimal join (WCOJ) algorithms ( Veldhuizen 2014 ; Ngo et al. 2018 ; Salihoglu 2023 ) guarantee runtimes bounded by the maximum possible output size, thereby avoiding the quadratic intermediate blow-ups that can arise in traditional plans. For instance, in the triangle query, a binary join plan may generate \Theta(N^{2}) intermediate tuples, while a WCOJ algorithm completes in O(N^{1.5}) time. Despite this theoretical elegance, WCOJ has not been widely adopted in practice: binary joins remain dominant after decades of engineering optimization, WCOJ implementations typically rely on complex indexing structures, and efficient parallelization is challenging even with recent advances such as HoneyComb ( Wu and Suciu 2025 ) . Complementary to WCOJs, another line of theoretical work investigates partition-based strategies ( Khamis et al. 2025 ; Deep et al. 2020 ; Deep et al. 2024 ; Hu 2024 ) . These algorithms mitigate skew directly by separating heavy and light values in the join key domains and evaluating them under different subplans. By isolating values with high occurrence, partitioning provides finer control over join orders and reduces intermediate result sizes. In the triangle query, for example, partitioning can also guarantee a O(N^{1.5}) bound on intermediate results. Although these strategies are theoretically powerful, their adoption in real systems remains limited due to the complexity of existing approaches ( Khamis et al. 2025 ) , leaving a gap between theory and practice. Building on the above insights, we take the initial step toward making partition-based strategies practical. Our goal is to bridge the gap between theoretical advances and real-world query engines. To achieve this, we propose SplitJoin , which introduces split as a first-class operator in query processing. The split operator partitions an input table R into a light table ( R_{L} ) and a heavy table ( R_{H} ), which are then processed with potentially different query plans. SplitJoin can substantially reduce intermediates without requiring new data structures like in existing WCOJ algorithms. In this paper, we systematically explore how splits can be incorporated into traditional execution frameworks during query planning. Our first contribution is a general framework (Section 3 ) that incorporates split as a first-class citizen in a query plan. This framework reveals a rich design space with several key dimensions, including which table(s) to split, on which attributes to split, how to determine the appropriate split thresholds, and how to decide the best join order on each part of the partition. From a theoretical perspective, we show in Section 4 that our framework can be used to create a large class of provably worst-case optimal algorithms for queries on binary relations that all have the same cardinality. However, achieving this requires strict rules on how to split and which join orders to use. To improve practical performance, we relax these rules in favor of heuristics. From a practical perspective, we implement an instantiation of our framework as SplitJoin (Section 5 ), a front-end layer that can work for any SQL database: it takes a join query as input, generates an optimized query that incorporates split operators where appropriate, and submits it to the underlying database engine for execution. This design allows SplitJoin to take advantage of the existing query processing infrastructure that may support only binary joins while transparently introducing split-based optimizations. We conduct experiments by placing this layer in front of two state-of-the-art databases, DuckDB ( Raasveldt and Mühleisen 2020 ) and Umbra ( Freitag et al. 2020 ) , and evaluate on commonly used social network datasets, which often exhibit data skew and cyclic query patterns. Our experiments demonstrate that SplitJoin significantly reduces intermediate result sizes and improves query execution time, while preserving the efficiency of carefully optimized binary joins. In particular, DuckDB with SplitJoin successfully completes 43 queries compared to 29 with native DuckDB, and Umbra with SplitJoin completes 45 queries compared to 35 with native Umbra. For the subset of queries that can finish both with and without SplitJoin , SplitJoin delivers substantial improvements: on DuckDB, queries are 2.1 \times faster and produce 7.9 \times smaller intermediates on average (up to 13.6 \times and 74 \times , respectively); on Umbra, it achieves 1.3 \times speedups and 1.2 \times smaller intermediates on average (up to 6.1 \times and 2.1 \times , respectively). Notably, for all query plans generated by SplitJoin in our experiments, we have manually checked and verified that they are provably worst-case optimal, demonstrating that our proposed heuristics work well for the tested queries and data. The remainder of this paper is