Database Theory in Action: Evaluation of Aggregate Queries Without Materialisation

Conjunctive queries (CQs) are arguably the most fundamental type of queries on relational databases. However, as the number of relations to be joined grows, their evaluation gets more and more challenging. A major source of the computational complexity of CQs is the potential explosion of intermediate results. In case of acyclic conjunctive queries (ACQs), Yannakakis’ algorithm [13] reduces this problem to some extent by eliminating dangling tuples via semi-joins before the actual join computation. However, for large ACQs, the (intermediate) join results may still become prohibitively big. This is particularly frustrating in case of aggregate queries where one first evaluates big joins but ultimately only outputs a small aggregated result. Advanced optimisation techniques like AJAR [4] and FAQs [5] do propose general techniques for aggregate queries, but are unfortunately incompatible with the architectures of the query evaluation engines of typical relational DBMS.

There are special cases of ACQs where the problem of exploding (intermediate) join results simply does not exist: above all, this applies to Boolean ACQs, which can be solved by a bottom-up traversal of the join tree via semi-joins. In [1, 2], a very restricted class of aggregate queries (so-called Zero-Materialisation Aggregate queries, 0MA for short) was presented, for which the result can be read off at the root node of the join tree after the bottom-up traversal via semi-joins. The goal of our work is to identify a big class of aggregate queries that can also be evaluated by a bottom-up traversal via semi-join-like operations without materializing any join results. Formally, we study queries of the following form:

where $\gamma [g_1,\mathrm{\dots },g_{\mathrm{\ell }},A_1(a_1),\mathrm{\dots },A_m(a_m)]$ denotes the grouping operation for attributes $g_1,\mathrm{\dots }$, $g_{\mathrm{\ell }}$ and aggregate expressions $A_1(a_1),\mathrm{\dots },A_m(a_m)$ for some (standard SQL) aggregate functions $A_1,\mathrm{\dots },A_m$ applied to expressions $a_1,\mathrm{\dots },a_m$. The grouping attributes $g_1,\mathrm{\dots },g_{\mathrm{\ell }}$ are attributes occurring in the relations $R_1,\mathrm{\dots },R_n$ and $a_1,\mathrm{\dots },a_m$ are expressions formed over the attributes from $R_1,\mathrm{\dots },R_n$.

The crucial concept to arrive at a class of aggregate queries that can be evaluated without the need to compute any joins is guardedness. More precisely, we call a query of the form in (1) a guarded aggregate query, if $(R_1\bowtie \mathrm{\cdots }\bowtie R_n)$ is acyclic and there exists a relation $R_i$ (= the guard) that contains all attributes that are either part of the grouping or occur in one of the aggregate expressions. If several relations have this property, we may arbitrarily choose one as the guard. The key idea for an efficient (join-less) evaluation of guarded queries is to propagate cardinalities of join results rather than the join results themselves in a bottom-up traversal of the join tree. It is then possible to evaluate any SQL aggregate operator at the root node of the join tree by taking these cardinalities into account.

In fact, we can further relax the requirement of the existence of a single guard for all of the grouping and aggregation attributes. To this end we introduce the class of piecewise guarded aggregate queries. Here, we only require the existence of a guard for the grouping attributes and guards for the aggregate expressions; but, in case of the most common aggregate operators MIN, MAX, COUNT, SUM, and AVG, every aggregate expression may have a different guard. As we outline in Section 2, such queries can be evaluated by attaching aggregated information to tuples during the bottom-up traversal of the join tree, without computing joins. The number of tuples thus propagated is the same as in case of the semi-join bottom-up traversal for Boolean ACQs. This class of queries covers a large proportion of common benchmarks (e.g., 100% of JOB [7] and STATS-CEB [3]). We have implemented our optimisation in Spark SQL and our experiments (Section 3) on several standard benchmarks clearly demonstrate the efficacy of this approach.

We evaluate guarded aggregate queries without propagating any join results up the join tree, by adapting the extension of Yannakakis’ algorithm for COUNT(*) from [10]. To describe the main ideas, we introduce the following notation: let $T$ be a join tree of the query such that the root node is labelled by the guard relation; let $u$ denote a node in $T$ and let $T_u$ denote the set of all nodes in the subtree rooted at $u$. Moreover, let $R(u)$ denote the relation labelling node $u$ and let $\mathrm{𝐴𝑡𝑡}(u)$ denote the list of attributes of $R(u)$. The goal of the bottom-up propagation of cardinalities is to evaluate, for every node $u$ in $T$, the following query:

Conceptually, this is the result of joining all relations in the subtree rooted at $u$, grouped by the attributes occurring in the relation at $u$, and COUNT(*) for each group. Of course, we do not actually compute these joins. Instead, in the style of semi-joins, we compute the COUNT(*) values by a semi-join-like bottom-up traversal of the join tree. However, rather than just checking for each tuple $t\in R(u)$ the existence of a join partner in the subtree below, we compute the number $c_t$ of join partners of $t$. This is done by initializing the cardinality attribute $c_t$ to 1 for every $t$. For internal nodes $u$ of $T$, we visit each child $v$ of $u$ (one at a time), sum up the cardinalities of all join partners of $t$ in $R(v)$ and multiply $c_t$ with this sum.

When the bottom-up propagation of cardinalities has reached the root node $r$ of the join tree $T$, we can evaluate the group-by and aggregation based on the resulting relation (extended by the cardinality attribute) at $r$. By definition, the guard contains all grouping attributes. Hence, we can evaluate the group-by solely based on $R(r)$. For the evaluation of the aggregates, we take the additional information of the cardinality attribute into account. For instance, COUNT(*) is obtained as the sum over the $c_t$ values for all tuples in the considered group. SUM(B) has to sum up the values $B\cdot c_t$ for all tuples $t$, taking NULLs into account. For details of the cardinality propagation and the evaluation of the remaining aggregate operators, see the full paper [6].

In case of piecewise guarded aggregate queries, we may have to deal with different guards for the grouping attributes and for the various aggregate expressions. We choose as root of the join tree a guard of the grouping attributes. As before, each relation is extended by a cardinality attribute, which is propagated bottom-up in the join tree $T$ as described before. Aggregate expressions whose guard is the relation $R(r)$ at the root node $r$ are processed as before. For an aggregate expression $A_j(a_j)$ which is not guarded by $r$, we choose as guard the node $w$ that contains all attributes in the expression $a_j$ and which is furthest up in $T$ with this property. We extend the relations at all nodes $u$ on the path between $w$ and the root $r$ by an attribute ${\mathrm{𝐴𝑔𝑔}}_j$ that contains the required aggregated information to ultimately evaluate $A_j(a_j)$. Conceptually, for every such node $u$, we want to evaluate the query

That is, as with the cardinality attribute, we want to compute the join of all relations in the subtree rooted at $u$, group by the attributes occurring in the relation at $u$ and evaluate $A_j(a_j)$ for each group. Again, we determine the concrete values of $A_j(a_j)$ by a semi-join-like operation in a bottom-up traversal of $T$ rather than actually computing the joins. The bottom-up traversal for the aggregate expression $A_j(a_j)$ starts at the node $w$ labelled by the guard of $A_j(a_j)$. The initialisation of ${\mathrm{𝐴𝑔𝑔}}_j$ for each tuple $t\in R(w)$ depends on the concrete aggregate operator. For MIN and MAX, we simply evaluate the expression $a_j$ for each tuple $t$ and take the result as the initial value. ${\mathrm{𝐴𝑔𝑔}}_j$ is initialised according to the operator (value of $a_j$ for MIN/MAX, 0 or $c_t$ for COUNT, $a_j\cdot c_t$ for SUM). The bottom-up propagation of the ${\mathrm{𝐴𝑔𝑔}}_j$ attribute in a semi-join-like style (i.e., without computing any joins) is done similarly to the bottom-up propagation of the cardinalities. For details of the ${\mathrm{𝐴𝑔𝑔}}_j$-propagation and its efficient realisation by a dedicated physical operator, we refer the reader to the full paper [6].

To evaluate our approach for materialisation-free query evaluation, we implemented the methods presented here (for full details, see [6]) in Spark SQL. Notably our implementation naturally integrates into the existing logical and physical query planning steps and operates entirely transparent to the user. Our experiments cover a broad spectrum of standard benchmarks: the Join Order Benchmark (JOB) [7], STATS-CEB [3], TPC-H [12], TPC-DS [11], and the Large-Scale Subgraph Query Benchmark (LSQB) [9]. In addition, we evaluatethe performance on simple graph queries over two real-world graphs from the SNAP (Stanford Network Analysis Project [8]) dataset.

Table 3 summarises the overall performance of our optimisations on the applicable queries. We use Ref to denote unmodified Spark SQL, and GuAO⁺ to denote our implementation with the new optimisations. Results for the SNAP graphs are reported separately in Table 2. In both tables, the fastest execution time is highlighted in bold. Each query is executed 6 times, with the first run being a warm-up run to avoid skew from initial table loads. We report statistics over the final five runs, including the mean execution time and standard deviation. The speed-up achieved by GuAO⁺ over Ref is explicitly stated in Table 3 in the column GuAO⁺ Speedup. For most benchmarks, we report end-to-end (e2e) times for subsequently executing all queries of a given benchmark where our optimisations are applicable (to the full query, or at least one subquery).

Overall, the evaluation shows that our optimisation is broadly applicable and yields substantial performance improvements. On STATS-CEB, we reduce end-to-end runtime by more than 24×, and for LSQB (Q1) by over 4.5×. On JOB, TPC-H, and TPC-DS, the gains are more modest (1–1.6×) but still consistent across queries. Importantly even in these simple cases, very few joins, all on foreign keys, we never observe performance degradation. For SNAP graph queries, the difference is dramatic: GuAO⁺ executes all path and tree queries in under 11 seconds, while Spark SQL frequently times out or runs out of memory.

We identified a widely applicable class of aggregate database queries that can be evaluated without materialising, or even computing, joins. Our Spark SQL implementation integrates seamlessly into existing systems, and experimental results demonstrate substantial performance gains. Future work includes lifting the restrictions of acyclicity and guardedness, for example via decomposition techniques and richer information propagation.