This SIGMOD '22 paper from the UC Berkeley RISELab presents Balsa, a significant milestone in the field of "Machine Learning for Systems." It is the first learned query optimizer that successfully navigates the "cold start" problem—learning to generate high-performance execution plans without ever seeing a single example from a human-engineered expert optimizer.
TL;DR
Balsa is a deep reinforcement learning (RL) query optimizer that bootstraps its knowledge from a simple simulator and refines it through real-world execution. It matches or outperforms mature optimizers like PostgreSQL and a leading commercial database by up to 2.8x, proving that "expert-free" learned optimization is both possible and highly efficient.
What Problem Does This Paper Address?
Query optimization is the "brain" of a database, responsible for finding the most efficient way to execute a SQL query. Traditionally, these are built by human experts over decades (PostgreSQL’s optimizer has been refined for 20+ years).
Recent "learned" optimizers (like Neo or DQ) showed promise but suffered from a "chicken-and-egg" problem: they required an existing, high-quality expert optimizer to provide "demonstrations" or a complex cost model to learn from. This makes them useless for new database engines where no such expert exists. Furthermore, RL agents in database environments face a unique challenge: while a "bad move" in a game like Chess ends the game quickly, a "bad plan" in a database can cause a query to run for hours, effectively stalling the learning process.
Methods
Balsa uses a two-stage "Sim-to-Real" approach:
- Bootstrapping from Simulation: Instead of an expert, Balsa starts with a "minimal" simulator—a simple logical cost model ($C_{out}$) that assumes "fewer tuples processed equals a better plan." While inaccurate, this simulator is fast and teaches the agent to avoid obviously disastrous plans.
- Fine-tuning in Real Execution: Balsa then executes queries on the actual database engine. It uses a Value Network (a tree convolution neural network) to predict the latency of partial plans and Beam Search to find the best complete plan.
To make this practical, the authors introduced three key techniques:
- Safe Execution (Timeouts): To prevent "stalling" on bad plans, Balsa uses the best-known latency for a query as a timeout. If a new plan exceeds this, it’s killed and assigned a "bad" reward.
- Safe Exploration: Standard RL uses random moves to explore. In DBs, random moves are usually catastrophic. Balsa instead picks the best unseen plan from its top-k predicted plans, staying within a "trust region" of likely-good options.
- Diversified Experiences: The authors found that training multiple agents independently and merging their experiences (Balsa-8x) significantly improved the model's ability to generalize to new, unseen query templates.
Datasets
The authors evaluated Balsa using:
- Join Order Benchmark (JOB): A standard, difficult benchmark based on real-world IMDb data designed to stress-test optimizers.
- TPC-H: A classic industry-standard benchmark for decision support systems.
- Ext-JOB: A "hard mode" generalization test featuring query templates entirely different from the training set.
Key Insights and Ideas
- The Simulator doesn't need to be "Good": A surprising finding was that the initial simulator can be quite "dumb" and full of inaccurate cardinality estimates. Its only job is to provide a "safety net" so the agent doesn't start its real-world training by trying plans that take hours to finish.
- Timeouts as a Learning Curriculum: By progressively tightening timeouts as the agent finds better plans, Balsa creates an implicit "curriculum" where the task of finding a better plan becomes more refined over time.
- On-Policy Learning is Faster: Unlike previous work (Neo) that retrained from scratch every iteration, Balsa uses on-policy updates (updating only on the most recent data). This made Balsa 9.6x faster to train than Neo.
Key Results
- Outperforming Experts: On the JOB benchmark, Balsa achieved a 2.1x speedup over PostgreSQL and a 2.8x speedup over a commercial "CommDB."
- Efficiency: Balsa matched PostgreSQL's performance after just 2 hours of training and reached peak performance in about 5 hours.
- Robust Generalization: Even on queries it had never seen before (Ext-JOB), the "Balsa-8x" variant (using diversified experiences) outperformed the expert optimizers by 20%.
- Novel Strategies: Balsa learned to prefer specific plan shapes (like bushy trees) and operators (like indexed nested loops) that the human-designed optimizers often overlooked for specific workloads.
Limitations and Future Work
- Static Data Assumption: Balsa currently assumes the underlying data distribution is static. If the data changes significantly, the model needs retraining.
- SPJ Focus: The current implementation focuses on Select-Project-Join blocks. Extending this to handle complex subqueries, aggregations, and window functions is a natural next step.
- Training Overhead: While 5 hours is fast for a one-time setup, it still requires a dedicated "training workload" and execution time, which might be a hurdle for very dynamic environments.
Summary updated