Learning to Optimize Join Queries With Deep Reinforcement Learning

Abstract

Exhaustive enumeration of all possible join orders is often avoided, and most optimizers leverage heuristics to prune the search space. The design and implementation of heuristics are well-understood when the cost model is roughly linear, and we find that these heuristics can be significantly suboptimal when there are non-linearities in cost. Ideally, instead of a fixed heuristic, we would want a strategy to guide the search space in a more data-driven way---tailoring the search to a specific dataset and query workload. Recognizing the link between classical Dynamic Programming enumeration methods and recent results in Reinforcement Learning (RL), we propose a new method for learning optimized join search strategies. We present our RL-based DQ optimizer, which currently optimizes select-project-join blocks. We implement three versions of DQ to illustrate the ease of integration into existing DBMSes: (1) A version built on top of Apache Calcite, (2) a version integrated into PostgreSQL, and (3) a version integrated into SparkSQL. Our extensive evaluation shows that DQ achieves plans with optimization costs and query execution times competitive with the native query optimizer in each system, but can execute significantly faster after learning (often by orders of magnitude).

References in corpus (7)

• Playing Atari with Deep Reinforcement Learning
• How transferable are features in deep neural networks?
• Deep Reinforcement Learning for Join Order Enumeration
• Learned Cardinalities: Estimating Correlated Joins with Deep Learning
• DART: Noise Injection for Robust Imitation Learning
• Towards a Hands-Free Query Optimizer through Deep Learning
• A Model for Learned Bloom Filters and Related Structures

Cited by in corpus (37)

• Neo: A Learned Query Optimizer
• Deep Unsupervised Cardinality Estimation
• Learned Cardinalities: Estimating Correlated Joins with Deep Learning
• SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning
• Provably Efficient Q-Learning with Low Switching Cost
• NeuroCard: One Cardinality Estimator for All Tables
• An Empirical Analysis of Deep Learning for Cardinality Estimation
• Opportunistic View Materialization with Deep Reinforcement Learning
• Multi-Attribute Selectivity Estimation Using Deep Learning
• A View on Deep Reinforcement Learning in System Optimization
• Learning to Generalize Across Long-Horizon Tasks from Human Demonstrations
• FLAT: Fast, Lightweight and Accurate Method for Cardinality Estimation
• Approximate Query Processing using Deep Generative Models
• DeepLens: Towards a Visual Data Management System
• Improved Cardinality Estimation by Learning Queries Containment Rates
• Flow-Loss: Learning Cardinality Estimates That Matter
• Polyjuice: High-Performance Transactions via Learned Concurrency Control
• A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Cost
• How I Learned to Stop Worrying and Love Re-optimization
• LMKG: Learned Models for Cardinality Estimation in Knowledge Graphs
• Progressive Neural Index Search for Database System
• Learned Indexes for Dynamic Workloads
• Join Query Optimization with Deep Reinforcement Learning Algorithms
• A Pluggable Learned Index Method via Sampling and Gap Insertion
• Learning a Partitioning Advisor with Deep Reinforcement Learning
• One Model to Rule them All: Towards Zero-Shot Learning for Databases
• Flexible Operator Embeddings via Deep Learning
• CARMI: A Cache-Aware Learned Index with a Cost-based Construction Algorithm
• Survive the Schema Changes: Integration of Unmanaged Data Using Deep Learning
• Frequency Estimation in Data Streams: Learning the Optimal Hashing Scheme
• Uncertainty-aware Cardinality Estimation by Neural Network Gaussian Process
• Online Sketch-based Query Optimization
• NN-based Transformation of Any SQL Cardinality Estimator for Handling DISTINCT, AND, OR and NOT
• A Comparative Exploration of ML Techniques for Tuning Query Degree of Parallelism
• Resonance: Replacing Software Constants with Context-Aware Models in Real-time Communication
• Estimating Cardinalities with Deep Sketches
• Simpli-Squared: A Very Simple Yet Unexpectedly Powerful Join Ordering Algorithm Without Cardinality Estimates