Abstract
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$\times$ 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.
Introduction
Query optimization is the "brain" of a database, responsible for finding the most efficient way to execute a SQL query. Traditionally, these systems are built by human experts over decades; for instance, PostgreSQL’s optimizer has been refined for over 20 years.
Recent "learned" optimizers showed promise but faced 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 dependency makes them unsuitable for new database engines where no such expert exists. Furthermore, reinforcement learning (RL) in databases faces 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.
System Architecture
Balsa is a deep RL query optimizer that bootstraps its knowledge from a simple simulator and refines it through real-world execution. It successfully navigates the "cold start" problem without ever seeing an example from a human-engineered expert optimizer.
The system uses a two-stage "Sim-to-Real" approach:
- Bootstrapping from Simulation: Balsa starts with a "minimal" simulator—a simple logical cost model ($C_{out}$) that assumes fewer processed tuples lead to better plans. While inaccurate, this fast simulator teaches the agent to avoid obviously disastrous plans.
- Fine-tuning in Real Execution: Balsa then executes queries on the actual database engine. It employs a Value Network (a tree convolution neural network) to predict the latency of partial plans and uses Beam Search to find the best complete plan.
Safe Learning and Exploration
To make RL practical in a database context, Balsa introduces several key techniques to handle the risks of executing unknown plans:
- 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 is terminated and assigned a "bad" reward.
- Safe Exploration: Standard RL uses random moves to explore, which is often catastrophic in databases. Balsa instead picks the best unseen plan from its top-k predicted plans, staying within a "trust region" of likely-good options.
- Diversified Experiences: By training multiple agents independently and merging their experiences (the Balsa-8x variant), the model's ability to generalize to new, unseen query templates is significantly improved.
Evaluation and Key Results
The authors evaluated Balsa using the Join Order Benchmark (JOB), TPC-H, and Ext-JOB (a generalization test with different query templates).
- Outperforming Experts: On the JOB benchmark, Balsa achieved a 2.1x speedup over PostgreSQL and a 2.8x speedup over a leading commercial database.
- Efficiency: Balsa matched PostgreSQL's performance after just 2 hours of training and reached peak performance in about 5 hours. It uses on-policy updates, making it 9.6x faster to train than previous learned optimizers like Neo.
- Generalization: On unseen queries (Ext-JOB), the "Balsa-8x" variant outperformed expert optimizers by 20%.
- Novel Strategies: Balsa learned to prefer specific plan shapes (like bushy trees) and operators (like indexed nested loops) that human-designed optimizers often overlooked for specific workloads.
Conclusion
Balsa demonstrates that "expert-free" learned optimization is not only possible but highly efficient. By using a minimal simulator for bootstrapping and safe exploration techniques for real-world fine-tuning, Balsa can outperform mature, human-engineered optimizers in just a few hours of training. This opens the door for automated optimization in novel compute environments where expert-designed systems do not yet exist.
Summary updated