# Learning to Optimize Join Queries With Deep Reinforcement Learning

arXiv: https://arxiv.org/abs/1808.03196 · HTML: https://mlsanity.com/paper/1808.03196/

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Aug 2018.

## Built on by (most cited first, 30 of 32)

- [A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Cost](https://mlsanity.com/paper/2101.00494/) (2021)
- [Sample-Efficient Reinforcement Learning with loglog(T) Switching Cost](https://mlsanity.com/paper/2202.06385/) (2022)
- [Lero: A Learning-to-Rank Query Optimizer](https://mlsanity.com/paper/2302.06873/) (2023)
- [DB-BERT: a Database Tuning Tool that "Reads the Manual"](https://mlsanity.com/paper/2112.10925/) (2021)
- [Balsa: Learning a Query Optimizer Without Expert Demonstrations](https://mlsanity.com/paper/2201.01441/) (2022)
- [Zero-Shot Cost Models for Out-of-the-box Learned Cost Prediction](https://mlsanity.com/paper/2201.00561/) (2022)
- [A Survey on Advancing the DBMS Query Optimizer: Cardinality Estimation, Cost Model, and Plan Enumeration](https://mlsanity.com/paper/2101.01507/) (2021)
- [Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning](https://mlsanity.com/paper/2210.08238/) (2022)
- [A Survey on Deep Reinforcement Learning for Data Processing and Analytics](https://mlsanity.com/paper/2108.04526/) (2021)
- [One Model to Rule them All: Towards Zero-Shot Learning for Databases](https://mlsanity.com/paper/2105.00642/) (2021)
- [CARMI: A Cache-Aware Learned Index with a Cost-based Construction Algorithm](https://mlsanity.com/paper/2103.00858/) (2021)
- [The Central Role of the Loss Function in Reinforcement Learning](https://mlsanity.com/paper/2409.12799/) (2024)
- [Gap-Dependent Bounds for Q-Learning using Reference-Advantage Decomposition](https://mlsanity.com/paper/2410.07574/) (2024)
- [Learning to Improve Code Efficiency](https://mlsanity.com/paper/2208.05297/) (2022)
- [Near-Optimal Adversarial Reinforcement Learning with Switching Costs](https://mlsanity.com/paper/2302.04374/) (2023)
- [A Unified and Efficient Coordinating Framework for Autonomous DBMS Tuning](https://mlsanity.com/paper/2303.05710/) (2023)
- [Gap-Dependent Bounds for Federated Q-learning](https://mlsanity.com/paper/2502.02859/) (2025)
- [Kepler: Robust Learning for Faster Parametric Query Optimization](https://mlsanity.com/paper/2306.06798/) (2023)
- [InTune: Reinforcement Learning-based Data Pipeline Optimization for Deep Recommendation Models](https://mlsanity.com/paper/2308.08500/) (2023)
- [Demystifying Reinforcement Learning in Time-Varying Systems](https://mlsanity.com/paper/2201.05560/) (2022)
- [Deploying a Steered Query Optimizer in Production at Microsoft](https://mlsanity.com/paper/2210.13625/) (2022)
- [Learned-Database Systems Security](https://mlsanity.com/paper/2212.10318/) (2022)
- [A Pluggable Learned Index Method via Sampling and Gap Insertion](https://mlsanity.com/paper/2101.00808/) (2021)
- [JoinGym: An Efficient Query Optimization Environment for Reinforcement Learning](https://mlsanity.com/paper/2307.11704/) (2023)
- [FOSS: A Self-Learned Doctor for Query Optimizer](https://mlsanity.com/paper/2312.06357/) (2023)
- [Hype or Heuristic? Quantum Reinforcement Learning for Join Order Optimisation](https://mlsanity.com/paper/2405.07770/) (2024)
- [GenJoin: Conditional Generative Plan-to-Plan Query Optimizer that Learns from Subplan Hints](https://mlsanity.com/paper/2411.04525/) (2024)
- [Multi-agent Databases via Independent Learning](https://mlsanity.com/paper/2205.14323/) (2022)
- [CrystalBox: Future-Based Explanations for Input-Driven Deep RL Systems](https://mlsanity.com/paper/2302.13483/) (2023)
- [Breaking the log(1/Delta2) Barrier: Better Batched Best Arm Identification with Adaptive Grids](https://mlsanity.com/paper/2501.17370/) (2025)

## Abstract (arXiv)

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).