Balsa: Learning a Query Optimizer Without Expert Demonstrations

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.

arXiv commentSIGMOD 2022; code released at: https://github.com/balsa-project/balsa/

References in corpus (9)

• Solving Rubik's Cube with a Robot Hand
• Neo: A Learned Query Optimizer
• Bao: Learning to Steer Query Optimizers
• Deep Unsupervised Cardinality Estimation
• Thinking Fast and Slow with Deep Learning and Tree Search
• Learned Cardinalities: Estimating Correlated Joins with Deep Learning
• SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning
• NeuroCard: One Cardinality Estimator for All Tables
• DeepDB: Learn from Data, not from Queries!

Cited by in corpus (6)

• NeurDB: An AI-powered Autonomous Data System
• How Good are Learned Cost Models, Really? Insights from Query Optimization Tasks
• Hype or Heuristic? Quantum Reinforcement Learning for Join Order Optimisation
• FOSS: A Self-Learned Doctor for Query Optimizer
• Low Rank Learning for Offline Query Optimization
• Is Your Learned Query Optimizer Behaving As You Expect? A Machine Learning Perspective