In this article, we approach Free Join from the traditional perspective of binary joins, and re-derive the more general framework via a series of gradual transformations. We hope this perspective from the past can help practitioners better understand the Free Join framework, and find ways to incorporate some of the ideas into their own systems.
]]>Over the last decade, worst-case optimal join (WCOJ) algorithms [10,14,11,9] have emerged as a breakthrough in one of the most fundamental challenges in query processing: computing joins e ciently. Such an algorithm can be asymptotically faster than traditional binary joins, all the while remaining simple to understand and implement [11]. These algorithms opened up a flourishing field of research, leading to both theoretical results [11,6] and practical implementations [14,2,4,8].
Over time, a common belief took hold: "WCOJ is designed for cyclic queries". This belief is rooted in the observation that WCOJ enjoys lower asymptotic complexity than traditional algorithms for cyclic queries [11], but when the query is acyclic, classic algorithms like the Yannakakis algorithm [16] are already asymptotically optimal. Moreover, traditional binary join algorithms have benefited from decades of research and engineering. Techniques like columnoriented layout, vectorization, and query optimization have contributed compounding constant-factor speedups, making The clover query Q | , and an input instance. Note that x 0 is the only x-value in all three relations, therefore the only output tuple is (x 0 , a 0 , b 0 , c 0 ).
it challenging for WCOJ to be competitive in practice.
The dichotomy of WCOJ versus binary join has led researchers and practitioners to view the algorithms as opposites. In our SIGMOD 2023 paper [15], we broke down this dichotomy with a new framework called Free Join that unifies WCOJ and binary join. Further more, we proposed new data structures, evaluation algorithms, and optimizations to make Free Join outperform both binary join and WCOJ.
In this article, we review Free Join from a new perspective: starting from the traditional binary join algorithm, we apply a series of gradual transformations to arrive at the Free Join algorithm as well as the WCOJ algorithm. We hope this perspective from the past can help practitioners better understand Free Join, and pave the way for its adoption into existing systems.
This article is based on the paper Free Join: Unifying Worst-case Optimal and Traditional Joins [15], published at SIGMOD 2023.
In this section we introduce the Free Join framework. Unlike our SIGMOD paper [15] which defines Free Join from the basic building blocks, here we start from the traditional binary join and gently massage it into the more general Free Join. To keep the presentation intuitive, we will be following an example instead of defining the algorithm in full generality. We refer the reader to our SIGMOD paper [15] for a more formal treatment.
For simplicity we consider only natural join queries, where all joins are equijoins, and all input relations are joined over common attributes. Such queries are also known as conjunc- for ...: m = M[x]? ... 1 for ...: 2 if x not in M: 3 continue 4 else: 5 m = M[x] 6 ... tive queries and can be written in "Datalog notation" as the following example shows.
Example 1. Consider SQL query in Figure 1. The corresponding conjunctive query appears above it, where each of R(x, a), S(x, b), and T (x, c) is called a body atom, and Q|(x, a, b, c) the head atom.
It is often convenient to view a conjunctive query as a hypergraph. The query hypergraph of Q consists of vertices V and edges E, where the set of nodes V is the set of variables occurring in Q, and the set of hyperedges E is the set of body atoms in Q. The hypergraph for Q | has four vertices, each for x, a, b, and c, and three edges, each for R(x, a), S(x, b), and T (x, c). As standard, we say that the query Q is acyclic if its associated hypergraph is ↵-acyclic 1 [3]. Note that Q| is acyclic, while an example of a cyclic query is the "triangle query": Q4(x, y, z) :-U (x, y), V (y, z), W (z, x).
whose query hypergraph is a triangle.
We now introduce a notation to make pseudocode cleaner. Inside a loop, we will write m = M[x]? for looking up x from the hash map M ; if M contains x, we assign the result of the lookup to m; otherwise, we continue to the next iteration of the enclosing loop. In other words, the code fragments in Figure 3 are equivalent.
The standard approach to computing a natural join of multiple relations is to compute one binary join at a time. A binary plan is a binary tree, where each internal node is a 1 The reader does not need to be familiar with definitions of acyclic queries to understand Free Join.
join operator 1, and each leaf node is one of the base tables Ri. The plan is a left-deep linear plan, or simply left-deep plan, if the right child of every join is a leaf node. If the plan is not left-deep, then we call it bushy. For example, (R 1 S) 1 (T 1 U ) is a bushy plan, while ((R 1 S) 1 T ) 1 U is a left-deep plan. We do not treat specially right-deep or zig-zag plans, but simply consider them to be bushy.
In this paper we consider only hash-joins, which are the most common types of joins in database systems. The standard way to execute a bushy plan is to decompose it into a series of left-deep linear plans. Every join node that is a right child becomes the root of a new subplan, which is first evaluated, and its result materialized, before the parent join can proceed. As a consequence, every binary plan, bushy or not, becomes a collection of left-deep plans. We decompose bushy plans in exactly the same way, and we will focus on left-deep linear plans in the rest of this paper. For example, the bushy plan (R 1 S) 1 (T 1 U ) is converted into two plans: P1 = T 1 U and P2 = (R 1 S) 1 P1; both are left-deep plans.
To reduce clutter, we represent a left-deep plan (
1 Rm as [R1, R2, . . . , Rm]. Evaluation of a left-deep plan is done using pipelining. The engine iterates over each tuple in the left-most base table R1; each tuple is probed in R2; each of the matching tuple is further probed in R3, etc. Example 2. A possible left-deep linear plan for Q
To execute this plan, we first build a hash table for S keyed on x, where each x maps to a vector of (x, a) tuples, and a hash table for T keyed on x, each mapped to a vector of (x, c) tuples 2 . Then the execution proceeds as shown in Figure 4a. For each tuple (x, a) in R, we first probe into the hash table for S using x to get a vector of (x, b) tuples. We then loop over each (x, a) and probe into the hash table for T with x. Each successful probe will return a vector of (x, c) tuples, and we output the tuple (x, a, b, c) for each (x, c). On the input instance in Figure 1 (visualized in Figure 2), this algorithm runs in time ⌦(n 2 ).
The first transformation we perform on the binary join algorithm makes it work on column-wise storage instead of a row-wise one. This is not yet an optimization because it likely will not improve the performance, but this step serves as an important bridge to the next optimizations. As Figure 4b shows, in the outermost loop we iterate over row indices instead of tuples. For each row index i, we retrieve the x-value R.x[i], as well as the corresponding a-value R.a[i]. The hash maps for S and T now map each x to a vector of row indices, so we next look up into the hash map for S using x to get a vector of j. In the second loop, we retrieve the x-value and b-value from S for each j, then probe into T to get a vector of k. Finally, we retrieve the x-value and c-value from T for each k, and output the tuple (x, a, b, c).
A key ine ciency of the algorithm in Figure 4b is that, although the query only outputs a single tuple (x0, a0, b0, c0), 2 When the relations are bags, then the hash table may contain duplicate tuples, or store separately the multiplicity. We also note that the question what exactly to store in the hash table (e.g. copies of the tuples, or pointers to the tuple in the bu↵er pool) has been studied for a long time, see [5].
for (x,a) in R:
1 for i in 0..R.len(): we still did a lot of work retrieving the di↵erent a, b, and c values from their respective columns. For example, since we iterate over the entire R relation, we retrieve all 2n + 1 a-values from R.a; even worse, since |R ./ S| = n 2 + 1, we will access S.b ⌦(n 2 ) times. A better strategy is to delay the retrieval of these values until we actually need them. In this case, we can delay the retrieval of a, b, and c until we are ready to output the tuple (x, a, b, c). This way we only need to access each of R.a, S.b, and T.c once, instead of ⌦(n 2 ) times. This is precisely the classic late materialization optimization [1] now implemented in nearly all modern database systems.
We can go one step beyond late materialization and further optimize the code in Figure 4c. The key observation is that, although we retrieve x from the di↵erent relations in each loop level, they have to be the same value because x is the join attribute! This means we can remove the last two redundant retrievals of x and reuse the value from the outermost loop, which corresponds to removing the underlined code in Figure 4c. At this point, we can see that the remaining body of the second loop, t = T[x]?, does not depend on the loop variable j at all. We can therefore pull the lookup out of the loop, resulting in the code in Figure 4d. In other words, we delay the iteration over s until after the lookup on T succeeds.
Note that this final optimization has improved the asymptotic run time of the algorithm: although late materialization already saves a quadratic number of accesses to the relation columns, it still needs to iterate over ⌦(n 2 ) row indices, because the first two loop levels essentially compute the join R ./ S. In contrast, the first loop level in Figure 4d joins every tuple of R with S and T at the same time, and the entire algorithm now runs in O(n) time.
At the moment, our optimizations may appear rather lowlevel and ad-hoc. Taking a step back, we can understand the execution of any join algorithm as a series of iterations and lookups. The transformation from row-wise to columnwise storage involves changing what to iterate over (row indices instead of tuples); the late materialization optimization changes what to look up and when to look up (look up row indices first, then retrieve values later); finally, the late iteration optimization reorders the iterations and lookups.
While columnar storage and late materialization have become stables of modern database systems, the contribution of the Free Join framework is a new abstraction to describe the ordering of iterations and lookups that we call the Free Join plan. The basic building blocks of a Free Join plan are called subatoms, each of which is a subset of a relation schema. For example, given the relation R with schema R(x, y), all of the following are valid subatoms: R(), R(x), R(y), R(x, y). A Free Join plan over a set of schemas is a sequence of groups, where each group is a list of subatoms.
Definition 2. Given a join query Q over R1, R2, . . ., a Free Join plan for Q is of the form:
where each of Ri(x i ), Rj(x j ), R k (x k ), . . . is a subatom over the schema of Ri, Rj, R k , . . . respectively.
Each group in a Free Join plan corresponds to a loop level. At each loop level, we iterate over tuples of the first subatom in the group, and use the values to look up into the remaining subatoms. For this reason, we will sometimes stylize a Free Join plan as follows to emphasize the iterated subatom and reflect the loop nesting:
Although we only retrieve the value of a in the innermost loop, each a-value one-to-one corresponds to each i, so the plan iterates over both x and a at the first level.
Example 4. We can represent the binary join algorithm in Figure 4a with the Free Join plan: if we ignore the redundant x at the inner loop levels.
In fact, every left-linear binary join plan [R1, R2, R3, . . .] can be represented by a Free Join plan:
. . .
Generic Join plan with a Free Join plan. Free Join therefore generalizes and unifies both binary join and Generic Join. However, the true power of Free Join is its ability to represent algorithms like the one in Figure 4d that are neither binary join nor Generic Join. Intuitively, a (linear) binary join plan says which relation to process at each step, and always processes one additional relation at a time. A Generic Join plan says which variable to process at each step, and always processes one variable at a time. A Free Join plan can process any number of relations and variables at a time.
As we show in Figure 5, this flexibilty allows Free Join to represent a much larger space of algorithms, leading to performance improvements beyond the existing algorithms.
In this section, we summarize a few additional optimizations introduced in our SIGMOD paper [15], as well as relate Free Join to the Generic Join algorithm. To motivate these optimizations, we will follow the new example query Q 4 in Figure 7, and visualize an input instance in Figure 8. Note Q4 is now a cyclic query, because its hypergraph is a triangle with three vertices x, y, and z and three edges corresponding to R(x, y), S(y, z), and T (z, x).
Let us first consider the algorithm in Figure 6a. We show the Free Join plan in the comments atop the figure, and note that it is equivalent to binary join. To reduce clutter we will stick with a row-wise notation while keeping in mind the underlying columnar storage. We also remove redudant values from the hash maps; for example, the hash map for S in Figure 6a now maps every y to a vector of z (instead of a vector of (y, z)). The binary join algorithm first iterates over (x, y)-tuples in R, using each y to probe into S to get a vector of z. For each z, it then probes into T to check if (z, x) is in T , and outputs the tuple (x, y, z) if so. This binary plan essentially computes the join R ./ S first before discarding tuples that do not join with T . Because R ./ T has size ⌦(n 2 ), the algorithm runs in quadratic time. Since the relations are symmetric, any binary join plan will have the same asymptotic run time.
A di↵erent algorithm is shown in Figure 6b. Here, as we iterate over tuples in R, we look up into S and T at the same time. In other words we perform the late iteration optimization again, pulling up lookups to discard tuples early. However, this is not su cient, because every tuple in R does in fact join with both S and T , so the first loop level discards no tuples. As the second loop level iterates over s, we are in e↵ect still computing the join R ./ S which takes ⌦(n 2 ) time. To overcome this ine ciency, we now introduce a new operator called intersection (\).
In contrast, the algorithm in Figure 6c runs in linear time. The small di↵erence is that we have replaced the inner loop of Figure 6b, which iterates over s, with a loop iterating over the intersection of s and t. When we compute the intersection, we always iterate over the smaller set while probing into the larger set. To analyze the run time of this algorithm, we first assume we have built a hash map for S, mapping each y to a hash set of z, and similar for T . Building each hash map takes linear time. Then, as we iterate over R, we consider three cases:
so we may iterate over either s or t to compute s \ t in linear time. 2. For each tuple (x0, yi)
, so we iterate over (the only element of) s and probe into t to compute s \ t. This takes constant time for each yi, so for all yi the total time is linear.
3. The case for tuple (xi, y0) is symmetric to the previous case, so it also takes linear time.
Overall, the algorithm in Figure 6c runs in linear time. Another way to think about the intersection operation is to understand it as dynamically reording the iterations and lookups: to compute s \ t, we switch between the plans [S(z) | T (z)] and [T (z) | S(z)] depending on which one is smaller.
We can now faithfully derive the Generic Join algorithm as a special case of Free Join, using the itersection operator. Suppose an instance of Generic Join follows the variable order x1, x2, . . . , xn. The corresponding Free Join plan is:
i is a relation that contains xi in its schema. When computing a multiway intersection, we (dynamically) pick the smallest set to iterate over and probe into the rest. For any choice of the variable order, the Generic Join algorithm is guaranteed to run in worst-case optimal time [14,9,10]. T T S S R R Figure 8: Visualization of input relations to Q 4 . Each relation is represented by a set of edges. The query Q 4 looks for triangles formed by one edge from each relation (there are 10).
To explain the algorithm in Figure 6b we assumed to have pre-built hash maps for S and T . A more e cient strategy is to lazily construct parts of the data structures as we iterate over the relations. Specifically, we will only build the hash set for s (or t) right before we need to probe into it. This way, we can avoid building a linear number of (singleton) hash sets that we only need to iterate over. In the full paper [15] we describe a data structure, called Column-oriented Lazy Trie (COLT), that generalizes this idea.
A simple way to implement Free Join is to use a recursive function, as shown in Figure 9. For every group in the Free Join plan, we iterate over the first subatom and probe into the remaining subatoms. If all probes are successful, we append new values to the partial tuple, and recursively call join on the remaining plan and sub-relations. This naïve implementation su↵ers from poor temporal locality: in the 1 def join(plan, tuple, R, S, T, ...): 2 if plan is empty: output(tuple) 3 else: 4 let [ R(xs) | S(ys), T(zs), ... ] = plan[0] 5 tup_rels = {} # map a partial tuple to sub-relations 6 for xs_batch in R.iter_batch(): 7 for xs in xs_batch: 8 r = R[xs]?; s = S[ys]?; t = T[zs]?; ... 9 tup = tuple ++ xs 10 tup_rels[tup] = (r, s, t, ...) 11 for (tup, rels) in tup_rels: 12 join(plan[1:], tup, rels) Figure 10: Vectorized execution for Free Join.
body of the loop, we probe into the same set of relations for each tuple. But these probes are interrupted by the recursive call at the end, which is itself a loop interrupted by further recursive calls.
A simple way to improve locality is to perform a batch of probes before recursing, just like the classic vectorized execution for binary join. As shown in Figure 10, we call iter_batch to retrieve a batch of tuples from R. For each tuple in a batch, we probe into the relations to get the corresponding sub-relations. If all probes are successful, we append new values to the partial tuple, and pair the tuple with the respecitve sub-relations; otherwise we continue onto the next tuple in the batch. Finally, for each tuple that successfully probes into all relations, we call join recursively on the remaining plan.
We implemented Free Join as a standalone Rust library. The main entry point of the library is a function that takes a binary join plan (produced and optimized by DuckDB), and a set of input relations. The system converts the binary plan to a Free Join plan, optimizes it, then runs it using COLT and vectorized execution. We compare Free Join against two baselines: our own Generic Join implementation in Rust, and the binary hash join implemented in the stateof-art in-memory database DuckDB [13,12]. We evaluate their performance on the popular Join Order Benchmark (JOB) [7]. We refer the reader to our SIGMOD paper [15] for additional experiments that include other systems and benchmarks, as well as detailed ablation studies of the optimizations.
While we had easy access to optimized join plans produced by DuckDB, we did not find any system that produces optimized Generic Join plans, or can take an optimized plan as input. We therefore implement a Generic Join baseline ourselves, by modifying Free Join to fully construct all tries, and removing vectorization. We chose as variable order for Generic Join the same as for Free Join. 3The JOB benchmark contains 113 acyclic join queries with an average of 8 joins per query. Each query in the benchmarks only contains base-table filters, natural joins, and a simple group-by at the end, and no null values. The queries works over real-world data from the IMDB dataset. We exclude 5 queries that return empty results, since such empty queries are known to introduce reproducibility issues 4 .
We ran all our experiments on a MacBook Air laptop with Apple M1 chip and 16GB memory. All systems are configured to run single-threaded in main memory, and we leave all of DuckDB's configurations to be the default. All systems are given the same binary plan optimzed by DuckDB. Since we are only interested in the performance of the join algorithm, we exclude the time spent in selection and aggregation when reporting performance. This excluded time takes up on average less than 1% of the total execution time.
base-table attributes in a vector. Future work may explore more e cient materialization strategies, for example only materializing attributes that are needed by future joins.
In this paper we review the Free Join framework, which generalizes and unifies traditional join algorithms and WCOJ algorithms. We re-derive the more general Free Join from the well-understood binary join, hoping to make the framework more accessible to database practitioners. We hope to see the adoption of Free Join in mainstream databases, which shall inspire further research on the design of join algorithms. We conclude by pointing out some promising research directions. First, we have been focusing on singlethreaded in-memory algorithms. How can we adapt Free Join to work on disk, on multi-core machines, and in distributed settings? In particular, the COLT data structure relies on laziness and appears inherently sequential. Do we need a new data structure to parallelize Free Join? Second, our optimizer starts from an already optimized binary plan, and conservatively improve it into a Free Join plan. How can we design and implement an optimizer to better exploit the flexibilty of Free Join? Finally, as the experiments show, our current implementation of Free Join is not yet competitive for certain bushy plans. How can we improve the performance of materializing intermediate results for Free Join?
Free Join defines only a partial order; we extended it to a total order.
See GitHub Issue #11: https://github.com/gregrahn/joinorder-benchmark/issues/11