Bao: Learning to Steer Query Optimizers

Abstract

Query optimization remains one of the most challenging problems in data management systems. Recent efforts to apply machine learning techniques to query optimization challenges have been promising, but have shown few practical gains due to substantive training overhead, inability to adapt to changes, and poor tail performance. Motivated by these difficulties and drawing upon a long history of research in multi-armed bandits, we introduce Bao (the BAndit Optimizer). Bao takes advantage of the wisdom built into existing query optimizers by providing per-query optimization hints. Bao combines modern tree convolutional neural networks with Thompson sampling, a decades-old and well-studied reinforcement learning algorithm. As a result, Bao automatically learns from its mistakes and adapts to changes in query workloads, data, and schema. Experimentally, we demonstrate that Bao can quickly (an order of magnitude faster than previous approaches) learn strategies that improve end-to-end query execution performance, including tail latency. In cloud environments, we show that Bao can offer both reduced costs and better performance compared with a sophisticated commercial system.

References in corpus (6)

• A Brief Survey of Deep Reinforcement Learning
• Further Optimal Regret Bounds for Thompson Sampling
• Innateness, AlphaZero, and Artificial Intelligence
• Bootstrapped Thompson Sampling and Deep Exploration
• An Information-Theoretic Analysis of Thompson Sampling
• Learned Garbage Collection

Cited by in corpus (15)

• Balsa: Learning a Query Optimizer Without Expert Demonstrations
• Are Updatable Learned Indexes Ready?
• Kepler: Robust Learning for Faster Parametric Query Optimization
• AdaChain: A Learned Adaptive Blockchain
• Deploying a Steered Query Optimizer in Production at Microsoft
• NeurDB: An AI-powered Autonomous Data System
• Hype or Heuristic? Quantum Reinforcement Learning for Join Order Optimisation
• FOSS: A Self-Learned Doctor for Query Optimizer
• AIBench Scenario: Scenario-distilling AI Benchmarking
• Low Rank Learning for Offline Query Optimization
• GEqO: ML-Accelerated Semantic Equivalence Detection
• A Novel Technique for Query Plan Representation Based on Graph Neural Nets
• Are Joins over LSM-Trees Ready? Take RocksDB as an Example
• Is Your Learned Query Optimizer Behaving As You Expect? A Machine Learning Perspective
• Experience-Enhanced Learning: One Size Still does not Fit All in Automatic Database