The Quest for Faster Join Algorithms

Joins are the cornerstone of relational databases. First introduced by Codd [8] as a core operator in relational algebra, they are now a key component of any database engine.

In any relational database engine, a join query can be executed via a plan of binary joins ($⨝$). The problem at hand is to optimize the order of these binary joins, as well as the specific algorithm that computes each join. There has been a huge amount of literature on this topic, and it is still a very active area of research. A key difficulty is that the join optimization problem is computationally hard, and is also based on gathering accurate statistical information, a process that is often erroneous. Query optimizers will notoriously choose suboptimal join plans. Nevertheless, the database systems architecture of how to do joins has remained virtually the same for the last three decades.

From a theoretical perspective, the story of join algorithms is quite different. Over the past couple of decades, there has been significant and exciting progress in our understanding of how to evaluate joins more efficiently. Novel techniques and new algorithmic frameworks have produced faster and faster join algorithms. Several ideas produced in the database theory community are also slowly moving into practice and are incorporated into real-world database systems. In this talk, we will tell this story and then talk about the research problems that are still open.

To keep the presentation simple, we will focus on relational queries with natural joins ($⨝$) and projections ($\pi$), of the following form:

Here, the attributes are indexed by $[n]=\{1,2,\mathrm{\dots },n\}$, and the join is described by a hypergraph $H=([n],E)$. $X_e$ denotes a vector of attributes indexed by the nodes in $e\in E$. The projection attributes are $X_U$, where $U\subseteq [n]$. When $U=\mathrm{\varnothing }$, we have a Boolean join and when $U=[n]$ we have a full join – no projections. For example, consider the following two full joins (triangle join and square join) which we will use as running examples throughout:

The key task is to compute the output $Q(D)$ of join query $Q$ over a relational instance $D$. We will denote by $N=|D|$ the input size (total number of tuples in the instance) and by $OUT=|Q(D)|$ the output size (total number of tuples in the output). To measure runtime, we will use data complexity, which means that we consider the query to be fixed. We can now pose the central question precisely.

Given a join query $Q$ and an instance $D$, what is the fastest algorithm that computes $Q(D)$ w.r.t. the input and output size?

What can we do when the join is not acyclic? The idea is simple: we will attempt to make the join acyclic by computing larger and larger intermediate relations, which can then be used as “input relations” in the join. Of course we have to be careful, so that the intermediate relations do not blow up in size. The task then becomes: what are the smallest possible intermediate relations we can construct such that we end up with an acyclic join? This questions leads naturally to the idea of tree decompositions.

A tree decomposition of a join $Q$ can be viewed as a join tree where each node is not an input relation, but an intermediate relation. In more technical terms, each node in the tree (called typically a bag) is assigned a subset of the attributes $X_1,\mathrm{\dots },X_n$. We still want the connectedness property to hold. Additionally, we want the attributes of each relation $R_e$ to appear in some bag of the tree; this is necessary to guarantee correctness.

The algorithm is then: compute the relation at each bag; then use Yannakakis’ algorithm to compute the final join output. To compute a bag $B$ with attributes $X_B$, we can use a simple algorithm: find the smallest subset of relations that “cover” all the attributes and join them. If we have $w$ such relations, this costs $O(N^w)$. The quantity $w$ is called the integral edge cover for $X_B$, denoted $w(X_B)$, and the largest $w$ over all bags is called the generalized hypertree width (ghw) of the tree decomposition [20]. Clearly, we want to find the tree decomposition with the smallest ghw overall, and this is called the ghw of the join.

When the join is acyclic, we have $\text{ghw}=1$. As the join becomes more complex, the generalized hypertree width increases. Using the idea of a tree decomposition produces again an algorithm that can be expressed as a join-project plan, as before (see Figure 2). We should note here that ghw is related to the notion of treewidth in graph theory [38].

So far we have discussed join algorithms that can be expressed as join-project plans. However, it can be shown that join-project plans are suboptimal [3]. For example, any join-project plan for the triangle join $Q_{\mathrm{\Delta }}$ has cost at least $N^2$, but as we will see this join can be computed in time only $O(N^{3/2})$. This means that we have to go beyond join-project plans and introduce possibly new operators in the query plan (or maybe new algorithmic frameworks). Surprisingly, to reach state-of-the-art we need to add a single operator: a partitioning operator that splits a relation into two disjoint parts which we call heavy and light.

The key intuition behind data partitioning is that different parts of a relation have different properties (e.g., frequencies of values on each attribute) and behave different with respect to different query plans. This means that it can be often beneficial to split the input into different parts, and apply different query plans to each part.

Partitioning helps us in two ways. First, it gives us a faster algorithm to compute each intermediate relation in a tree decomposition. Instead of paying the cost of the integral cover, we now only need to pay the fractional edge cover, which we denote by $f(X_{[n]})$. The breakthrough work on worst-case-optimal join algorithms [43, 33, 35] showed that any join can be computed in worst-case size time that is equal to $O(N^{f(X_{[n]})})$.

This immediately gives us a stronger notion of width, called fractional hypertree width (fhw). For the triangle query, $\mathrm{𝖿𝗁𝗐}(Q_{\mathrm{\Delta }})=3/2$, since we can cover each relation with a fractional weight of $1/2$. In general:

But even that is not enough to give us a fast algorithm. Take the example of $Q_{\square }$. If we are guided by single tree decomposition, we only get a quadratic runtime. So, we need to use multiple tree decompositions and partition the data such that each decomposition guides the plan of a different part of the data. Hence, we not only need to decide what plan we want to use for each part of the data, but also into which tree decomposition we will place it. This is a complex optimization problem. To solve this, Khamis et al. proposed the PANDA algorithm [30, 31], which is the current state-of-the-art algorithm for most join queries. We will not describe the details of PANDA, but the key idea is that it prescribes an algorithm that chooses the next operator (between a join, a projection, and a partitioning). PANDA leads to an even tighter notion of width, called submodular width [32]:

The difference in the definition is on the function which specifies the cost of computing each bag. This is now specified by a submodular function $h$. For the square query, $\text{subw}(Q_{\square })=3/2$.

So far we have analyzed join algorithms with respect to only two parameters: the input size $N$ and the output size $OUT$. Unfortunately, using only these two parameters in the runtime bound gives us join algorithms that have worst-case optimal performance, but in practice may not perform well. The reason behind this gap between theory and practice is that the input and output sizes are not sufficient to accurately describe the database instance. A query optimizer that uses more fine-grained statistical information will thus perform better, even if it uses a suboptimal class of algorithms.

The above example shows the use of integrity constraints (here, primary keys) as statistical information. Other types of statistical information are cardinality constraints (a bound on the size of each input relation), functional dependencies, key-foreign key constraints, and a more general type of statistical information called degree constraints [30]. In their most general form, degree constraints assert that for two disjoint sets of attributes $X_A,X_B$ in the same relation $R$, for any values $b$ of $X_b$, we have that $|{\pi }_{X_A}({\sigma }_{X_B=b}(R))|\le d$ for some number $d>0$. Degree constraints generalize both cardinality constraints and functional dependencies, and can nicely fit into the algorithmic framework of join-project-partition plans providing tighther runtime analysis and more optimized query plans [30].

Some very recent work has progressed one step further and has provided algorithms that work for even more fine-grained statistical information. Degree sequences [10] maintain the distribution of frequencies for $|{\pi }_{X_A}({\sigma }_{X_B=b}(R))|$ instead of a single upper bound. Norm bounds [27] use ${\mathrm{\ell }}_p$ norms to capture concisely this distribution of frequencies. Finally, partition constraints [9] offer another generalization of degree constraints that also captures the notion of degeneracy in graph theory. All these types of statistical information can be integrated to state-of-the-art join algorithms and can also lead to better cardinality estimation in practice, but of course there is a catch: more fine-grained statistics are more costly to gather and maintain. It is still an open question to find the right balance between the granularity (and type) of statistics and the efficiency of a join algorithm.

The efficiency of an algorithm is typically measured by the time it takes to produce the whole output. When the output is a single number (e.g., integer, real) or a Boolean value, this is a natural definition. But in query evaluation, the output is often a relation that can have multiple tuples – in many cases, the join output can be much bigger than the input itself.

This particular characteristic of join computation allows for the use of runtime measurement for join algorithms in a more fine-grained way. In particular, we can think of a join algorithm for a join query $Q$ as working in two phases:

Preprocessing Phase:

in the first phase, the algorithm will read the input instance $D$ and produce an intermediate data structure $C_Q(D)$. For the preprocessing phase, we care to minimize the total preprocessing time.

Enumeration Phase:

in the second phase, the algorithm will read $C_Q(D)$ and start producing the output tuples. For this phase, the goal is to minimize the largest time between outputting any two consecutive tuples (including the time to produce the first tuple, and the time from the last tuple to terminating): this time is called the delay.

Ideally, we want to achieve constant-delay enumeration, which is the strongest possible delay guarantee [40]. Constant-delay enumeration implies that we need only $O(1)$ time between seeing two consecutive output tuples. This can be very powerful as an algorithmic framework: if we only want to see $k$ tuples of the join output, we then need to pay only $O(N+k)$ time. Additionally, if we know that the output may be reused, we can keep the intermediate data structure only (and not the full join output).

It turns out that we can modify Yannakakis’ algorithm such that we can keep linear preprocessing time but also achieve constant-delay enumeration [4].

The algorithm can also be applied to more general acyclic joins with projections, a class called free-connex acyclic joins. Combining the above theorem with tree decompositions and data partitioning, we can also obtain for any join query an algorithm with $\tilde{O}(N^{\mathrm{𝗌𝗎𝖻𝗐}})$ preprocessing time and constant delay.

The idea of enumeration leads naturally to the idea of a factorized representation of an output. There is really no need to keep the join output fully materialized if we can always reconstruct it as fast as possible when needed. This idea first appeared under the name of factorized databases [37, 36]. The additional benefit of a factorized join result is that often we can do post-processing directly on the factorization, without decompressing it and depending on the downstream task [39, 28].

So far we have focused on join processing under relational set semantics: an tuple can either occur in the output or not. Many real-world applications require different semantics for join evaluation: SQL uses bag semantics (and so a tuple may appear multiple times in the output), or other times we may want to perform some aggregate computation on the join result (summation, max, min, counting). Many of these semantics can be beautifully captured in one unifying algebraic framework with the use of semirings.

Semirings for joins were first proposed by Green et al. [21]. A semiring $𝕊=(𝐃,\oplus ,\otimes ,\mathrm{𝟎},\mathrm{𝟏})$ is an algebraic structure where $\oplus$ is the addition and $\otimes$ is the multiplication such that $(i)$ $(𝐃,\oplus ,\mathrm{𝟎})$ and $(𝐃,\otimes ,\mathrm{𝟏})$ are commutative monoids, $(ii)$ multiplication is distributive over addition, and $(iii)$ $x\otimes \mathrm{𝟎}=\mathrm{𝟎}$ for every element $x\in 𝐃$. The semiring is also idempotent if $x\oplus x=x$ for every element $x\in 𝐃$. An example of an idempotent semiring is the tropical semiring $(\mathbb{N},\min ,+,+\mathrm{\infty },0)$ or the Boolean semiring $(\{0,1\},\vee ,\wedge ,0,1)$.

Given an instance $D$ and a semiring $𝕊$, we can annotate each input tuple $t$ from relation $R_e$ with a value from the domain $𝐃$ of the semiring $𝕊$. For example, if $𝕊$ is the Boolean semiring $(\{0,1\},\vee ,\wedge ,0,1)$, the annotation captures the presence or absence of the tuple $t$. If $𝕊$ is the counting semiring $(\mathbb{N},+,\times ,0,1)$, the annotation captures the multiplicity of the tuple $t$. The semantics of a join can be naturally lifted to semirings: for a join $Q={\pi }_U({⨝}_{e\in E}{R}_e(X_e))$, we interpret ${\pi }_U$ as an $\oplus$-sum and ${⨝}_{e\in E}$ as an $\otimes$-product. For example, if we consider the query ${\pi }_{\mathrm{\varnothing }}(R(X_1,X_2)⨝S(X_2,X_3),T(X_3,X_1))$ over the tropical semiring $(\mathbb{N},\min ,+,+\mathrm{\infty },0)$, the output will be the total weight of the minimum-weight triangle. Over the counting semiring, the same query would output the total number of triangles.

Lifting the semantics of a join to semirings may seem that it would create a harder algorithmic problem, but in fact many of the join algorithms we have discussed so far in this paper can work for any semiring with minor modifications. For example, Yannakakis’ algorithm can be modified to compute a Boolean acyclic join over any semiring in linear time $O(N)$ [29]. Joins with negation can also be handled with the same efficiency when we consider semirings [49]. If the semiring is idempotent, then PANDA can also be applied to work for any semiring with the same runtime [29]. Joins over non-idempotent semiring (e.g., counting) are more challenging although we can still apply some of the newer join algorithms [29, 25]. One key takeway here is that the join algorithms used in practice and in theory can most of the time be lifted to work in this more general algebraic structure of semirings: we get this almost for free!

In this final part, we present several exciting open problems in join algorithms.