Algorithms for Optimizing Acyclic Queries

The query optimizer sits at the heart of a database system. It takes a query as input and generates a plan for efficient execution, allowing users to program declaratively without worrying about performance. Among the many relational algebra operators, join has received significant attention in optimization research. Its compositional nature allows for combining information from multiple relations, constructing complex queries from simple ones, and producing an output asymptotically larger than the inputs. The primary challenge is the join ordering problem to find the best arrangement of many join operations. Most existing research has focused on binary join algorithms such as hash join and sort-merge join, but these can produce unnecessarily large intermediates. Recent work has revived interest in optimal join algorithms, notably Yannakakis’ instance-optimal algorithm [42] for acyclic queries, which runs in linear time in the input and output size, $𝒪(|\text{IN}|+|\text{OUT}|)$. Its execution is guided by join trees whose nodes are relations, different from traditional binary join plans with relations at the leaves and join operators at the internal nodes. Although the algorithm is optimal regardless of the join tree, the choice of plan can affect practical performance. In this paper, we study the optimization problem in the context of Yannakakis-style algorithms.

A query optimizer typically has two parts: a plan generator and a cost model to assess each plan. This paper focuses on plan generation and presents three approaches:

1. 1.

   Given the line graph $L$ (Definition 6) of an $\alpha$-acyclic query $H$, Algorithm 2 enumerates all join trees by edits¹¹1To avoid redundant work, enumeration by edits [22] outputs the difference between consecutive elements. with amortized constant delay, i.e., in $𝒪(|L|+k)$ where $k$ is the number of trees generated (Theorem 27). If the query is $\gamma$-acyclic, Algorithm 4 further reduces the total time complexity to $𝒪(|H|+k)$ (Theorem 28).

2. 2.

   Given a Berge-acyclic query, we prove that the classic Maximum Cardinality Search algorithm by Tarjan and Yannakakis [38] yields a unique shallowest join tree (Theorem 35), enabling parallel execution of very large queries.

3. 3.

   Given a connected left-deep linear join plan for any $\gamma$-acyclic query, we prove that a simple algorithm by Hu et al. [20] always converts the plan into a valid join tree (Corollary 39), allowing reuse of existing optimizers.

The rest of the paper is organized as follows: Section 2 discusses related work; Section 3 introduces relevant concepts and notations; Section 4 presents the join tree enumeration algorithms; Section 5 introduces the unique shallowest join tree, namely the canonical join tree and its construction; Section 6 discusses the conversion from binary plans to join trees; Section 7 concludes the paper by pointing to avenues for future work. For easy reference, the key notations are summarized in Table 1. Additional technical details and proofs are provided in the extended report [27].

Join order optimization is well studied, with algorithms based on dynamic programming (DP) from the bottom up [29, 33, 31], cost-based rewriting from the top down [11, 15], greedy heuristics [5, 14, 37], and randomized search [35]. Since the plan space is exponential, most methods prune it: some restrict to left-deep plans [21, 23], while others avoid Cartesian products [29, 30]. Our algorithms restrict the query plans to those running in linear time for acyclic queries. In particular, while avoiding Cartesian products requires each subplan to form a spanning tree of the corresponding subquery’s join graph,²²2The join graph of a query has a vertex for each relation and an edge for each pair of relations that join with each other. We later define this as the line graph of the query hypergraph in Definition 6. our algorithms find maximum spanning trees of the weighted join graph. Several algorithms for ordering binary joins are based on dynamic programming and tabulate shared structures among different plans [29, 30]. This is desirable because subplans are grouped into equivalence classes, and the optimal plan can be constructed in a bottom-up manner. Future work may explore constructing compact representations of join trees, suitable for dynamic programming.

Several recent papers have proposed practical implementations of Yannakakis’ algorithm for acyclic queries [2, 20, 40, 45]. For example, Zhao et al. [45] find that different query plans perform similarly, thanks to the optimality of Yannakakis’ algorithm. They adopt a simple heuristic to construct the join tree by picking the largest input relation as the root, and then greedily attaching the remaining relations into the tree. Inspired by this algorithm, we prove in Section 5 that for Berge-acyclic queries there is a unique shallowest join tree for any given root where the depth of each node is minimized. Furthermore, this tree can be constructed in linear time by Tarjan and Yannakakis’ Maximum Cardinality Search algorithm [38]. Shallow trees are desirable for parallel execution, where the depth of the tree determines the number of sequential steps. Other practical implementations of Yannakakis’ algorithm leverage existing optimizers for binary joins and convert a binary plan into a join tree [2, 20]. In particular, Hu et al. [20] find that every left-deep linear plan encountered in practice can be converted into a join tree by a simple algorithm. This is not surprising, as we will prove in Section 6 that every connected left-deep linear plan of a $\gamma$-acyclic query must traverse some join tree from root to leaves.

On the theoretical side, attention has been focused on finding (hyper-)tree decompositions to improve the asymptotic complexity of query processing [36, 19, 16]. The general goal is to find a decomposition with small width which can be used to guide the execution of join algorithms. Most algorithms find a single decomposition with minimum width to achieve the optimal asymptotic complexity [36, 19, 16]. Nevertheless, different decompositions with the same width may still lead to different performance in practice, and cost-based optimization remains crucial. For this, Carmeli et al. [6] propose an algorithm to enumerate tree decompositions with polynomial delay. In this paper, we focus on acyclic queries and their join trees, which are precisely the decompositions with width 1. Our enumeration algorithm can generate all join trees by edits with amortized constant delay.

We focus on full conjunctive queries [1] in this paper and identify each query with its hypergraph, where each vertex represents a variable and each hyperedge represents a relation. Table 1 summarizes key notations introduced throughout the paper.

We only consider hypergraphs without isolated vertices, empty hyperedges or duplicated hyperedges over the same set of vertices. We assume each hyperedge $r$ contains a bounded number ($𝒪(1)$) of vertices exclusive to $r$. When there is no ambiguity, we will use $r$ interchangeably with $\chi (r)$, $x\in r$ with $x\in \chi (r)$, and $H(X,R)$ with $H(X,R,\chi )$. We will also apply common set operations directly to hyperedges, e.g., $r_1\cap r_2$ for $\chi (r_1)\cap \chi (r_2)$.

In fact, the reader can often ignore $\chi$ and identify a hyperedge with its set of vertices; the purpose of $\chi$ is to relate hyperedges over different vertex sets across hypergraphs in the correctness proofs of our algorithms.

We write $X(H)$ and $R(H)$ to refer to the vertices and edges of $H$ respectively. The size of a hypergraph is the total size of all hyperedges $|H|={\sum }_{r\in R}|r|$. We let ${H|}_x$ denote the neighborhood of $x\in X$, consisting of all hyperedges containing $x$.

We denote the set of vertices in $G$ with $R$, because we will soon define the line graph $L$ of a hypergraph where each vertex in $L$ represents a hyperedge. We write $R(G)$ and $E(G)$ to refer to the vertices and edges of $G$ respectively.

Because each edge $e$ in a simple graph can be identified with its two endpoints $\rho (e)=\{r_1,r_2\}$, we will omit $\rho$ and write $\{r_1,r_2\}$ for $e$ when there is no ambiguity.

A weighted graph is a (multi-)graph where each edge is assigned a weight:

The line graph of a hypergraph is the “intersection graph” of its hyperedges:

In addition, we define a weight function mapping each edge to the size of its label:

When there is no ambiguity from the context, we simply write $L(H)$ as $L$, and we may treat the line graph $(G,\chi )$ as a weighted graph $(G,\omega )$. The size of a line graph is the sum of all edge weights $|L|={\sum }_{e\in E(L)}\omega (e)$. For any subgraph $G$ of $L(H)$, we let ${G|}_x$ denote the subgraph of $G$ induced by ${H|}_x$.

We use $R(T)$ to denote the set of nodes and $E(T)$ to denote the set of edges of tree $T$. The requirement that ${T|}_{x\in X(H)}$ be a connected subtree is also known as the running intersection property [13]. We write $𝒯(L(H))$ or $𝒯(H)$ to denote the set of unrooted join trees of $H$. We use $T_r$ to denote a join tree rooted at $r\in R(T)$. When there is no ambiguity, we simply write $T$. The depth of a node $r_i$ in the rooted tree $T_r$, denoted $0pt(T_r,r_i)$, is defined as its distance from the root.

Four common notions of hypergraph acyclicity are defined in increasing order of strictness [13], namely $\alpha$-acyclic $\supset$ $\beta$-acyclic $\supset$ $\gamma$-acyclic $\supset$ Berge-acyclic.

The following classic result relates join trees of $H$ to maximum spanning trees of $L(H)$:

Join trees for acyclic hypergraphs can be constructed by GYO reduction:

The GYO reduction algorithm [43] finds such an order iteratively, and attaches each hyperedge to its parent to form a join tree. It generates the join tree $T^G$ as shown in Figure 1(c), where, for example, the node $T$ is the parent of $W$, denoted as $p(W)=T$ and the root $P$ has no parent.

Another way to construct join trees is via the Maximum Cardinality Search (MCS) algorithm [38], and we present a simplified version in Algorithm 1. The join tree produced by the algorithm is called an MCS tree. Given an input hypergraph $H$ and a hyperedge $r\in R(H)$ chosen as the root, Algorithm 1 constructs a rooted MCS tree by iteratively expanding toward hyperedges connected with those already processed. The algorithm maintains a set $R$ of unprocessed hyperedges and a set $X$ of unvisited vertices. Initially, the MCS tree contains no edges, and the first hyperedge to be processed is the root $r$. In each iteration, the algorithm processes the current hyperedge $r$ by examining all of its unvisited vertices in $r\cap X$. Whenever such a vertex $x$ is encountered, every remaining hyperedge $r^{\prime }\in R$ that contains $x$ records $r$ as its tentative parent $p(r^{\prime })\leftarrow r$. Once all vertices of $r$ are marked as visited, they are removed from $X$. The hyperedge $r$ is marked as processed and removed from $R$. After processing each $r$, the edge between $r$ and its recorded parent $p(r)$ is added to the MCS tree as $\{r,p(r)\}$. The algorithm selects as the next hyperedge an element of $R$ that maximizes the number of already visited vertices, namely a hyperedge $r$ that maximizes $|r\setminus X|$, breaking ties arbitrarily. This process continues until all hyperedges have been processed, when the recorded edges $\{r,p(r)\}$ form an MCS tree rooted at $r$.

Algorithm 1 can generate different join trees by varying the choice of root and tie-breaking strategy. However, it does not guarantee to generate all possible trees. For example, it never generates the join tree $T^G$ shown in Figure 1(c).

We extend the notions of parent, children and siblings to edges of a rooted tree. Let $e\in E(T)$ be an edge of tree $T$ rooted at $r$ (and $e$ not incident to $r$). Its parent $p(e)\in E(T)$ is the unique tree edge incident to $e$ and closer to the root $r$. We let $c(e)$ denote the set of children of $e$ in $T$. The siblings of $e$ are the set of edges incident to the parent of $e$, namely $s(e)=\{e^{\prime }\in E(T)\setminus \{e\}\mid p(e^{\prime })=p(e)\}$. Edges incident to the root do not have a parent and are all siblings.

Lemma 14 shows that an MCS tree is “somewhat monotonic” in that every edge must contain some variable not in its parent. If two edges share any variable not in their parents, they must be siblings.

Our strategy for enumerating the join trees of a hypergraph $H$ starts from Theorem 11 which allows us to reduce the problem to the enumeration of maximum spanning trees (MSTs) of the line graph $L(H)$. The best known algorithm for MST enumeration³³3Eppstein focuses on minimum spanning trees, but the same algorithm applies to maximum spanning trees with flipped comparisons. is due to Eppstein [12] by deriving from the input graph $G$ a so-called equivalent graph $G^{\equiv }$. Every spanning tree of $G^{\equiv }$ corresponds to an MST of $G$ and vice versa. Eppstein gives an algorithm (and proves a matching lower bound) in time $𝒪(m+n\log n)$ to construct the equivalent graph from an arbitrary weighted graph with $m$ edges and $n$ vertices. Then to enumerate all $k$ MSTs of $G$, he applies existing algorithms to enumerate the spanning trees of $G^{\equiv }$. Since there are optimal spanning tree enumeration algorithms that run in $𝒪(m+n+k)$ time [22, 34], the overall time complexity to enumerate MSTs is $𝒪(m+n\log n+k)$. The main result of this section is an algorithm for enumerating join trees leveraging the structure of acyclic hypergraphs and their line graphs. In particular:

• $\mathrm{■}$

  Given the line graph $L$ of an $\alpha$-acyclic hypergraph, we can construct an equivalent graph of $L$ in $𝒪(|L|)$, thus enumerating the join trees in $𝒪(|L|+k)$ time (Theorem 27).

• $\mathrm{■}$

  Given any $\gamma$-acyclic hypergraph $H$, we can construct an equivalent graph of $L(H)$ in $𝒪(|H|)$, lowering the overall time complexity of enumeration to $𝒪(|H|+k)$ (Theorem 28).

Note that $|L(H)|$ can be quadratic in $|H|$ while $|H|\in 𝒪(|L(H)|)$, so the second item above yields a better bound.

In the rest of this section, we first define the equivalent graph. Then, we present the algorithm for enumerating join trees of $\alpha$-acyclic hypergraphs. Finally, we adapt the algorithm to enumerate join trees of $\gamma$-acyclic hypergraphs more efficiently.

An acyclic query can have exponentially many join trees with respect to its size. For example, the line graph of a clique query with $n$ relations is an $n$-clique $K_n$ with $n^{n-2}$ join trees by Cayley’s formula [7]. Enumerating all join trees can be prohibitive for large queries. The query optimizer does not need to consider all possible join trees to achieve good performance. For example, the implementation of Yannakakis’ algorithm by Zhao et al. [45] achieves similar performance on any join tree rooted at the largest relation. An alternative to enumeration is therefore to simply construct one join tree for a given root. This can be done in linear time by the Maximum Cardinality Search (MCS) algorithm from a chosen relation as shown in Algorithm 1. In this section, we prove that for a Berge-acyclic query the MCS algorithm produces a shallowest tree, where the depth of each tree node is minimized. We prove that this shallowest tree is unique, and therefore call it the canonical join tree.

A shallow join tree has practical benefits. For example, the depth of the join tree determines the number of sequential steps required in a parallel join algorithm. A shallow join tree also tends to be wide and have more leaves, allowing better utilization of indices.

Although Berge-acyclicity was thought to be too restrictive when it was first introduced to database theory [13], we found it to be general enough to cover almost all acyclic queries encountered in the wild. As shown in Table 2, among $\mathrm{10\hspace{0.17em}454}$ queries from five popular benchmarks, $9285$ are $\alpha$-acyclic, and only 8 of these are not Berge-acyclic. In retrospect, this should not be surprising, as most joins in relational databases are over primary/foreign keys. Emerging workloads in graph databases usually involve simple graphs and seldom require composite key joins. A query without composite key joins admits a linear hypergraph, where each pair of hyperedges shares at most one vertex. The following result establishes an equivalence between $\alpha$-acyclicity with linearity and Berge-acyclicity.

By Proposition 30, every edge in the line graph of a Berge-acyclic hypergraph has a weight of 1. Every spanning tree is a maximum spanning tree, therefore a join tree.

In the rest of this section, we prove the existence and uniqueness of the canonical join tree rooted at any relation of a Berge-acyclic hypergraph, and show that it can be constructed by MCS as in Algorithm 1.

The key insight leading to the existence and uniqueness of the canonical join tree is that the line graph $L$ of a Berge-acyclic hypergraph is geodetic [32], meaning that there is a unique shortest path between any pair of vertices. The canonical join tree can then be constructed by taking the union of all shortest paths from the root to each other vertex, as this will guarantee minimal depth for each vertex. The key step to establish the geodetic property is to show that $L$ is a special class of chordal graphs called block graphs. Chordal graphs are intimately related to acyclic hypergraphs [9], and a block graph is a special chordal graph defined as follows:

Together with the fact that every block graph is geodetic (with a unique shortest path between any two vertices) [32], Lemma 33 implies the following corollary.

We are now ready to prove the existence and uniqueness of the canonical join tree.

Recent approaches [20, 2] that convert a binary join plan into a join tree have gained popularity as they allow system builders to leverage existing query optimizers designed for binary join plans. In this section, we focus on an algorithm by Hu et al. [20] to convert left-deep linear join plans into join trees as shown in Figure 5. We prove that the algorithm converts any connected left-deep linear join plan into a join tree if and only if the query is $\gamma$-acyclic. This can be seen as a new characterization of $\gamma$-acyclic queries. We formally define binary join plans and describe the algorithm by Hu et al. in Algorithm 5.

Query optimizers strive to produce connected plans, to avoid expensive Cartesian products. Many optimizers produce exclusively left-deep linear plans. Plans that are not left-deep are called bushy, and such plans may still be decomposed into left-deep fragments [41].

Given a left-deep linear plan, Hu et al. [20] generate a join tree with Algorithm 5. The algorithm chooses the first relation $r_1$ as the root and iterates through the rest of the plan. For each relation $r_{i\in [2,n]}$, it finds the first relation $r_j$ that contains all attributes shared by $r_i$ with all previous relations, , and assigns $r_j$ as the parent of $r_i$. The algorithm constructs a join tree if it finds a parent for each $r_i$.

Hu et al. [20] proved that the algorithm succeeds whenever the input plan is the reverse of a GYO-reduction order. They also observed that every left-deep linear plan produced for queries in standard benchmarks is indeed the reverse of a GYO-reduction order. This is not a coincidence, as we show that every connected left-deep linear join plan must be the reverse of a GYO-reduction order if and only if the query is $\gamma$-acyclic.

Immediately following Theorem 38, we can conclude the following.

We proposed three approaches for constructing join trees. Our enumeration algorithm in Section 4 generates join trees by edits with amortized constant delay; in Section 5, we showed that the Maximum Cardinality Search algorithm constructs the unique shallowest join tree for any Berge-acyclic query; in Section 6, we characterize the class of binary join plans that can be converted to join trees. Practitioners can choose from the three approaches to integrate instance-optimal algorithms into their system: a cost-based optimizer can use our enumeration algorithm to generate candidate query plans; a system aiming to support very large queries can implement the MCS algorithm to generate shallow join trees to improve parallelism; and a more conservative extension can derive join trees using existing optimization infrastructure, while our final result guarantees the validity of the output.

Future work includes compact representations of join trees for dynamic programming, as in binary plan optimizers, and the challenging cost estimation for Yannakakis-style algorithms: the random-walk approach [26] models joint probabilities for binary joins, whereas an efficient and accurate solution for semijoins remains to be found.

Our work also raises further theoretical questions. Can join tree enumeration achieve worst-case constant delay? We proved Berge-acyclicity sufficient for the existence and uniqueness of the canonical join tree, but it is not necessary, and $\gamma$-acyclicity is insufficient as shown in Figure 6. What is the precise characterization of hypergraphs that admit a unique canonical join tree for any root, or for some root? How can our algorithms be extended to enumerate tree decompositions à la Carmeli et al. [6]? One possible direction is to further develop connections between MSTs of the line graph and tree decompositions of the hypergraph. For example, we are considering using the determinants of the line graph Laplacian as heuristics to guide the search for good tree decompositions.