# Balsa: Learning a Query Optimizer Without Expert Demonstrations

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 39 references that are in the map.
- First posted on arXiv 5 Jan 2022.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Domain Randomization for Transferring Deep Neural Networks from Simulation to the Real World](https://mlsanity.com/paper/1703.06907/) (2017)
- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [Solving Rubik's Cube with a Robot Hand](https://mlsanity.com/paper/1910.07113/) (2019)
- [Ray: A Distributed Framework for Emerging AI Applications](https://mlsanity.com/paper/1712.05889/) (2017)
- [Generative Language Modeling for Automated Theorem Proving](https://mlsanity.com/paper/2009.03393/) (2020)
- [Thinking Fast and Slow with Deep Learning and Tree Search](https://mlsanity.com/paper/1705.08439/) (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)
- [An End-to-End Learning-based Cost Estimator](https://mlsanity.com/paper/1906.02560/) (2019)
- [Deep Unsupervised Cardinality Estimation](https://mlsanity.com/paper/1905.04278/) (2019)
- [Learning to Optimize Join Queries With Deep Reinforcement Learning](https://mlsanity.com/paper/1808.03196/) (2018)
- [NeuroCard: One Cardinality Estimator for All Tables](https://mlsanity.com/paper/2006.08109/) (2020)
- [Are We Ready For Learned Cardinality Estimation?](https://mlsanity.com/paper/2012.06743/) (2020)
- [SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning](https://mlsanity.com/paper/1901.05152/) (2019)
- [Towards Scalable Dataframe Systems](https://mlsanity.com/paper/2001.00888/) (2020)

## Built on by (most cited first, 18 of 18)

- [Barbarians at the Gate: How AI is Upending Systems Research](https://mlsanity.com/paper/2510.06189/) (2025)
- [Lero: A Learning-to-Rank Query Optimizer](https://mlsanity.com/paper/2302.06873/) (2023)
- [E2ETune: End-to-End Knob Tuning via Fine-tuned Generative Language Model](https://mlsanity.com/paper/2404.11581/) (2024)
- [NeurDB: An AI-powered Autonomous Data System](https://mlsanity.com/paper/2405.03924/) (2024)
- [CardBench: A Benchmark for Learned Cardinality Estimation in Relational Databases](https://mlsanity.com/paper/2408.16170/) (2024)
- [Kepler: Robust Learning for Faster Parametric Query Optimization](https://mlsanity.com/paper/2306.06798/) (2023)
- [Let the Barbarians In: How AI Can Accelerate Systems Performance Research](https://mlsanity.com/paper/2512.14806/) (2025)
- [JoinGym: An Efficient Query Optimization Environment for Reinforcement Learning](https://mlsanity.com/paper/2307.11704/) (2023)
- [FOSS: A Self-Learned Doctor for Query Optimizer](https://mlsanity.com/paper/2312.06357/) (2023)
- [Hype or Heuristic? Quantum Reinforcement Learning for Join Order Optimisation](https://mlsanity.com/paper/2405.07770/) (2024)
- [GenJoin: Conditional Generative Plan-to-Plan Query Optimizer that Learns from Subplan Hints](https://mlsanity.com/paper/2411.04525/) (2024)
- [Large Scale Multi-Task Bayesian Optimization with Large Language Models](https://mlsanity.com/paper/2503.08131/) (2025)
- [Low Rank Learning for Offline Query Optimization](https://mlsanity.com/paper/2504.06399/) (2025)
- [LLM4Hint: Leveraging Large Language Models for Hint Recommendation in Offline Query Optimization](https://mlsanity.com/paper/2507.03384/) (2025)
- [TiCard: Deployable EXPLAIN-only Residual Learning for Cardinality Estimation](https://mlsanity.com/paper/2512.14358/) (2025)
- [MICRO: A Lightweight Middleware for Optimizing Cross-store Cross-model Graph-Relation Joins [Technical Report]](https://mlsanity.com/paper/2603.13835/) (2026)
- [RELOAD: A Robust and Efficient Learned Query Optimizer for Database Systems](https://mlsanity.com/paper/2604.14725/) (2026)
- [Agentic Cost-Aware Query Planning with Knowledge Distillation for Big Data Analytics](https://mlsanity.com/paper/2605.17831/) (2026)

## Abstract (arXiv)

Query optimizers are a performance-critical component in every database system. Due to their complexity, optimizers take experts months to write and years to refine. In this work, we demonstrate for the first time that learning to optimize queries without learning from an expert optimizer is both possible and efficient. We present Balsa, a query optimizer built by deep reinforcement learning. Balsa first learns basic knowledge from a simple, environment-agnostic simulator, followed by safe learning in real execution. On the Join Order Benchmark, Balsa matches the performance of two expert query optimizers, both open-source and commercial, with two hours of learning, and outperforms them by up to 2.8× in workload runtime after a few more hours. Balsa thus opens the possibility of automatically learning to optimize in future compute environments where expert-designed optimizers do not exist.