Query Decompositions and All That

Conjunctive Queries (CQs, for short) are arguably the most fundamental class of (relational) queries. Consequently, the optimization of CQs has been a major topic in DB theory and systems research. Finding an optimal query evaluation plan is a highly non-trivial (in fact, intractable) problem. A particular challenge consists in avoiding the explosion of intermediate results. For acyclic CQs (ACQs, for short), Yannakakis’ algorithm [36] guarantees that intermediate results never exceed the combined size of input and output. In recent time, implementations of Yannakakis’ algorithm have found their way into mature research prototypes and industrial-strength database management systems [7, 35, 6, 26].

In general, we cannot expect all CQs to be acyclic. However, extensive analyses [8, 27, 13] of queries in benchmarks and query logs have shown that the majority of those queries are “almost acyclic”. Various types of query decomposition methods (with associated width-measures) have been proposed to transform such CQs into ACQs. Among the most thoroughly studied decomposition methods are tree decompositions (TDs) [31], (generalized) hypertree decompositions (GHDs and HDs, respectively) [17, 2], and fractional hypertree decompositions (FHDs) [20]. The associated width measures, that allow us to formalize the notion of “almost acyclic” CQs are tree-width (tw), (generalized) hypertree-width (ghw and hw, respectively), and fractional hypertree-width (fhw). Note that decomposition methods for query evaluation have been successfully implemented in several research prototypes [1, 32, 25].

The main “freedom” of query evaluation algorithms based on one of these decompositions is how to compute and materialize the subquery corresponding to each bag of the decomposition. Using some worst-case optional join (WCOJ) method is often considered as optimal. A basic and very intuitive form of WCOJ algorithm is the so-called Generic Join [29]. Assume the upper bound $N$ on the size of the database. Then the time and space complexity of using an (optimal) FHD is essentially $O(N^{\text{fhw}})$ (data complexity). While this bound on the time complexity may be satisfactory, such a space complexity may actually be not acceptable.

Space is a critical bottleneck in query evaluation across diverse hardware settings. Modern in-memory databases suffer significant performance degradation when forced to spill to disk [33]. Similarly, tensor algebra programs, often modeled as Sum-Product Queries (SPQs, for short), are frequently executed on GPUs where high-bandwidth memory is scarce; the cost of data movement between GPU and CPU can easily dwarf computation time [30, 19]. Furthermore, in resource-constrained environments like embedded devices, memory limits are strict and must be respected [21, 22]. In all these contexts, the existing space-complexity bounds of current query evaluation techniques are insufficiently tight for practical optimization.

Now a natural question arises: can we do better? That is, can we improve the time and space requirements of query evaluation or, at least, improve one without deteriorating the other. Here, we are particularly interested in the question whether we can improve the space complexity of previous query evaluation approaches without (significantly) compromising the time complexity.

CQs have long been known to be closely related to Constraint Satisfaction Problems (CSPs) [24]. In fact, on the logical level, both correspond to first-order formulas restricted to the connectives $\exists ,\wedge$ and excluding $\forall ,\vee ,\neg$. The above mentioned decomposition methods have actually been equally studied and applied in both areas. However, other than that, both areas have developed their own techniques. Here, we follow mostly Rina Dechter’s book [11], where “constraint networks” [10] (corresponding to Boolean CQs) as well as “probabilistic networks” and “cost networks” (which can be captured by scalar SPQs) have been studied. In [11], decomposition-based methods are referred to as “inference-based”. They are contrasted with the other important paradigm in the CSP-community, namely “search-based” methods.

In their basic form (so-called “OR-search”), search algorithms work by branching into possible instantiations of one variable after the other. This search is realized by nested loops which, for each variable, iterate through the possible values. By exploring one instantiation of each variable at a time, the space consumption is proportional to the number of variables and, therefore, constant when considering data complexity. A more sophisticated approach is an “AND/OR-search”, which exploits the fact that, after instantiating some variable(s), possible instantiations for other variables may be investigated independently. While OR-search is guided by an order on the variables (i.e., in which order to inspect possible instantiations), AND/OR search is guided by a tree structure, reflecting the independence of variables conditioned on their common ancestors. Here, we concentrate on pseudo-trees, which were introduced in [15] and studied in detail and further developed in [11]. As was observed in [12], Generic Join, which realizes the “attribute”- (= “variable-”) at-a-time” paradigm, corresponds to the less sophisticated OR-search.

The following example will help to illustrate some of the characteristics of the classes of query plans mentioned so far, namely tree decompositions, Generic Join, and pseudo-trees.

Our goal is to study both decompositions and search-based methods as well as the relationship between them. To this end, we first recall properties of these methods individually and then study their combination. In particular, we look at what is gained in terms of time and/or space complexity, when using pseudo-tree-based algorithms for evaluating the subquery at each bag of a (tree) decomposition. We thus analyze various classes of query plans in terms of data complexity. As “yardstick”, we consider their space and time exponents. More specifically, we will say that a query plan $\mathrm{\Pi }$ in a given class of query plans has space-time exponent $e(\mathrm{\Pi })=(s(\mathrm{\Pi }),t(\mathrm{\Pi }))$, if the “canonical” evaluation algorithm executing the query plan $\mathrm{\Pi }$ has space complexity $O(N^{s(\mathrm{\Pi })})$ and time complexity $O(N^{t(\mathrm{\Pi })})$, where $N$ is a bound on the size of the database. For instance, as fundamentally different approaches we have Generic Join plans $\mathrm{\Pi }$ with $e(\mathrm{\Pi })=(0,{\rho }^{\ast }(Q))$ and plans $\mathrm{\Pi }$ using a (tree) decomposition and WCOJ to evaluate and materialize the subqueries at each bag with $e(\mathrm{\Pi })=(\text{fhw}(Q),\text{fhw}(Q))$. That is, the space complexity of Generic Join plans is clearly optimal, while plans based on a decomposition plus WCOJ are, in general, superior in terms of time consumption.

The focus of this article will be on illustrating the key ideas of various classes of query plans by means of examples. Formal proofs of all results mentioned here can be found in [12]. To keep things simple and in the interest of clarity, we will concentrate on CQs and, in particular, Boolean CQs. We note that, in [12], the more general case of SPQs over some semi-ring $𝕂$ and with output variables is studied.

The remainder of this article is structured as follows: After introducing some basic definitions and results in Section 2, we revisit query plans based on decompositions in Section 3. In Section 4, we will study several variants of pseudo-trees. The combination of decompositions and pseudo-trees will then be discussed in Section 5. We conclude with a summary and an outlook on future work in Section 6.

In this paper, we focus on Conjunctive Queries (CQs), which correspond to select-project-join queries in the Relational Algebra. W.l.o.g., we restrict ourselves to CQs of the form $Q={\pi }_{𝑿}(R_1\bowtie \mathrm{\cdots }\bowtie R_m)$. Here we assume that equi-joins are replaced by natural joins via appropriate renaming of attributes. Moreover, we assume that selections applying to a single relation have been pushed immediately in front of this relation and the $R_i$’s are the result of these selections. Alternatively, we denote CQs in Datalog-style notation and write them as

$Q$ is a Boolean CQ, if $𝑿$ is the empty set. Recall that, from a logical point of view, CQs and Constraint Satisfaction Problems (CSPs) are, the same. Hence, our discussion equally applies to CSPs.

By slight abuse of notation, we write $R_i$ both, to denote a relation (in a Relational Algebra expression) and a relation symbol (in Datalog notation). We denote (sets of) variables (also called attributes) by capital letters $A,B,C,\mathrm{\dots }$ ($𝑿,𝒀,𝒁,\mathrm{\dots }$) and (tuples of) domain values by lowercase letters $a,b,c,\mathrm{\dots }$ ($𝒙,𝒚,𝒛,\mathrm{\dots }$). We will also refer to variables as attributes when this is more appropriate. We write $\mathrm{𝑣𝑎𝑟}(Q)$ and $\mathrm{𝑎𝑡𝑜𝑚𝑠}(Q)$ to denote the set of variables in $Q$ and the set of atoms in $Q$, respectively, i.e., $\mathrm{𝑣𝑎𝑟}(Q)={\bigcup }_{i=1}^m{𝑿}_i$ and $\mathrm{𝑎𝑡𝑜𝑚𝑠}(Q)=\{R_i({𝑿}_i)\mid 1\le i\le m\}$. If $𝑿,𝒀$ are two sets of variables and $𝒙\in {\mathrm{𝐝𝐨𝐦}}^{𝑿}$, then we denote by $𝒙[𝒀]$ the projection of $𝒙$ on the variables $𝑿\cap 𝒀$. Throughout this paper we fix an infinite domain $\mathrm{𝐝𝐨𝐦}$ and we write ${\mathrm{𝐚𝐝𝐨𝐦}}_i$ to denote the (finite) set of domain values actually occurring in attribute $A_i$ in the given database $D$, i.e., the active domain of $A_i$.

Unless mentioned otherwise, we consider set semantics. Then the semantics of $Q$ in Eq. (1) on a database $D$ is the relation ${⟦Q⟧}^D\subseteq {\mathrm{𝐝𝐨𝐦}}^{𝑿}$ defined as

Sometimes, we will switch to bag semantics. Then the semantics of $Q$ in Eq. (1) on a database $D$ is a mapping ${⟦Q⟧}^D:{\mathrm{𝐝𝐨𝐦}}^{𝑿}\to \mathbb{N}$, which assigns to every $𝒙\in {\mathrm{𝐝𝐨𝐦}}^{𝑿}$ the cardinality $|\{𝒚\in {\mathrm{𝐝𝐨𝐦}}^{\mathrm{𝑣𝑎𝑟}(Q)\setminus 𝑿}\mid \text{ for every }i,(𝒙,𝒚)[{𝑿}_i]\in R_i^D\}|$. We will mostly consider Boolean queries and, in this case, under bag semantics we have to count the number of tuples $𝒙\in {\mathrm{𝐝𝐨𝐦}}^{\mathrm{𝑣𝑎𝑟}(Q)}$ that satisfy the right hand side of Eq. (1). We may omit the superscript $D$ when it is clear from the context, and simply write $R_i$, $⟦Q⟧$.

Let $𝒀\subseteq \mathrm{𝑣𝑎𝑟}(Q)$ be a set of variables. A fractional edge cover of $𝒀$ (with respect to $Q$) is a weight function $w:\mathrm{𝑎𝑡𝑜𝑚𝑠}(Q)\to [0,1]$, such that, for every variable $A\in 𝒀$, ${\sum }_{i:A\in {𝑿}_i}w(R_i({𝑿}_i))\ge 1$. The fractional edge cover number of $𝐘$, denoted ${\rho }^{\ast }(𝒀)$, is the minimum value of ${\sum }_{i}w(R_i({𝑿}_i))$ attainable by fractional edge covers $w$ of $𝒀$. Due to [4], we know that ${|D|}^{{\rho }^{\ast }(𝒀)}$ is an upper bound on the number of tuples $𝒚\in {\mathrm{𝐝𝐨𝐦}}^{𝒀}$ that satisfy the query $Q$ restricted to the variables $𝒀$¹¹1Formally, we mean that for every $R_i$ there has to exist an ${𝒙}_i\in R_i$ such that ${𝒙}_i[𝒀]=𝒚[{𝑿}_i]$..

A CQ is called acyclic (an ACQ, for short), if it has a join tree, i.e., a labeled tree $⟨T,\lambda ⟩$ with node-labeling function $\lambda$ such that (1) for every relation $R_i$ there exists exactly one node $u$ of $T$ with $\lambda (u)=R_i$ and (2) $\lambda$ satisfies the so-called connectedness condition, i.e., if some attribute $A$ occurs in both relations $\lambda (u)$ and $\lambda (v)$ for two nodes $u,v$ of $T$, then $A$ occurs in the relation $\lambda (w)$ for every node $w$ on the path between $u$ and $v$.

Yannakakis [36] has shown that ACQs can be efficiently evaluated (that is, essentially, linear w.r.t. the input+output data and linear w.r.t. the size of the query) via 3 traversals of the join tree: (1) a bottom-up traversal of semi-joins, (2) a top-down traversal of semi-joins, and (3) a bottom-up traversal of joins. Formally, let $u$ be a node in $T$ with child nodes $u_1,\mathrm{\dots },u_k$ of $u$ and let relations $R$, $R_{i_1},\mathrm{\dots },R_{i_k}$ be associated with the nodes $u$, $u_1,\mathrm{\dots },u_k$ at some stage of the computation. Then we set

1. (1)

   $R=(((R⋉R_{i_1})⋉R_{i_2})\mathrm{\cdots })⋉R_{i_k}$,

2. (2)

   $R_{i_j}=R_{i_j}⋉R$ for every $j\in \{1,\mathrm{\dots },k\}$, and

3. (3)

   $R=(((R\bowtie R_{i_1})\bowtie R_{i_2})\mathrm{\cdots })\bowtie R_{i_k}$

in the 3 traversals (1), (2), and (3). The final result of the query can be read off from the resulting relation associated with the root $r$ of $T$. Importantly, in case of a Boolean CQ, only the first bottom-up traversal of semi-joins is needed: a Boolean CQ evaluates to true, iff this bottom-up traversal yields a non-empty relation at the root $r$ of $T$.

In this paper, we examine the data complexity of evaluating CQs with various types of query plans, i.e., we measure the space and time complexity as exponentials w.r.t. an upper bound $N$ on the number of tuples in the given database $D$. We consider a query plan $\mathrm{\Pi }$ for a query $Q$ as a structure that is associated with a specific algorithm for evaluating $Q$, e.g., in case of an ACQ $Q$, we may consider a join tree as a query plan, which is associated with Yannakakis’ algorithm. We denote a class of plans by $𝒞$, e.g. all tree decompositions, and the plans of $𝒞$ for a query $Q$ as $𝒞(Q)$. Each plan $\mathrm{\Pi }$ is associated with a space exponent $s(\mathrm{\Pi })$ and a time exponent $t(\mathrm{\Pi })$. The latter bounds the associated algorithm’s runtime by $\tilde{O}({|D|}^{t(\mathrm{\Pi })})$. The former bounds the space used by the algorithm by $O({|D|}^{s(\mathrm{\Pi })})$, excluding the space required to store the input relations. We refer to these jointly as space-time exponents $e(\mathrm{\Pi })=(s(\mathrm{\Pi }),t(\mathrm{\Pi }))$.

Several forms of decompositions have been proposed to make use of structural properties of the query in the quest for efficient query evaluation algorithms. The most fundamental form are tree decompositions (TDs, for short). They were originally introduced for graphs [31]. In case of queries (notably CQs), the underlying structure is best captured by hypergraphs. In principle, we could therefore associate with every hypergraph a graph and define TDs of a hypergraph as TDs of the corresponding graph. We prefer to define TDs (and, based on TDs, the other forms of decompositions studied here) directly for CQs without taking the detour via the underlying hypergraph and an associated graph. Our notion of TDs corresponds to the definition of the TD via the “primal graph” of the hypergraph, i.e., the graph whose vertices are identical with the vertices of the hypergraph and two vertices are adjacent in the graph if they jointly occur in some hyperedge. This is arguably the most common way of defining the TD of a hypergraph and, ultimately, of a CQ, but not the only possible way, e.g.: in [9], TDs defined via the so-called “incidence graph” were considered.

The sets $\chi (v)$ are called bags. The width of a TD is the maximum size of its bags minus 1, i.e., $width(T,\chi )={\max }_v(|\chi (v)|)-1$. The tree-width $\text{tw}(Q)$ of a CQ $Q$ is defined as the minimum width attainable by a TD of $Q$, i.e., $\text{tw}(Q)={\min }_{(T,\chi )}(width(T,\chi ))$. Note that, usually, TDs are considered as undirected trees. However, since we want to use TDs as query plans, it is more convenient to consider TDs as directed trees, since we will ultimately evaluate a (Boolean) CQ by a bottom-up traversal of the tree.

A straightforward way of evaluating a CQ $Q$ by making use of a TD is to compute and materialize, for every node $v$, the query restricted to the variables in the bag $\chi (v)$ to turn the CQ into an ACQ and then to apply Yannakakis’ algorithm. Hence, the principal source of complexity when using a TD for query evaluation are the subqueries $Q^v$ corresponding to each bag. Clearly, there is a choice as to what plan we use to compute the subqueries $Q^v$. The most naive evaluation consists in associating with each bag with variables $X_{i_1},\mathrm{\dots },X_{i_{\alpha }}$ the relation obtained by computing the query restricted to those atoms which are covered by $\chi (v)$ and extending the result to the variables not contained in the subquery by allowing these variables to take any value from their active domain. That is, for every node $v\in V$, we compute the subquery $Q^v=\left({\bowtie }_{i\in I^v}{R}_i\right)\times \left({\times }_{j\in J^v}{\mathrm{𝐚𝐝𝐨𝐦}}_j\right)$, where the index sets $I^v$ and $J^v$ are defined as $I^v=\{i\mid {𝑿}_i\subseteq \chi (v)\}$ and $J^v=\{A_j\mid A_j\in \chi (v)$ and $\mathrm{\nexists }i\in I^v$ with $X_j\in {𝑿}_i\}$, respectively. We can then transform $Q$ into an equivalent ACQ ${\bowtie }_{v\in V}{Q}^v$ and evaluate this ACQ by applying Yannakakis’ algorithm to it. The space and time exponents of this approach are essentially $(\text{tw}(Q)+1,\text{tw}(Q)+1)$ (cf. [10]).

A better evaluation strategy was proposed in [17] by extending TDs to hypertree decompositions (HDs, for short):

The width of an HD is the maximum size of its $\lambda$-labels, i.e., $width(T,\lambda ,\chi )={\max }_v(|\lambda |)$. The hypertree-width $\text{hw}(Q)$ of a CQ $Q$ is defined as the minimum width attainable by an HD of $Q$, i.e., $\text{hw}(Q)={\min }_{(T,\lambda ,\chi )}(width(T,\lambda ,\chi ))$. Note that the fourth condition in Definition 4 was introduced in [17] only to make the problem of deciding, if $\text{hw}(Q)\le k$ holds, tractable for fixed $k\ge 1$. When using an HD for query evaluation, this condition is irrelevant. If we drop the fourth condition, we get Generalized Hypertree Decompositions (GHDs, for short) with generalized hypertree-width, denoted $\text{ghw}(Q)$ as the associated width measure [2]. Clearly, GHDs generalize HDs and $\text{ghw}(Q)\le \text{hw}(Q)$ holds for every CQ $Q$. The downside of GHDs is that even deciding if $ghw(Q)\le 2$ for given query $Q$ holds, is NP-complete [18, 16].

Bounded hw and bounded ghw generalize acyclicity in that ACQs are precisely the CQs with $\text{hw}=\text{ghw}=1$. In order to turn a CQ with given HD or GHD into an ACQ, we just need to join the relations in the $\lambda$-label and project the result to the $\chi$-label for every node $v\in V$. That is, for every $v\in V$, we compute the subquery $Q^v={\pi }_{\chi (v)}\left({\bowtie }_{R_i\left({𝑿}_i\right)\in \lambda \left(v\right)}{R}_i\right)$. The resulting ACQ ${\bowtie }_{v\in V}{Q}^v$ can then be evaluated by applying Yannakakis’ algorithm. We thus get the space-time exponents $(\text{hw}(Q),\text{hw}(Q))$ and $(\text{ghw}(Q),\text{ghw}(Q))$, respectively [17].

A further refinement of this technique was proposed in [20] by introducing fractional hypertree decompositions (FHDs, for short):

The width of an FHD is defined as the maximum weight of its $\gamma$-labels, i.e., $width(T,\gamma ,\chi )={\max }_v({\sum }_i\gamma (v)(R_i({𝑿}_i)))$. The fractional hypertree-width $\text{fhw}(Q)$ of a CQ $Q$ is defined as the minimum width attainable by an FHD of $Q$, i.e., $\text{fhw}(Q)={\min }_{(T,\gamma ,\chi )}(width(T,\gamma ,\chi ))$. In order to turn a CQ with given FHD into an ACQ, we need to evaluate the query $Q$ restricted to the variables in $\chi (v)$ for every $v\in V$, i.e., $Q^v(\chi (v))={\bigwedge }_{i=1}^m{R}_i({𝑿}_i\cap \chi (v))$. By using a WCOJ method such as Generic Join [29], the maximal output size and the time for evaluating such a query $Q^v$ over a database $D$ is $O({|D|}^{{\rho }^{\ast }(\chi (v))})$. The resulting ACQ ${\bowtie }_{v\in V}{Q}^v$ can then be evaluated by Yannakakis’ algorithm, leading to the space-time exponents $(\text{fhw}(Q),\text{fhw}(Q))$ [20].

For every CQ $Q$, we clearly have $\text{fhw}(Q)\le ghw(Q)\le \text{hw}(Q)\le \text{tw}(Q)+1$. Hence, treating a TD as an FHD and evaluating the subqueries at each bag by some WCOJ techniques in order to turn $Q$ into an ACQ, is optimal among the decomposition methods discussed in this section. As mentioned, e.g., in [11], one can even do better space-wise. More specifically, it suffices to materialize only the subqueries restricted to the variables in the intersection between the bags at a node and its parent. To each vertex $v\in V$ of a TD $(T,\chi )$, we thus associate a query as follows. Let ${𝒀}^v:=\chi (v)$ and ${𝒁}^v:=\chi (v)\cap \chi (\mathrm{𝑝𝑎𝑟𝑒𝑛𝑡}(v))$ or, if $v$ is the root node, then ${𝒁}^v:=\mathrm{\varnothing }$. Then we compute, in a bottom-up traversal of the TD, the queries

Using a WCOJ method such as Generic Join for evaluating each of these subqueries, we end up with the space-time exponents $s(T,\chi )={\max }_{(u,v)\in E(T)}{\rho }^{\ast }(\chi (u)\cap \chi (v))$ and $t(T,\chi )={\max }_{v\in V(T)}{\rho }^{\ast }(\chi (v))$. The latter is equal to $\text{fhw}(T,\chi )$, if $(T,\chi )$ is the TD underlying an FHD of minimum width.

In this section, we discuss pseudo-trees [15, 11] together with several extensions. It will turn out that WCOJ algorithms such as Generic Join [29] can actually be seen as a special case of pseudo-tree-based algorithms. We therefore revisit Generic Join (GJ)) query plans first.