Deep Reinforcement Learning for Join Order Enumeration

Abstract

Join order selection plays a significant role in query performance. However, modern query optimizers typically employ static join enumeration algorithms that do not receive any feedback about the quality of the resulting plan. Hence, optimizers often repeatedly choose the same bad plan, as they do not have a mechanism for "learning from their mistakes". In this paper, we argue that existing deep reinforcement learning techniques can be applied to address this challenge. These techniques, powered by artificial neural networks, can automatically improve decision making by incorporating feedback from their successes and failures. Towards this goal, we present ReJOIN, a proof-of-concept join enumerator, and present preliminary results indicating that ReJOIN can match or outperform the PostgreSQL optimizer in terms of plan quality and join enumeration efficiency.

References in corpus (2)

• Deep Learning in Neural Networks: An Overview
• The Vertica Analytic Database: C-Store 7 Years Later

Cited by in corpus (40)

• Neo: A Learned Query Optimizer
• Bao: Learning to Steer Query Optimizers
• Deep Unsupervised Cardinality Estimation
• Learned Cardinalities: Estimating Correlated Joins with Deep Learning
• Database Meets Deep Learning: Challenges and Opportunities
• Plan-Structured Deep Neural Network Models for Query Performance Prediction
• Are We Ready For Learned Cardinality Estimation?
• A Survey on Advancing the DBMS Query Optimizer: Cardinality Estimation, Cost Model, and Plan Enumeration
• Learning to Optimize Join Queries With Deep Reinforcement Learning
• SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning
• Towards a Hands-Free Query Optimizer through Deep Learning
• Kepler: Robust Learning for Faster Parametric Query Optimization
• Automated Database Indexing using Model-free Reinforcement Learning
• RadixSpline: A Single-Pass Learned Index
• Opportunistic View Materialization with Deep Reinforcement Learning
• Deploying a Steered Query Optimizer in Production at Microsoft
• Multi-Attribute Selectivity Estimation Using Deep Learning
• Monotonic Cardinality Estimation of Similarity Selection: A Deep Learning Approach
• Approximate Query Processing using Deep Generative Models
• Improved Cardinality Estimation by Learning Queries Containment Rates
• Polyjuice: High-Performance Transactions via Learned Concurrency Control
• Hype or Heuristic? Quantum Reinforcement Learning for Join Order Optimisation
• Blueprinting the Cloud: Unifying and Automatically Optimizing Cloud Data Infrastructures with BRAD -- Extended Version
• A Unified Transferable Model for ML-Enhanced DBMS
• How I Learned to Stop Worrying and Love Re-optimization
• FOSS: A Self-Learned Doctor for Query Optimizer
• One Model to Rule them All: Towards Zero-Shot Learning for Databases
• Join Query Optimization with Deep Reinforcement Learning Algorithms
• Learned Indexes for Dynamic Workloads
• Flexible Operator Embeddings via Deep Learning
• Are Joins over LSM-Trees Ready? Take RocksDB as an Example
• Is Your Learned Query Optimizer Behaving As You Expect? A Machine Learning Perspective
• A Comparative Exploration of ML Techniques for Tuning Query Degree of Parallelism
• Which Channel to Ask My Question? Personalized Customer Service Request Stream Routing using Deep Reinforcement Learning
• Maliva: Using Machine Learning to Rewrite Visualization Queries Under Time Constraints
• Online Sketch-based Query Optimization
• NN-based Transformation of Any SQL Cardinality Estimator for Handling DISTINCT, AND, OR and NOT
• Simpli-Squared: A Very Simple Yet Unexpectedly Powerful Join Ordering Algorithm Without Cardinality Estimates
• Wield: Systematic Reinforcement Learning With Progressive Randomization
• Estimating Cardinalities with Deep Sketches