A Unified Architecture for Efficient Binary and Worst-Case Optimal Join Processing
Amirali Kaboli, Alex Mascolo, Amir Shaikhha · 2025
Read A Unified Architecture for Efficient Binary and Worst-Case Optimal Join Processing by Amirali Kaboli, Alex Mascolo, Amir Shaikhha (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-2505-19918.txt.
Introduction
Amirali Kaboli, Alex Mascolo, and Amir Shaikhha unify two families of database join algorithms in a 2025 computer science study. Joins combine tables, and hard queries can create intermediate results vastly larger than the final answer. Worst-case optimal algorithms avoid that blow-up in theory, while classic binary joins are fast and simple in practice, leaving engine builders torn.
A single architecture that runs both styles efficiently is the authors' goal. Switching strategy per query, inside one system, could give worst-case guarantees without giving up everyday speed. The design speaks to the core of every relational database engine.
Catalog record
| CREATOR | Amirali Kaboli, Alex Mascolo, Amir Shaikhha |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 58 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-19918
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Unified Architecture for Efficient Binary and Worst-Case Optimal Join Processing Amirali Kaboli, Alex Mascolo, Amir Shaikhha Abstract . Join processing is a fundamental operation in database management systems; however, traditional join algorithms often encounter efficiency challenges when dealing with complex queries that produce intermediate results much larger than the final query output. The emergence of worst-case optimal join (WCOJ) algorithms represents a significant advancement, offering asymptotically better performance by avoiding the enumeration of potentially exploding intermediate results. In this paper, we propose a unified architecture that efficiently supports both traditional binary joins and WCOJ processing. As opposed to the state-of-the-art, which only focuses on either hash-based or sort-based join implementations, our system accommodates both physical implementations of binary joins and WCOJ algorithms. Experimental evaluations demonstrate that our system achieves performance gains of up to 3.1 × 3.1\times (on average 1.5 × 1.5\times ) and 4.8 × 4.8\times (on average 1.4 × 1.4\times ) over the state-of-the-art implementation of Generic Join and Free Join methods, respectively, across acyclic and cyclic queries in standard query benchmarks. 1. Introduction Efficient query processing is essential for the performance of modern database management systems, particularly as the complexity and size of data continue to grow. Join operations, which combine records from multiple tables, play a pivotal role in this process; however, traditional join algorithms often face significant efficiency challenges when processing complex queries that produce intermediate results much larger than the final output. The emergence of worst-case optimal join (WCOJ) algorithms ( Ngo, 2018 ; Ngo et al., 2012 ; Veldhuizen, 2013 ; Ngo et al., 2014 ) represents a significant advancement, offering asymptotically better performance by avoiding the enumeration of potentially exploding intermediate results. It can be the case for both cyclic and acyclic queries as opposed to the common belief that WCOJ is designed for cyclic queries. There have been previous efforts ( Freitag et al., 2020 ; Aberger et al., 2017 ; Mhedhbi and Salihoglu, 2019 ) to adopt an approach where WCOJ algorithms are used for certain parts of a query while traditional join algorithms are applied to the rest. However, the use of two distinct algorithms within the same system introduces additional complexity, which has hindered the broader adoption of WCOJ methods. The current state-of-the-art system, and our main competitor in this work, is Free Join ( Wang et al., 2023 ) , which aims to address this challenge by unifying WCOJ with traditional join methods. Free Join provides a platform capable of executing a wide range of join queries, offering performance benefits in both WCOJ and traditional join scenarios. However, despite these advances, Free Join supports only a specific class of WCOJ algorithms–hash-based approaches–limiting its coverage and flexibility in handling other algorithmic paradigms such as sort-based joins. Our approach stands out by leveraging advancements in programming languages, specifically through the use of SDQL ( Shaikhha et al., 2022 ) , an intermediate language designed for functional collection programming using semi-ring dictionaries. By employing SDQL as our intermediate representation, we can translate worst-case optimal join (WCOJ) queries into an intermediate representation that can be directly compiled into highly efficient C++ code. This gives our system a key advantage in flexibility and performance optimization. The use of SDQL enables us to introduce a unified architecture that efficiently supports both traditional binary joins and WCOJ algorithms. Moreover, our system can handle hash-based and sort-based paradigms of WCOJ processing, significantly improving over state-of-the-art systems such as Free Join. Existing systems typically only focus on one approach – either hash-based or sort-based – while we provide support for both, ensuring that our system can adapt to various input data types and query execution scenarios. This broad capability enhances the versatility and overall performance of our system across a wide range of join queries. We demonstrate that our system not only matches but also outperforms the performance of the Free Join framework as the state-of-the-art. In this paper, we present the following contributions: (1) A unified architecture that integrates both efficient binary join and WCOJ processing (Section 3 ). (2) A comprehensive set of optimizations that refine our initial implementation into a highly optimized system (Sections 4.1 and 4.2 ). (3) A novel hybrid approach, along with support for sort-based WCOJ algorithms, leverages the strengths of both hash-based and sort-based paradigms (Section 4.3 ). (4) A detailed experimental evaluation of our system and the applied optimizations (Section 5 ). Specifically, we show that our method achieves speedups of up to 3.1\times and 4.8\times compared to the Generic Join and Free Join implementations within the Free Join framework, respectively. 2. Background A full conjunctive query is expressed in the form shown in Eq ( 1 ). In this notation, each term R_{i}(x_{i}) is referred to as an atom, where R_{i} represents a relation name, and x_{i} is a tuple of variables. The query is considered full because the head variables x encompass all variables that appear in the atoms. We assume that selections have been pushed down to the base tables, meaning that each atom R_{i} may already incorporate a selection over a base relation. Similarly, projections and aggregations are performed only after the full join operation is executed, and hence, they are not explicitly included in Eq ( 1 ). (1) Q(x):-R_{1}(x_{1}),\dotsc,R_{m}(x_{m}) Example. Throughout this paper, we will make use of a conjunctive query referred to as Q_{\clubsuit} , denoted in Eq ( 2 ). (2) Q_{\clubsuit}(x,a,b):-R(x,a),S(x,b),T(x) The SQL query of Q_{\clubsuit} is as below and its corresponding implementation using binary joins in SDQL and C++ is shown in Figure 2.1 . ⬇ SELECT * FROM R , S , T WHERE R . x = S . x AND R . x = T . x AND S . x = T . x 2.1. Generic Join The Generic Join algorithm, first introduced in ( Ngo et al., 2014 ) , represents the simplest worst-case optimal join algorithm. It builds upon the earlier Leapfrog Triejoin algorithm ( Veldhuizen, 2013 ) . The Generic Join algorithm computes the query Q from Eq ( 1 ) by executing a series of nested loops, where each loop iterates over a specific query variable. In particular, Generic Join arbitrarily selects a variable x , computes the intersection of all x -columns across the relations that contain x , and for each value \theta in this intersection, it evaluates the residual query Q[x/\theta] . In the residual query, every relation R containing x is replaced by \sigma_{x=\theta}(R) (or equivalently R[\theta] ). If the query Q contains k variables, the algorithm proceeds with k nested loops. In the innermost loop, Generic Join outputs a tuple consisting of constants derived from each iteration. The Generic Join algorithm is provably worst-case optimal, achieving a time complexity of O(n^{1.5}) , where n represents the maximum possible size of the output ( Ngo et al., 2014 ; Atserias et al., 2013 ) . In contrast, binary join algorithms can exhibit a time complexity of O(n^{2}) . While binary joins rely on hash tables for efficiency, Generic Join leverages a hash trie structure for each relation in the query. A hash trie is a tree structure where each node is either a leaf node