Introduction
Modern database management systems (DBMSs) are highly optimized for standard workloads but often struggle with complex join queries involving dozens of tables. Traditional optimizers rely on join-ordering heuristics to decompose large queries into sequences of binary joins. However, as the number of relations increases, finding an optimal join order becomes NP-hard. Consequently, systems often resort to heuristics that can lead to massive intermediate results, memory exhaustion, or execution timeouts.
While database theory provided a solution for "acyclic" queries decades ago via Yannakakis’ algorithm (1981), this approach has seen limited adoption in mainstream systems because it does not naturally fit the standard "Volcano" iterator model. This paper explores bridging this gap using YanRe (Yannakakis Rewriter), a middleware tool that implements these theoretical principles through SQL rewriting.
The YanRe Approach
YanRe functions as a middleware layer that identifies the core join structure of a query and transforms it into a sequence of smaller SQL statements. This process follows the three phases of Yannakakis’ algorithm:
- Bottom-up traversal: Employs semi-joins (via
EXISTSoperators) to filter out rows that cannot be part of the final result. - Top-down traversal: Performs further filtering to ensure "full reducibility."
- Final Join: Joins the reduced relations to produce the final output.
By forcing a structure-guided execution plan, YanRe avoids the "intermediate result explosion" typical of standard optimizers.
Experimental Evaluation
The authors evaluated YanRe across three diverse systems—PostgreSQL (row-oriented), DuckDB (column-oriented), and Spark SQL (distributed)—using the real-world MusicBrainz dataset and a benchmark of 435 challenging join queries. The evaluation focused on two query types: Full Enumeration (returning all results) and Min-Aggregation (finding the minimum value of a specific attribute).
Results and Discussion
The experimental results demonstrate that YanRe significantly enhances the reliability of modern DBMSs for complex queries.
As shown in the performance data above, YanRe drastically reduced the number of timeouts. In Min-Aggregation queries, DuckDB and Spark SQL saw their timeouts drop to zero. Furthermore, for the most difficult queries that did complete, the maximum execution times were substantially reduced. For example, in Spark SQL min-aggregation, the maximum execution time decreased from 1082 seconds to 156 seconds.
However, the results also highlight a trade-off: for simpler queries, the overhead of managing temporary tables can lead to higher median execution times. This indicates that YanRe is most effective as a specialized optimizer for queries that exceed the capabilities of standard heuristic-based optimizers.
Conclusion
This research proves that 40-year-old database theory offers concrete solutions to modern scaling issues. By leveraging semi-joins to eliminate irrelevant data early, YanRe provides architecture-agnostic performance gains. Future work will focus on extending these techniques to "almost acyclic" queries and integrating them directly into database kernels to further reduce overhead.
Summary updated