Query optimization is one of the hardest problems in database research whose goal is to find the best query plan given a SQL query to minimize its runtime. This NP-hard combinatorial optimization problem has been tackled with various approaches over the last decade, and it has been shown that machine learning approaches often struggle to beat traditional approaches using sophisticated cost models.

This paper introduces GenJoin – a ML-based query optimizer that significantly outperforms classical optimizers. Rather than writing a machine learning-based query optimizer from scratch, GenJoin explores how a generative model can be used as a learned query optimizer (LQO) and provides hints to a classical optimizer for finding the fastest running query. GenJoin generates a set of restrictions on the subplan join types, shrinking the search space and forcing the classical optimizer to consider plans that might have been otherwise overlooked. This lightweight approach not only allows GenJoin to steer the optimizer towards high-quality query plans, but also does it with very little time spent for inference. 

 

A preprint of the paper can be found on arxiv (https://arxiv.org/abs/2411.04525).