AI-Powered Query Optimizer

Learn from past runs to steer the database's query plans

Design a service that learns from how past queries actually ran and steers the database's optimizer toward faster plans, without ever making a query much slower than the optimizer would on its own.

Overview

A database's query optimizer turns SQL into a plan: the join order, the join method (nested loop, hash or merge join) and how each table is read. It picks the plan it estimates is cheapest, and that estimate rests on cardinality estimates: how many rows each step will produce. When those counts are wrong, the plan can be badly wrong.

They often are. In the study that introduced the Join Order Benchmark, Leis and colleagues found that every system they tested routinely misestimated join results by a factor of 1,000 or more, that errors grow with each join, and that the cost model mattered much less than the row counts. PostgreSQL's own documentation names one cause: the planner assumes conditions on different columns are independent, which is false when columns are correlated.

A learned optimizer uses the history of queries that already ran, with their real run times, to do better. One research line (Neo in 2019, then Bao at SIGMOD 2021) shows the practical version: do not replace the optimizer; give it hints per query, and learn which hints help. This design builds that, with the safety rails a production database needs.

Questions to ask first

Which database? — PostgreSQL, used as an analytical warehouse
What workload? — About 100,000 analytical queries a day, many repeating from dashboards and jobs; 20 a second at peak
How slow are the queries? — Seconds to minutes, so a few milliseconds of planning is affordable
Can we change the database? — No: we can set planner options per query, nothing more
What is unacceptable? — Any query becoming much slower than it runs today
How often does data change? — Daily loads; the right plan can change after a load

What you will be able to do

Explain why optimizers pick bad plans, and fix the easy cases with plain statistics first.
Compare learned cardinality estimation, a learned optimizer, and learned steering with hints.
Design the per-query path: fingerprint, plan several ways, score, pick, record.
Balance trying new plans against using known good ones, with Thompson sampling.
Roll out models safely: shadow mode, canary, guardrails and instant rollback.

Key concepts

Cardinality estimation
Cost model
Query plan tree
Optimizer hints
Hint sets as bandit arms
Thompson sampling
Experience store
Regression guardrail
Shadow and canary rollout
Extended statistics

Functional requirements

For each query, produce plans under a small set of hint sets, including no hints
Score each plan with a model and run the one predicted fastest
Record each execution's plan, hint set and actual run time
Retrain the model on recent executions and roll new versions out gradually
Stop using a hint set for a query template after it causes a regression
Turn steering off per template, per database, or everywhere, instantly

Non-functional requirements

Steering adds under 50 ms per query at p99 (a target we chose), small next to queries of seconds
No query template runs more than 2 times slower than its default plan for long (a target we chose)
If the steering service is down, queries run with the default plan
Results are always correct: hints change how a query runs, never what it returns
A bad model can be rolled back in under a minute

Interview questions

Why do traditional optimizers pick bad plans?
Would you replace the optimizer with a neural network?
How does the system decide when to try a new plan?
How do you make sure the model never causes an outage?
How do you encode a query plan for a model?
How does the system adapt when the data changes?
What would you measure to prove it works?