Join queries involving many relations pose a severe challenge to today's query optimisation techniques. To some extent, this is due to the fact that these techniques do not pay suficient attention to structural properties of the query. In stark contrast, the Database Theory community has intensively studied structural properties of queries (such as acyclicity and various notions of width) and proposed eficient query evaluation techniques through variants of Yannakakis' algorithm for many years. However, although most queries in practice actually are acyclic or have low width, structure-guided query evaluation techniques based on Yannakakis' algorithm have not found their way into mainstream database technology yet.
Query processing lies at the very heart of database applications and systems – with join queries
arguably being the most fundamental and basic form of queries. A lot of research spanning
over several decades has gone into optimizing queries in general and join queries in particular.
Consequently, in many practical cases, Database Management Systems (DBMSs) perform really
well. However, there still remain queries where today’s DBMSs struggle or simply fail. This is
especially the case with queries that involve the join of many (say 10, 50 or even hundreds of)
relations. Large join queries remain challenging even when all joins are made along foreign key
constraints, one of the most common and basic cases for relational DBMSs. Such queries are
becoming more and more common, e.g., when automatically generated by business intelligence
tools [
The traditional approach to evaluating a join query is to split it into a sequence of two-way
joins. One of the main tasks of query optimisation is then to determine an optimal join order,
which avoids the costly computation of large intermediate results as far as possible. However,
even for moderately large queries, the resulting optimisation problem becomes too dificult to
solve exactly and DBMSs resort to heuristic optimisation techniques. For instance, PostgreSQL
14 by default performs a full search for the optimal plan only up to 11 joins. Sophisticated
pruning methods and parallelisation have been shown to push this threshold higher [
From a theoretical perspective, the problem of avoiding large intermediate results in join queries has long been considered as mostly solved. For acyclic queries, Yannakakis’ algorithm [6] is well known to guarantee query answering without any unnecessary intermediate results by following the inherent tree-like structure of acyclic queries in the evaluation of the query. From there, a rich theory of structural decompositions and related notions of width has been developed [7, 8] that generalises the acyclic case to general queries with guaranteed bounds (relative to some notion of width) on the intermediate results.
A small number of research systems have indeed adopted structural decomposition methods and worst-case optimal join algorithms with highly promising results [9, 10, 11, 12, 13]. However, these are “standalone-systems" (i.e., not integrated into widely used relational DBMSs) and some of the most successful approaches have actually focused on queries that are more of graph theoretical interest and particularly suitable to worst-case optimal joins (e.g., queries with clique, or lollipop graph structure). Therefore, despite all the progress made with applying Yannakakis-style query evaluation to real-world problems and the experience gained with these systems, the principal question remains unanswered:
Can the theory of Yannakakis-style query evaluation of acyclic queries be of use for typical relational queries in mainstream RDBMSs?
Our goal is to study precisely this question and to bridge this gap between the theory
and systems communities. We thus embark on a broad experimental evaluation on a recent
benchmark [
Such an evaluation on mainstream DBMSs is not straightforward due to an apparent mismatch in paradigms between Yannakakis’ algorithm, which operates in multiple phases, and the Volcano iterator model commonly adapted by modern DBMSs. A direct integration of such methods is therefore laborious and shifts the performance question towards a matter of efective implementation and integration, rather than a study of the general viability of the method. Instead, we base our experimental evaluation on a DBMS-agnostic rewriting-based approach to control a Yannakakis-style evaluation from “outside” the DBMS by submitting to the DBMS appropriate SQL statements that correspond to the operations performed by Yannakakis’ algorithm. Using these rewritings, we compare the performance of a structure-guided approach to the standard query execution strategies in three DBMSs: PostgreSQL, DuckDB, and Spark SQL, that were selected as popular representatives of distinct types of DBMS architecture. Our experimental results thus obtained clearly indicate that structure-guided evaluation can indeed bring large performance gains and can thus alleviate some of the most critical pain-points of modern DBMSs.
We assume familiarity with basic database terminology and we very briefly recall only the most important concepts. Consider a Conjunctive Query (CQ) as Relational Algebra expressions of the form = (1 ◁▷ . . . ◁▷ ), where 1, . . . , are pairwise distinct relations and the projection list consists of attributes occurring in the ’s. Then is acyclic, if it has a join tree, i.e., a rooted, labelled tree ⟨, , ⟩ with root , such that (1) is a bijection that assigns to each node of one of the relations in {1, . . . , } and (2) if some attribute occurs in both relations () and ( ) for two nodes and in , then occurs in the relation () for every node along the path between and . Deciding whether a CQ is acyclic and constructing a join tree only requires linear time. Yannakakis’ algorithm [6] to eficiently evaluate acyclic CQs proceeds in 3 traversals of the join tree : (1) in a bottom-up traversal, the relations labelling the child nodes of a node of are semi-joined into the relation labelling ; (2) in a top-down traversal, the relation at a node is semi-joined into the relation at each child node; (3) all relations are finally joined in yet another bottom-up traversal. The projection is easily integrated into this third traversal. The final result of the query is the resulting relation associated with the root node of . If this relation is empty after the first bottom-up traversal, then so is the final result and the traversals (2) and (3) can be omitted.
Our goal is to shed light on the benefit of realizing structure-guided query evaluation by common RDBMSs. We thus do not want to restrict ourselves to a single architecture or query planning and execution strategy. We have therefore chosen three DBMSs based on diferent technologies: PostgreSQL 13.4 [14] as a “classical” row-oriented relational DBMS, the columnbased in-memory system DuckDB 0.4 [15], and the distributed data processing system Spark SQL 3.3 [16].
We have implemented a proof-of-concept system called YanRe, that works by rewriting a query into a sequence of SQL statements which express Yannakakis’ algorithm. This makes our approach easily portable and we can execute it on the three chosen DBMSs uniformly. The system proceeds in several steps: we first extract the CQ from the given SQL query and transform it into a hypergraph, from which we compute a join tree. We then generate individual SQL statements that correspond to the semi-joins1 and joins of an execution of Yannakakis’ algorithm over the join tree.
We perform experiments using a recent benchmark by Mancini et al. [
In Table 1, we summarise our results obtained with two types of experiments for the acyclic
queries in [
In Table 1, the Max, Mean, Med. (Median), and Std. Dev. columns provide statistical information for those queries that terminated within the 20 minutes time limit of the respective case. The number of queries that did not terminate within 20 minutes is stated in the Timeouts column. The number of timeouts is significantly lower with YanRe and the remaining timeouts are primarily due to a prohibitively large number of output tuples. Of course, the discrepancy 1We express semi-joins as usual via the SQL EXISTS operator.
2This can always be achieved by rerooting the jointree. is particularly big (see particularly the Max column) for the min-aggregate queries, where Yannakakis-style evaluation completely avoids materialisation of all joins.
We have presented a first empirical study of Yannakakis’ algorithm in common RDBMSs. Full details are available in [18]. The results, though preliminary, clearly indicate that such a structure-guided approach may indeed allow RDBMSs to handle large join queries that were out of reach before. Our experiments split query evaluation into multiple SQL statements over various temporary tables and naturally leads to some overhead on easy queries, as can be seen in the higher median execution time of YanRe in Table 1. In contrast, queries that are too hard for mainstream RDBMS to solve benefit immensely from evaluation via YanRe. The natural next step is a full-fledged integration of Yannakakis’ algorithm into the RDBMSs to get the best of both worlds.
In [18], we have also looked at “almost acyclic” CQs (i.e., CQs of low hypertree-width). Here, many further challenging research questions wait to be solved: above all, database statistics will have to be considered when computing a “good” decomposition – minimising the width alone is no longer enough.
Acknowledgements Georg Gottlob is a Royal Society Research Professor and acknowledges support by the Royal Society in this role through the “RAISON DATA” project (Reference No. RP\R1\201074). Matthias Lanzinger acknowledges support by the Royal Society “RAISON DATA” project (Reference No. RP\R1\201074). The work of Cem Okulmus is supported by the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation. The work of Reinhard Pichler and Alexander Selzer has been supported by the Vienna Science and Technology Fund (WWTF) [10.47379/ICT2201, 10.47379/VRG18013, 10.47379/NXT22018]; and the Christian Doppler Research Association (CDG) JRC LIVE. [5] W. Fischl, G. Gottlob, D. M. Longo, R. Pichler, Hyperbench: A benchmark and tool for hypergraphs and empirical findings, ACM J. Exp. Algorithmics 26 (2021) 1.6:1–1.6:40. URL: https://doi.org/10.1145/3440015. doi:10.1145/3440015. [6] M. Yannakakis, Algorithms for acyclic database schemes, in: Proc. VLDB, 1981, pp. 82–94. [7] G. Gottlob, N. Leone, F. Scarcello, Hypertree decompositions and tractable queries, J.
Comput. Syst. Sci. 64 (2002) 579–627. URL: https://doi.org/10.1006/jcss.2001.1809. doi:10. 1006/jcss.2001.1809. [8] M. Grohe, D. Marx, Constraint solving via fractional edge covers, ACM Trans. Algorithms 11 (2014) 4:1–4:20. [9] C. R. Aberger, A. Lamb, S. Tu, A. Nötzli, K. Olukotun, C. Ré, Emptyheaded: A relational engine for graph processing, ACM Trans. Database Syst. 42 (2017) 20:1–20:44. URL: https://doi.org/10.1145/3129246. doi:10.1145/3129246. [10] M. Idris, M. Ugarte, S. Vansummeren, The dynamic yannakakis algorithm: Compact and efifcient query processing under updates, in: SIGMOD Conference 2017, ACM, 2017, pp. 1259– 1274. URL: https://doi.org/10.1145/3035918.3064027. doi:10.1145/3035918.3064027. [11] M. Idris, M. Ugarte, S. Vansummeren, H. Voigt, W. Lehner, General dynamic yannakakis: conjunctive queries with theta joins under updates, VLDB J. 29 (2020) 619–653. URL: https://doi.org/10.1007/s00778-019-00590-9. doi:10.1007/s00778-019-00590-9. [12] A. Perelman, C. Ré, Duncecap: Compiling worst-case optimal query plans, in: SIGMOD Conference 2015, ACM, 2015, pp. 2075–2076. URL: https://doi.org/10.1145/2723372.2764945. doi:10.1145/2723372.2764945. [13] S. Tu, C. Ré, Duncecap: Query plans using generalized hypertree decompositions, in: SIGMOD Conference 2015, ACM, 2015, pp. 2077–2078. URL: https://doi.org/10.1145/2723372. 2764946. doi:10.1145/2723372.2764946. [14] M. Stonebraker, G. Kemnitz, The postgres next generation database management system, Commun. ACM 34 (1991) 78–92. URL: https://doi.org/10.1145/125223.125262. doi:10.1145/ 125223.125262. [15] M. Raasveldt, H. Mühleisen, DuckDB: an Embeddable Analytical Database, in: Proc.
SIGMOD 2019, ACM, 2019, pp. 1981–1984. [16] M. Zaharia, R. S. Xin, P. Wendell, T. Das, M. Armbrust, A. Dave, X. Meng, J. Rosen, S. Venkataraman, M. J. Franklin, A. Ghodsi, J. Gonzalez, S. Shenker, I. Stoica, Apache spark: a unified engine for big data processing, Commun. ACM 59 (2016) 56–65. URL: http://doi.acm.org/10.1145/2934664. doi:10.1145/2934664. [17] MusicBrainz - The Open Music Encyclopedia, https://musicbrainz.org/, 2022. [18] G. Gottlob, M. Lanzinger, D. M. Longo, C. Okulmus, R. Pichler, A. Selzer, Structure-guided query evaluation: Towards bridging the gap from theory to practice, CoRR abs/2303.02723 (2023). URL: https://arxiv.org/abs/2303.02723.