Selective Use of Yannakakis' Algorithm to Improve Query Performance: Machine Learning to the Rescue
This work addresses a critical need in database research for a decision procedure to selectively apply optimization techniques, though it is incremental as it focuses on a specific algorithm.
The paper tackles the problem of when to apply Yannakakis' algorithm for query optimization by formulating it as an algorithm selection problem and using a machine learning approach, resulting in statistically significant performance improvements across various database systems and benchmarks.
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.