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: 6399
Venue: SIGMOD
Year: 2022
Pagerank: 0.00011521639
Overall Rank: 1,241 | 91.49%
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 50 of 57 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,420	Lero: A Learning-to-Rank Query Optimizer	2023	VLDB	8.605257e-05
3,516	LOGER: A Learned Optimizer towards Generating Efficient and Robust Query Execution Plans	2023	VLDB	7.3524442e-05
3,809	Auto-WLM: Machine Learning Enhanced Workload Management in Amazon Redshift	2023	SIGMOD	7.1074195e-05
4,434	LEON: A New Framework for ML-Aided Query Optimization	2023	VLDB	6.7079088e-05
4,470	Kepler: Robust Learning for Faster Parametric Query Optimization	2023	SIGMOD	6.6817353e-05
4,929	AutoSteer: Learned Query Optimization for Any SQL Database	2023	VLDB	6.4423294e-05
5,107	Stage: Query Execution Time Prediction in Amazon Redshift	2024	SIGMOD	6.3623786e-05
5,277	FASTgres: Making Learned Query Optimizer Hinting Effective	2023	VLDB	6.2859099e-05
5,573	Eraser: Eliminating Performance Regression on Learned Query Optimizer	2024	VLDB	6.1682747e-05
5,701	Lemo: A Cache-Enhanced Learned Optimizer for Concurrent Queries	2023	SIGMOD	6.1167049e-05
5,712	Sample-Efficient Cardinality Estimation Using Geometric Deep Learning	2024	VLDB	6.1123894e-05
6,088	How Good are Learned Cost Models, Really? Insights from Query Optimization Tasks	2025	SIGMOD	5.9813965e-05
6,271	Is Your Learned Query Optimizer Behaving As You Expect? A Machine Learning Perspective	2024	VLDB	5.9326197e-05
6,462	PilotScope: Steering Databases with Machine Learning Drivers	2024	VLDB	5.8717744e-05
6,543	Speeding Up End-to-end Query Execution via Learning-based Progressive Cardinality Estimation	2023	SIGMOD	5.8461929e-05
6,593	Simple Adaptive Query Processing vs. Learned Query Optimizers: Observations and Analysis	2023	VLDB	5.8297039e-05
6,735	Join Order Selection with Deep Reinforcement Learning: Fundamentals, Techniques, and Challenges	2023	VLDB	5.7878855e-05
6,921	Rethinking Learned Cost Models: Why Start from Scratch?	2023	SIGMOD	5.7388557e-05
6,997	E2ETune: End-to-End Knob Tuning via Fine-tuned Generative Language Model	2025	VLDB	5.7300324e-05
7,809	Can Large Language Models Be Query Optimizer for Relational Databases?	2026	SIGMOD	5.5399022e-05
7,846	The Holon Approach for Simultaneously Tuning Multiple Components in a Self-Driving Database Management System with Machine Learning via Synthesized Proto-Actions	2024	VLDB	5.5331459e-05
8,163	Learned Offline Query Planning via Bayesian Optimization	2025	SIGMOD	5.4751517e-05
8,164	SlabCity: Whole-Query Optimization using Program Synthesis	2023	VLDB	5.4750309e-05
8,572	T3: Accurate and Fast Performance Prediction for Relational Database Systems With Compiled Decision Trees	2025	SIGMOD	5.4102362e-05
8,984	Hit the Gym: Accelerating Query Execution to Efficiently Bootstrap Behavior Models for Self-Driving Database Management Systems	2024	VLDB	5.3395569e-05
9,123	BASE: Bridging the Gap between Cost and Latency for Query Optimization	2023	VLDB	5.3193264e-05
9,428	LIMAO: A Framework for Lifelong Modular Learned Query Optimization	2025	VLDB	5.2709145e-05
9,475	BladeDISC: Optimizing Dynamic Shape Machine Learning Workloads via Compiler Approach	2023	SIGMOD	5.2634238e-05
9,601	Low Rank Learning for Offline Query Optimization	2025	SIGMOD	5.2487799e-05
9,617	NeuSO: Neural Optimizer for Subgraph Queries	2026	SIGMOD	5.2434488e-05
9,724	Approximate Sketches	2024	SIGMOD	5.2308295e-05
9,971	Athena: An Effective Learning-based Framework for Query Optimizer Performance Improvement	2025	SIGMOD	5.1845938e-05
10,108	An Elephant Under The Microscope: Analyzing The Interaction Of Optimizer Components In PostgreSQL	2025	SIGMOD	5.1347137e-05
10,196	Are Learned DBMS Components Robust to Workload Drift?: [Experiments & Analysis]	2026	SIGMOD	5.093636e-05
10,272	NeurBench: A Benchmark Suite for Learned Database Components with Drift Modeling: [Experiments & Analysis]	2026	SIGMOD	5.093636e-05
10,277	On Self-Designing Learned Indexes	2026	SIGMOD	5.093636e-05
10,296	Succinct Structure Representations for Efficient Query Optimization	2026	SIGMOD	5.093636e-05
10,316	GenJoin: Conditional Generative Plan-to-Plan Query Optimizer that Learns from Subplan Hints	2026	SIGMOD	5.093636e-05
10,327	Rainbow: Risk-aware Index Benefit Estimation Facing Out Of Distribution Workloads	2026	SIGMOD	5.093636e-05
10,343	APQO: An Adaptive Framework for Parametric Query Optimization	2026	SIGMOD	5.093636e-05
10,401	SEFRQO: A Self-Evolving Fine-Tuned RAG-Based Query Optimizer	2026	SIGMOD	5.093636e-05
10,445	Divo: Learning a Stable and Effective Query Optimizer with a Diverse Workload	2026	SIGMOD	5.093636e-05
10,508	Practical Parameterized Query Optimization via Efficient Plan Reuse and List-wise Ranking	2026	SIGMOD	5.093636e-05
10,513	LIO: A lightweight and interpretable query optimizer based on an evolutionary forest	2026	VLDB	5.093636e-05
10,515	Sample-based Distinct Cardinality Estimation for Multiple Attributes in Multi-Dataset Queries	2026	VLDB	5.093636e-05
10,559	OBELISK: Efficient Offline Query Planning with Bayesian Optimization-Informed Language Model Reasoning	2026	VLDB	5.093636e-05
10,569	Toward Drift-Aware Database Benchmarking	2026	VLDB	5.093636e-05
10,586	TATA: An Efficient Framework for Task Transfer in Query Plan Representation	2026	VLDB	5.093636e-05
10,881	Robust Plan Evaluation based on Approximate Probabilistic Machine Learning	2025	VLDB	5.093636e-05
10,884	Conformal Prediction for Verifiable Learned Query Optimization	2025	VLDB	5.093636e-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.0024089429
18	How Good Are Query Optimizers, Really?	2016	VLDB	0.00059284255
84	Learned Cardinalities: Estimating Correlated Joins with Deep Learning	2019	CIDR	0.00035838391
154	Neo: A Learned Query Optimizer	2019	VLDB	0.00028726181
323	DeepDB: Learn from Data, not from Queries!	2020	VLDB	0.00021264788
378	Bao: Making Learned Query Optimization Practical	2021	SIGMOD	0.00019638121
401	Deep Unsupervised Cardinality Estimation	2020	VLDB	0.00019092557
465	An End-to-End Learning-based Cost Estimator	2020	VLDB	0.0001803934
513	NeuroCard: One Cardinality Estimator for All Tables	2021	VLDB	0.00017190574
697	Selectivity Estimation for Range Predicates using Lightweight Models	2019	VLDB	0.00014888851
1,061	Are We Ready For Learned Cardinality Estimation?	2021	VLDB	0.00012369764
1,431	Towards Scalable Dataframe Systems	2020	VLDB	0.00010807221
1,468	Towards a Learning Optimizer for Shared Clouds	2019	VLDB	0.00010686496
1,712	SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning	2019	SIGMOD	9.9492299e-05
2,499	Learning a Partitioning Advisor for Cloud Databases	2020	SIGMOD	8.4993549e-05
3,545	Astrid: Accurate Selectivity Estimation for String Predicates using Deep Learning	2021	VLDB	7.3249967e-05

Semantically Similar Papers

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