# Selective Use of Yannakakis' Algorithm to Improve Query Performance: Machine Learning to the Rescue

arXiv: https://arxiv.org/abs/2502.20233 · HTML: https://mlsanity.com/paper/2502.20233/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 28 of its 94 references that are in the map.
- First posted on arXiv 27 Feb 2025.

## Builds on (most cited first, 28 of 28)

- [Hypergraph Neural Networks](https://mlsanity.com/paper/1809.09401/) (2018)
- [The Case for Learned Index Structures](https://mlsanity.com/paper/1712.01208/) (2017)
- [Neo: A Learned Query Optimizer](https://mlsanity.com/paper/1904.03711/) (2019)
- [Learned Cardinalities: Estimating Correlated Joins with Deep Learning](https://mlsanity.com/paper/1809.00677/) (2018)
- [Bao: Learning to Steer Query Optimizers](https://mlsanity.com/paper/2004.03814/) (2020)
- [SNAP: A General Purpose Network Analysis and Graph Mining Library](https://mlsanity.com/paper/1606.07550/) (2016)
- [ALEX: An Updatable Adaptive Learned Index](https://mlsanity.com/paper/1905.08898/) (2019)
- [Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation](https://mlsanity.com/paper/2109.05877/) (2021)
- [BestConfig: Tapping the Performance Potential of Systems via Automatic Configuration Tuning](https://mlsanity.com/paper/1710.03439/) (2017)
- [Plan-Structured Deep Neural Network Models for Query Performance Prediction](https://mlsanity.com/paper/1902.00132/) (2019)
- [SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning](https://mlsanity.com/paper/1901.05152/) (2019)
- [QuickSel: Quick Selectivity Learning with Mixture Models](https://mlsanity.com/paper/1812.10568/) (2018)
- [An Empirical Analysis of Deep Learning for Cardinality Estimation](https://mlsanity.com/paper/1905.06425/) (2019)
- [Constraint Solving via Fractional Edge Covers](https://mlsanity.com/paper/1711.04506/) (2017)
- [Learning Space Partitions for Nearest Neighbor Search](https://mlsanity.com/paper/1901.08544/) (2019)
- [Designing Succinct Secondary Indexing Mechanism by Exploiting Column Correlations (Extended Version)](https://mlsanity.com/paper/1903.11203/) (2019)
- [Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs](https://mlsanity.com/paper/2105.08878/) (2021)
- [Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores](https://mlsanity.com/paper/2411.04042/) (2024)
- [Debunking the Myth of Join Ordering: Toward Robust SQL Analytics](https://mlsanity.com/paper/2502.15181/) (2025)
- [Fuzzy neural networks to create an expert system for detecting attacks by SQL Injection](https://mlsanity.com/paper/1901.02868/) (2019)
- [Diversifying Database Activity Monitoring with Bandits](https://mlsanity.com/paper/1910.10777/) (2019)
- [Collaborative SQL-injections detection system with machine learning](https://mlsanity.com/paper/2209.06553/) (2022)
- [Change Propagation Without Joins](https://mlsanity.com/paper/2301.04003/) (2023)
- [Computing the Difference of Conjunctive Queries Efficiently](https://mlsanity.com/paper/2302.13140/) (2023)
- [Structure-Guided Query Evaluation: Towards Bridging the Gap from Theory to Practice](https://mlsanity.com/paper/2303.02723/) (2023)
- [Predicate Transfer: Efficient Pre-Filtering on Multi-Join Queries](https://mlsanity.com/paper/2307.15255/) (2023)
- [Avoiding Materialisation for Guarded Aggregate Queries](https://mlsanity.com/paper/2406.17076/) (2024)
- [Soft and Constrained Hypertree Width](https://mlsanity.com/paper/2412.11669/) (2024)

## Abstract (arXiv)

Query optimization has played a central role in database research for decades. However, more often than not, the proposed optimization techniques lead to a performance improvement in some, but not in all, situations. Therefore, we urgently need a methodology for designing a decision procedure that decides for a given query whether the optimization technique should be applied or not. In this work, we propose such a methodology with a focus on Yannakakis-style query evaluation as our optimization technique of interest. More specifically, we formulate this decision problem as an algorithm selection problem and we present a Machine Learning based approach for its solution. Empirical results with several benchmarks on a variety of database systems show that our approach indeed leads to a statistically significant performance improvement.