Reaching Back to Move Forward: Using Old Ideas to Achieve a New Level of Query Optimization (short paper)

Georg Gottlob, Matthias Lanzinger, Davide Mario Longo, Cem Okulmus, Reinhard Pichler, Alexander SelzerAMW 2023 · OpenReview

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:

  1. Bottom-up traversal: Employs semi-joins (via EXISTS operators) to filter out rows that cannot be part of the final result.
  2. Top-down traversal: Performs further filtering to ensure "full reducibility."
  3. 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.

Performance comparison of standard DBMS optimizers vs. YanRe for Full Enumeration and Min-Aggregation 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

BibTeX
@inproceedings{gottlob2023reaching,
  author = {Georg Gottlob and Matthias Lanzinger and Davide Mario Longo and Cem Okulmus and Reinhard Pichler and Alexander Selzer},
  title = {{Reaching Back to Move Forward: Using Old Ideas to Achieve a New Level of Query Optimization (short paper)}},
  booktitle = {AMW},
  year = {2023},
  url = {https://openreview.net/forum?id=PzxVvZx8kh},
}
Figure