Are LLM agents good at join order optimization?

Summary

Join ordering is difficult because relational optimizers choose among exponentially many plans and depend on potentially inaccurate cardinality estimates. Databricks and UPenn researchers built an LLM agent that uses structured outputs to generate valid join reorderings and executes candidates through a tool returning runtime and intermediate subplan sizes. It can test up to 50 iterations, while the evaluation tested 15 rollouts per query across 113 Join Order Benchmark queries after duplicating each dataset row ten times. With a frontier model, the best tested orders improved geometric-mean latency by 1.288 times and reduced P90 latency by 41% versus the standard Databricks optimizer. A five-way example links its gain to LIKE predicates that are exceptionally difficult for cardinality estimators.

Context

Relational query optimizers must select join orderings from an exponentially large plan space, but cardinality estimation can be especially difficult and lead to suboptimal choices. Integrating an LLM into the optimizer’s few-hundred-millisecond hot path is not currently feasible, motivating an offline approach to the manual tuning process.

Approach / What changed

A prototype LLM agent generates valid join reorderings using structured model outputs and tests them with a single execution tool. The tool returns each candidate’s runtime, subject to the original query’s timeout, and the sizes of computed subplans. The evaluation used 15 rollouts for each of 113 Join Order Benchmark queries on data expanded by duplicating every row ten times.

Takeaways

• Using a frontier model, the best tested join orders improved geometric-mean query latency by a factor of 1.288 and reduced P90 latency by 41% compared with the standard Databricks optimizer.
• Structured model outputs constrain every generated join ordering to a specified grammar, ensuring that tool calls produce valid join reorderings rather than arbitrary model output.
• The agent improved a five-way join by testing a plan that filtered VHS releases referencing 1994 first; the example attributes the gain to LIKE predicates being exceptionally difficult for cardinality estimators.

Related reading