Large intermediate results can cause join queries to run unexpectedly long. This problem is particularly common for analytical queries, which aggregate data over many tables to produce a comparatively small final output, and queries on graph data, where intermediate results blow up quickly. Recent work inspired by Yannakakis' algorithm approaches this by modifying the query engine to avoid materializing unnecessary tuples. However, this requires significant changes to the core of the system, which is not feasible in many situations such as cloud environments or proprietary systems. In this work, we propose a flexible approach for optimizing long-running join queries from the outside of the DBMS. Rewriting-based realizations of Yannakakis' algorithm sufer from inherent overhead due to the creation of intermediate tables. Thus, we present an approach for detecting and targeting queries which would benefit from a Yannakakis-style optimization. We introduce a new benchmark combining 5 standard benchmarks and augmenting them with additional instances, which provides a suficient size and diversity for a machine learning based solution. On PostgreSQL, DuckDB and SparkSQL, slowdowns on queries where the rewriting is counterproductive are mostly avoided, as opposed to a naïve application of the rewriting, and we observe significant improvements in end-to-end runtimes over standard query execution and unconditional rewriting.
Join queries can exhibit unexpectedly long runtimes when intermediate results grow significantly larger than the final result. This problem is common in analytical queries, which aggregate data over many tables but intentionally produce compact outputs, and queries over graph data, where the intermediate results explode quickly due to the connectedness of the data.
Yannakakis’ algorithm [
Recent work has brought renewed attention to integrating Yannakakis-style query evaluation into
database systems [
SELECT MIN(c.Id) FROM comments AS c, posts AS p, votes AS v, users AS u WHERE u.Id = p.OwnerUserId AND u.Id = c.UserId AND u.Id = v.UserId AND u.Views>=0 AND p.Score>=0 AND p.Score<=28 AND p.ViewCount>=0 AND p.ViewCount<=6517 AND p.AnswerCount>=0 AND p.AnswerCount<=5 AND p.FavoriteCount>=0 AND p.FavoriteCount<=8 AND c.CreationDate>='2010-07-27 12:03:40' AND p.CreationDate>='2010-07-27 11:29:20' AND p.CreationDate<='2014-09-13 02:50:15' AND u.CreationDate>='2010-07-27 09:38:05'
An alternative that avoids these limitations is to realize Yannakakis-style query evaluation via SQL
query rewriting [
Rewriting-based approaches, however, introduce overhead due to the execution of multiple SQL statements from outside of the system, and the creation of temporary tables for storing intermediate results. This has the efect that Yannakakis-style rewriting does not always improve the performance, even for queries where the algorithm should in theory be optimal.
The query in Figure 1, a slightly modified version of a query from the STATS benchmark [
In theory, the advantage of such a join-less evaluation is clear over conventional query evaluation techniques that first fully evaluate the underlying join query and only then apply the aggregate as a kind of post-processing. For the query in Figure 1, Yannakakis-style evaluation was faster by a factor of roughly 30 times compared to the standard execution of PostgreSQL. However, when changing one of the filter conditions in the WHERE clause from ≥ 0 to ≥ 8 (which, together with the ≤ 8 condition, yields = 8), this reverses and the standard execution of PostgreSQL is faster, taking 0.05s compared to the rewriting with 0.09s. This example illustrates a fundamental challenge with Yannakakis-style rewriting in practice: we require a method to decide when to apply it. It also shows that making such a decision is non-trivial, since small changes to the query can have significant efects in the efectiveness of Yannakakis-style execution.
In this work, we address this challenge by developing a decision procedure that predicts whether Yannakakis-style rewriting will improve the performance for a given query. We frame this as an algorithm selection problem and solve it using lightweight machine learning models.
To cover various database technologies, we study three diverse DBMSs: PostgreSQL [
Contributions. • We develop a flexible and robust query rewriting tool based on Apache Calcite. Compared to earlier implementations, it allows for greater applicability to complex queries and straightforward adaptation to new systems and SQL dialects. • We present a decision procedure for selectively applying the Yannakakis-style query rewriting based on features derived from the query structure as well as DBMS cost estimates. We show that simple models (decision/regression trees) outperform more complex approaches, achieving high accuracy while allowing fine-grained control over the precision-recall tradeof. • We introduce a new dataset and benchmark – focusing on hard join queries – which is extensive and diverse enough for efective model training and testing. This new benchmark, which we will refer to as MEAMBench (Materialization Explosion Augmented Meta Benchmark) is constructed by combining and augmenting queries from several common benchmarks. Beside the algorithm selection problem we are focusing on here, we expect this dataset to be valuable also for other problems, such as query performance prediction. • To prove the practical potential of the introduced approach, we implement the system SMASH, short for Supervised Machine-learning for Algorithm Selection Heuristics. SMASH supports multiple DBMSs, including PostgreSQL, DuckDB and SparkSQL, and comprises all steps from feature extraction and algorithm selection up to rewriting. • Empirical evaluation on MEAMBench clearly confirms significant improvements in end-to-end (e2e) runtimes and decreases in false-positive applications of the rewriting through SMASH compared with the original query evaluation method of the DBMS or unconditionally rewriting.
The queries studied here are either Conjunctive Queries (CQs, i.e., select-project-join queries in Relational Algebra) and, more generally, queries with grouping and aggregation on top: = 1,...,ℓ, 1(1),...,()︀( 1 ◁▷ · · · ◁▷ )︀ (1) where 1,...,ℓ, 1(1),...,() denotes the grouping operation for attributes 1, . . . , ℓ and aggregate expressions 1(1), . . . , (). The grouping attributes 1, . . . , ℓ are attributes occurring in the relations 1, . . . , , the functions 1, . . . , are (standard SQL) aggregate functions such as MIN, MAX, COUNT, SUM, AVG, etc., and 1, . . . , are expressions formed over the attributes from 1, . . . , . We have omitted the projection in Equation (1), since it can be taken care of by the grouping. Moreover, we assume w.l.o.g. that equi-joins have been replaced by natural joins via appropriate renaming of attributes and selections applying to a single relation have been pushed immediately in front of this relation and the ’s are the result of these selections. A simple query of the form of Equation (1) is given in SQL-syntax in Figure 1.
An acyclic conjunctive query (an ACQ, for short) is a CQ = (1 ◁▷ . . . ◁▷ ) that has a join tree,
i.e., a rooted, labeled tree ⟨, , ⟩ with root , such that (1) is a bijection that assigns to each node of
one of the relations in {1, . . . , } and (2) satisfies the so-called connectedness condition, i.e., if
some attribute occurs in both relations () and ( ) for two nodes and , then occurs in the
relation () for every node along the path between and . Actually, the join query underlying
the SQL query in Figure 1 is acyclic. A possible join tree is shown in Figure 2. In its original form,
Yannakakis’ algorithm [
A restricted type of queries of the form given in Equation (1) is the class of 0MA queries (short for
“zero-materialization answerable”) queries (see [
users posts votes • Set-safety: we call an aggregate function set-safe, if it is invariant under duplicate elimination, i.e., its value over any set of tuples remains unchanged if duplicates are eliminated from . A query satisfies the set-safety condition, if all its aggregate functions 1 . . . , are set-safe.
The root of the join tree can be arbitrarily chosen. For a 0MA query, we choose the node labeled by the guard as the root node. Hence, if all aggregate functions are set-safe (i.e., multiplicities do not matter), then we can apply the grouping and aggregation 1,...,ℓ, 1(1),...,() to the relation at the root node right after the first bottom-up traversal. In SQL, in particular, the MIN and MAX aggregates are inherently set-safe. Moreover, an aggregate becomes set-safe when combined with the DISTINCT keyword. For instance, COUNT DISTINCT is a set-safe aggregate function.
An example of a 0MA query is given in Figure 1: it is trivially guarded (i.e., there is no grouping and the only aggregate expression is over a single attribute) and set-safe (since the only aggregate function in this query is MIN).
Acyclic queries and Yannakakis-style query evaluation. Yannakakis’ algorithm [
Decompositions. In order to go beyond acyclic queries, a major area of research seeks to extend
Yannakakis-style query answering to "almost-acyclic" queries via various notions of decompositions and
their associated width measures, such as hypertree-width, soft hypertree-width, generalized
hypertreewidth, and fractional hypertree-width [
Query performance prediction. Predicting the performance of a query – usually the runtime, or sometimes
the resource requirements – is related to the problem of deciding whether to rewrite a query. Runtime
prediction has been performed by constructing cost models based on statistical information of the
data [
Benchmark
Queries
Data augmentation
Rewritten Queries
Rewriting Augmented
Queries
Runtime measurements
Feature extraction
Runtimes
Query
Features
As illustrated in Section 1, a Yannakakis-style rewriting does not always improve the performance, even for queries where it would be expected based on the reduction in intermediate results. To benefit from the rewriting in practice, it is clear that we require a decision procedure for the selective application of the rewriting. We are thus faced with an algorithm selection problem, where we have to decide, for every database instance and query, which query evaluation method should be applied. In this section, we describe our approach towards solving this algorithm selection problem. We develop a pipeline, starting from the databases and queries, and resulting in a decision procedure. In the process of this, we create a new implementation for query rewriting using Apache Calcite. An overview of the workflow is given in Figure 3.
Robust and Flexible Yannakakis-style Query Rewriting We improve upon the approach of [
We take a SQL query as input and first transform it into a hypergraph. The approach of [
We illustrate the query rewrite process for the 0MA query , which is shown, with its join tree, in Figure 4. Note that, in this example, for each relation in the query, as well as its associated filters (involving only attributes in the relation), a view is created. Overhead due to this can be slightly reduced in practice by integrating the selections and filters of the CREATE VIEW statements into the CREATE UNLOGGED TABLE statements.
The implementation makes use of Apache Calcite [
WHERE u.Id=v.UserId AND v.UserId=b.UserId
AND v.BountyAmount>=0 AND v.BountyAmount<=50 AND u.DownVotes=0
if attributes are referred to implicitly, the schema is required to resolve the reference), is extracted
directly from the DBMS over the JDBC interface. The logical plan resulting from the SQL string is next
transformed into a convenient intermediate representation via query optimizer rules, where all filters are
pushed to the bottom of the plan, which allows us to retrieve a set of subtrees. These subtrees of the plan,
corresponding to the hyperedges, are followed by equi-join operator nodes, from which the hypergraph
can be constructed. The approach of using the parser and optimizer of Apache Calcite, as opposed to
earlier works [
We focus on ACQs, which make up the vast majority of the queries in the base benchmarks. The number of (acyclic) CQs of each dataset is given in Table 1. Some of the queries in the benchmarks are enumeration queries and some already contain some aggregate (in particular, MIN) and satisfy the 0MA conditions. Clearly, also from the enumeration queries, we can derive 0MA queries by an appropriate aggregate expression (again, in particular, with the MIN aggregate function) in the SELECT clause of the query. For this, we randomly choose a table occurring in the query and one column of this table. Our collection of data and queries from diferent benchmarks results in 219 acyclic queries. This is still not suficient for training and testing ML models. We, therefore, perform the following steps for data augmentation: “filter augmentation” (for all queries) followed by “aggregate-attribute augmentation” (for 0MA-queries) and “enumeration augmentation” (for enumeration queries), respectively.
Through the “filter augmentation” we produce duplicates of all queries having filters (i.e., selection conditions on a single table) by changing some filters in a way that the sizes of the resulting relations vary between these queries. In fact, the SNAP and LSQB queries do not have filter conditions, which means that there is no filter augmentation for them. For 0MA queries, we next apply the “aggregate-attribute augmentation” to vary the table from which we take the MIN-attribute. This is done in a way that every table occurring in the query appears once in the MIN-expression. For enumeration queries, we randomly choose two of the attributes used in join conditions and write them into the SELECT clause of the query. In summary, after applying the data augmentation step, we have obtained 4677 queries in total (see Table 1). The MEAMBench benchmark can be found here: https://github.com/dbai-tuw/MEAMBench. Feature Extraction and Selection We choose a variety of features that we derive from the structure of the query itself, from the join tree constructed in the process of rewriting the query, and from statistics determined by PostgreSQL or DuckDB over the database. The latter kind of features is extracted from the query optimizer’s estimates, and obtained via the EXPLAIN command. Note that Spark SQL does not provide an EXPLAIN command. However, we will explain below how to circumvent this shortcoming. Another challenge are features that are based on a set, of variable length, containing numeric values. In order to reduce such a set of values into a fixed-length list of values, we calculate, for each set, several statistics: min, the 0.25-quantile (referred to as q25), median, the 0.75-quantile (referred to as q75), max, and mean. In the list of features below, we use “* ” (e.g. B7*) to mark which features consist of variable-length sets, and hence will get reduced to the mentioned collection of 6 values. Features derived from the query. The following features are easily obtained by inspecting the query itself: Feature B1: is 0MA? indicates (1 or 0) if the query is 0MA, Feature B2: number of relations, Feature B3: number of conditions, the number of (in)equality conditions in the WHERE clause, Feature B4: number of filters , the number of (in)equality conditions occurring in the query, and Feature B5: number of joins.
Features based on the join tree. These features are inspired by the work in [
These eight features (B1)-(B8*) are the shared "basic features". In addition, we can use statistical information from the database and the estimates for the query evaluation, though the exact features that are exposed difers between DBMSs. In case of PostgreSQL and DuckDB, we have the EXPLAIN command at our disposal to obtain relevant further information. For PostgreSQL, we thus select the following additional features, which we refer to as "PSQL features": Feature P1: estimated total cost (of the query), Feature P2*: estimated single table rows, which stands for the estimated number of rows for each table involved in the query after the application of the filter conditions, and Feature P3*: estimated join rows, the estimated number of rows of each join before the application of the filter conditions.
The EXPLAIN command for DuckDB behaves diferently. It allows us to derive a single "DDB feature": Feature D1*: estimated cardinalities, the estimated number of rows after each node in the logical plan, such as filters and joins.
As Spark SQL (the open-source version) does not perform cost-based optimization, it also does not keep track of statistical information about the data, and cannot estimate cardinalities or costs of a plan. However, since SparkSQL also does not provide a persistent storage layer, tables are commonly imported from another database via JDBC. This implies that, in practice, the statistical features can easily be extracted from this database and used for the decision whether to rewrite the query in SparkSQL. For the experiments presented in Section 5, we extracted these features from PostgreSQL, hence SparkSQL has the same feature set as PostgreSQL.
Model Training and Evaluation Our ultimate goal is the development of a decision procedure, for making a binary decision between two evaluation methods for acyclic queries. Hence, we are dealing with a classification problem with 2 possible outcomes. We will refer to these two possible outcomes as 0 vs. 1 to denote the original evaluation method of the DBMS vs. a Yannakakis-style evaluation (enforced by our query rewriting). Alternatively, we can first address a regression problem that predicts the runtime diference between the two query evaluation techniques and then classify a query as 0 (if the predicted value suggests faster evaluation by the original method of the DBMS within a certain threshold) or 1 (otherwise). We will come back to the selection of an appropriate threshold in Section 5.
We have considered 7 Machine Learning model types for our algorithm selection problem, namely
k-nearest neighbors (k-NN), decision tree, random forest, support vector machine (SVM), and 3 forms
of neural networks (NNs): multi-layer perceptron (MLP), hypergraph neural network (HGNN) and
a combination of the two. MLP is the “classical” deep neural network type. Hypergraph neural
networks [
After running the 4677 queries on the 3 selected DBMSs, we have to prepare the input data for training the ML models of the 7 types mentioned above. For our supervised learning tasks (classification and regression), we have to label each feature vector for each of the 3 DBMSs. The labeled data can then be split into training data, validation data, and test data – choosing a common ratio of 80:10:10. To get more accurate results, we do 10-fold cross validation. That is, we split the 90% of the data that were chosen for training and validation in 10 diferent ways in a ratio 80:10 into training:validation data and, thus, repeat the training-validation step 10 times.
In order to ultimately choose the “best” model for our decision procedure, we evaluate, for every feature vector, the predicted classification compared to the optimal decision. This leads to 4 possible outcomes comparing between predicted and actual value, namely TP (true positive) and TN (true negative) for correct classification and FP (false positive) and FN (false negative) for misclassification. We consider 3 common metrics: accuracy, precision, and recall. The natural goal when selecting a particular model is to maximize the accuracy. However, in our context, we consider the precision equally important. That is, we find it particularly important to minimize false positives, i.e., in case of doubt, it is better to stick to the original evaluation method of the DBMS rather than wrongly choosing an alternative method. Apart from the purely quantitative assessment of a model in terms of accuracy, precision, and recall, we also carry out a qualitative analysis. That is, for each of the misclassified cases, we investigate by how much the chosen evaluation method is slower than the optimal method – again with a focus on false positive classifications.
We now present the experimental results obtained by putting the algorithm selection as described in Section 4 to work. With these experiments, we are aiming to answer the following key questions: Q1 How well can machine learning methods predict whether Yannakakis-style evaluation is preferable over standard execution? Q2 Can we use these machine learning models to gain insights about the circumstances in which Yannakakis-style query evaluation is preferable over standard query execution? Q3 How well does good algorithm selection performance translate to query evaluation times on diferent DBMSs? Q4 To what extent can we optimize for precision while maintaining e2e runtime and accuracy?
Model Performance We compare the performance of various learned models in terms of accuracy, precision, and recall (see Tables 2 and 3). We do this for all queries (i.e., 0MA and enumeration) based on the feature vectors and the runtime data obtained with the 3 chosen DBMSs. It turns out that the simplest models (decision tree and random forest) perform best, with accuracy, precision and recall values well above 0.90.
Fine-tuning Precision and Recall So far we have only considered choosing a threshold of the predicted runtime diference of the regression model at 0 (i.e., if the predicted runtime diference is below this threshold, we choose Yannakakis-style query evaluation, and, otherwise, we opt for the original query execution). However, we can make use of the regression model as a useful tool to configure the trade-of between precision and recall, depending on the requirements of the application. To simplify the presentation, we focus on one DBMS and on one model, namely PostgreSQL and decision trees. The extension to other models and DBMSs is straightforward and yields similar results. In Figure 100% 90% 80% 70% 60% 50% accuracy precision
recall runtime 1295s 1290s 1285s 1280s 1275s 1270s 1265s 0.4 0.2
0.0 threshold 0.2 5, we show how changing the threshold afects the accuracy, precision and recall of the resulting classification model. Clearly, the maximum accuracy is at the 0-threshold. The accuracy, however, continues to be high in the direction of negative thresholds, while falling of quickly in the direction of a positive threshold. In particular, this shows that an optimization of precision can be performed without sacrificing much recall.
To summarize: Table 2 and Table 3 show very high accuracy, precision and recall for decision trees, which allows us to positively answer the key question Q1. In Figure 5 we also get an answer for our key question Q4: by choosing the right threshold one can achieve almost perfect precision, with only modest reductions in accuracy and e2e runtime.
Insights from Decision Trees It is particularly interesting that decision trees are the top-performing
models as they are highly interpretable and can provide us with insights into the features that strongly
afect the prediction. To get a deeper understanding of the impact that the various features have on the
outcome of the decision tree model, we have analyzed their Gini coeficients [
Efects on Database Performance Based on the training and evaluation of various ML models, we choose the decision tree regression model followed by classification with threshold value 0 for our runtime measurements. As mentioned in the introduction, we refer to our method, that decides whether to rewrite to Yannakakis-style evaluation based on the prediction of the decision tree model as SMASH, short for Supervised Machine-learning for Algorithm Selection Heuristics. We have measured these runtimes only on the test set queries, i.e., no queries from these experiments were seen by the model 6,000 4,000 2,000 0
2661 1824 602
SparkSQL 3965 1849 1256 6,000 4,000 2,000 0 5841 2162 1627 6,000 at training time. The whole evaluation is performed on a server with 128GB RAM, a 16-core AMD EPYC-Milan CPU, and a 100GB SSD disk, running Ubuntu 22.04.2 LTS. After a warm-up run, the original query, as well as the rewritten version, is evaluated five times, and then we report the mean of those ifve runs. Fundamentally, we are interested in improving overall query answering performance. We investigate this by analyzing the e2e runtime necessary to answer all queries in the test set, i.e., the time to run all the benchmark queries cumulatively. This includes the time for the algorithm selection included in SMASH, which was around 2 milliseconds in total for all queries together.
We summarize our analysis in Figure 6, where Base refers to the baseline of executing the queries directly in the DBMS, Rewriting refers to unconditionally applying the rewriting for Yannakakis-style evaluation, and SMASH refers to the use of our algorithm selection model as described above. To study the robustness of our approach we perform these experiments on three diferent DBMSs: PostgreSQL, Spark (via SparkSQL), and DuckDB. The significant technical diferences between the three systems provide us with a way to study the performance of our method independently of specific DBMS technologies. We report timeouts as follows: if only one of the evaluation methods (rewriting or base case) times out, then we report in Figure 6 for such queries as runtime the value of the timeout (= 100s). On the other hand, if both evaluation methods time out, we exclude them from the comparison, since algorithm selection cannot afect anything in such a case. Out of the 441 queries involved in the test set, there were 27 queries that timed out for both evaluation methods on PostgreSQL, 13 queries that timed out for both evaluation methods on SparkSQL, and 30 queries that timed out for both evaluation methods on DuckDB.
Consistently, over all systems, we can observe a large improvement of algorithm selection over the other two alternatives. Furthermore, we see that even when unconditionally rewriting, there are significant improvements over the baseline execution for all three systems tested. However, this improvement comes from speedups specifically on queries that are hard for traditional RDBMS execution. These large improvements ofset more common minor slowdowns using the Rewriting approach. Using SMASH we are able to achieve the best of both worlds: major speedups on hard queries without the minor performance degradations. In summary, we can give a strongly positive answer to key question Q3. Our algorithm selection method clearly improves the e2e query evaluation times both significantly and consistently over diferent DBMSs (each with their own trained model).
The Efect of Data Augmentation. We explore the impact of data augmentation on model performance through a focused ablation study, carefully examining the efectiveness of our augmentation strategies. Specifically, we compare models trained on two distinct training sets: one encompassing the fully augmented dataset derived from the complete MEAMBench, and another restricted solely to base queries with all augmented data removed. Table 4 succinctly summarizes this comparison, presenting accuracy, precision, and recall metrics for both the "Base" set comprised of 0MA and enumeration queries without filter augmentation, and the full augmented training set. Our analysis reveals that data augmentation substantially enhances accuracy and recall, with even greater gains in precision.
In this work we addressed the problem of slow join queries caused by large intermediate results. Yannakakis-style query evaluation ofers a solution by eliminating dangling tuples, but recent approaches require modifications to the DBMS internals, which is an option unavailable in many situations.
We thus considered an alternative based on SQL rewriting, which is applicable to any standard DBMS. However, due to the overhead of the external rewriting, it does not always improve performance, even for queries with unnecessary intermediate results. To unlock the potential of the Yannakakis-style rewriting, we developed SMASH, a decision procedure that predicts when rewriting is beneficial. Our experiments on PostgreSQL, DuckDB, and SparkSQL demonstrate significant improvements in e2e runtimes over both standard execution and unconditional rewriting, while largely avoiding slowdowns on queries where the rewriting is counterproductive.
MEAMBench, our new benchmark combining five standard benchmarks extended via data augmentation, focuses on hard join queries and provides suficient size and diversity for training learned models.
Although we focused on acyclic and 0MA queries, the methodology we propose is broadly applicable. It opens the door to more intelligent optimization strategies across a wide range of techniques, including decomposition-based methods for cyclic queries.
This work has been supported by the Vienna Science and Technology Fund (WWTF) [10.47379/ICT2201, 10.47379/VRG18013]. Georg Gottlob and Davide Mario Longo acknowledge support from the PNRR FAIR project Future AI Research (PE00000013), Spoke 9 - Green-aware AI, under the NRRP MUR program funded by the NextGenerationEU initiative.
During the preparation of this work, the authors used Claude and ChatGPT in order to: Grammar and spelling check, paraphrase and reword. After using these tools/services, the authors reviewed and edited the content as needed and take full responsibility for the publication’s content.