Balsa: Learning a Query Optimizer Without Expert Demonstrations

Summary: Balsa uses deep RL to learn a query optimizer without expert demonstrations, from a simple simulator to safe real-execution fine-tuning. On Join Order Benchmark, it matches two expert optimizers after ~2 hours and beats them up to 2.8x with training. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hc15b634968a29395
Venue: SIGMOD
Year: 2022
Pagerank: 0.00011630532
Overall Rank: 1,175 | 92.13%
DOI: 10.1145/3514221.3517885

Incoming Non-self Citations Over Time

Authors

1. Zongheng Yang (University of California Berkeley)
2. Wei-Lin Chiang (University of California Berkeley)
3. Sifei Luan (University of California Berkeley)
4. Gautam Mittal (University of California Berkeley)
5. Michael Luo (University of California Berkeley)
6. Ion Stoica (University of California Berkeley)

BibTeX Citation

@inproceedings{yang_sigmod22,
        title = {{Balsa: Learning a Query Optimizer Without Expert Demonstrations}},
        author = {Yang, Zongheng and Chiang, Wei-Lin and Luan, Sifei and Mittal, Gautam and Luo, Michael and Stoica, Ion},
        series = {{SIGMOD} '22},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3514221.3517885},
        url = {https://dl.acm.org/doi/10.1145/3514221.3517885},
        year = {2022}
}

Incoming Citations (Sorted by Pagerank)

Showing 10 of 60 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,771	Sample-based Distinct Cardinality Estimation for Multiple Attributes in Multi-Dataset Queries	2026	VLDB	4.9605343e-05
10,812	OBELISK: Efficient Offline Query Planning with Bayesian Optimization-Informed Language Model Reasoning	2026	VLDB	4.9605343e-05
10,822	Toward Drift-Aware Database Benchmarking	2026	VLDB	4.9605343e-05
10,953	QDBO: A Real-time Quantum-augmented Database System Optimizer	2026	VLDB	4.9605343e-05
10,994	TATA: An Efficient Framework for Task Transfer in Query Plan Representation	2026	VLDB	4.9605343e-05
11,008	Towards Industrial-Scale Parametric Query Optimization	2026	VLDB	4.9605343e-05
11,347	Robust Plan Evaluation based on Approximate Probabilistic Machine Learning	2025	VLDB	4.9605343e-05
11,484	Learned Cost Models for Query Optimization: From Batch to Streaming Systems	2025	VLDB	4.9605343e-05
11,501	LEAP: A Low-cost Spark SQL Query Optimizer using Pairwise Comparison	2025	VLDB	4.9605343e-05
11,511	RankPQO: Learning-to-Rank for Parametric Query Optimization	2025	VLDB	4.9605343e-05

Outgoing Citations (Sorted by Pagerank)

Showing 16 of 16 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
1	Access Path Selection in a Relational Database Management System	1979	SIGMOD	0.0023948467
15	How Good Are Query Optimizers, Really?	2016	VLDB	0.00061463175
84	Learned Cardinalities: Estimating Correlated Joins with Deep Learning	2019	CIDR	0.00035920657
142	Neo: A Learned Query Optimizer	2019	VLDB	0.00029114937
320	DeepDB: Learn from Data, not from Queries!	2020	VLDB	0.00021128745
355	Bao: Making Learned Query Optimization Practical	2021	SIGMOD	0.00020146245
405	Deep Unsupervised Cardinality Estimation	2020	VLDB	0.00019020138
453	An End-to-End Learning-based Cost Estimator	2020	VLDB	0.0001801482
508	NeuroCard: One Cardinality Estimator for All Tables	2021	VLDB	0.00017108973
690	Selectivity Estimation for Range Predicates using Lightweight Models	2019	VLDB	0.00014703258
1,064	Are We Ready For Learned Cardinality Estimation?	2021	VLDB	0.00012181459
1,374	Towards Scalable Dataframe Systems	2020	VLDB	0.00010862447
1,436	Towards a Learning Optimizer for Shared Clouds	2019	VLDB	0.00010658836
1,609	SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning	2019	SIGMOD	0.0001007196
2,481	Learning a Partitioning Advisor for Cloud Databases	2020	SIGMOD	8.3862675e-05
3,555	Astrid: Accurate Selectivity Estimation for String Predicates using Deep Learning	2021	VLDB	7.1877332e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,109	Is Your Learned Query Optimizer Behaving As You Expect? A Machine Learning Perspective	2024	VLDB
2	5,126	Steering Query Optimizers: A Practical Take on Big Data Workloads	2021	SIGMOD
3	4,508	LearnedSQLGen: Constraint-aware SQL Generation using Reinforcement Learning	2022	SIGMOD
4	3,481	LOGER: A Learned Optimizer towards Generating Efficient and Robust Query Execution Plans	2023	VLDB
5	8,989	Conformal Prediction for Verifiable Learned Query Optimization	2025	VLDB
6	4,683	AutoSteer: Learned Query Optimization for Any SQL Database	2023	VLDB
7	1,803	SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning	2018	VLDB
8	9,236	BASE: Bridging the Gap between Cost and Latency for Query Optimization	2023	VLDB
9	355	Bao: Making Learned Query Optimization Practical	2021	SIGMOD
10	3,062	Towards a Hands-Free Query Optimizer through Deep Learning	2019	CIDR