JoinGym: An Efficient Query Optimization Environment for Reinforcement Learning
Not on the map. Why?
Abstract (arXiv)
Join order selection (JOS) is the problem of ordering join operations to minimize total query execution cost and it is the core NP-hard combinatorial optimization problem of query optimization. In this paper, we present JoinGym, a lightweight and easy-to-use query optimization environment for reinforcement learning (RL) that captures both the left-deep and bushy variants of the JOS problem. Compared to existing query optimization environments, the key advantages of JoinGym are usability and significantly higher throughput which we accomplish by simulating query executions entirely offline. Under the hood, JoinGym simulates a query plan's cost by looking up intermediate result cardinalities from a pre-computed dataset. We release a novel cardinality dataset for 3300 SQL queries based on real IMDb workloads which may be of independent interest, e.g., for cardinality estimation. Finally, we extensively benchmark four RL algorithms and find that their cost distributions are heavy-tailed, which motivates future work in risk-sensitive RL. In sum, JoinGym enables users to rapidly prototype RL algorithms on realistic database problems without needing to setup and run live systems.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 38 of its 65 references that are in the map. First posted on arXiv 21 Jul 2023.
Builds on
38 of 65 references.
References · 38
- 2017Proximal Policy Optimization Algorithmscited by 14,441
- 2017Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networkscited by 4,861
- 2018Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actorcited by 4,635
- 2018Addressing Function Approximation Error in Actor-Critic Methodscited by 2,302
- 2015Deep Reinforcement Learning with Double Q-learningcited by 1,704
- 2019Mastering Atari, Go, Chess and Shogi by Planning with a Learned Modelcited by 1,327
- 2019Meta-World: A Benchmark and Evaluation for Multi-Task and Meta Reinforcement Learningcited by 1,168
- 2015Prioritized Experience Replaycited by 1,070
- 2018DeepMind Control Suitecited by 935
- 2019Leveraging Procedural Generation to Benchmark Reinforcement Learningcited by 478
- 2021Brax -- A Differentiable Physics Engine for Large Scale Rigid Body Simulationcited by 375
- 2018Quantifying Generalization in Reinforcement Learningcited by 345
26 more
- 2015Risk-Sensitive and Robust Decision-Making: a CVaR Optimization Approachcited by 162
- 2020A Closer Look at Invalid Action Masking in Policy Gradient Algorithmscited by 160
- 2022Robust Reinforcement Learning using Offline Datacited by 95
- 2019Neo: A Learned Query Optimizercited by 80
- 2021Conservative Offline Distributional Reinforcement Learningcited by 78
- 2021RL for Latent MDPs: Regret Guarantees and a Lower Boundcited by 69
- 2021DR3: Value-Based Deep Reinforcement Learning Requires Explicit Regularizationcited by 66
- 2021Risk-Averse Offline Reinforcement Learningcited by 65
- 2018Learned Cardinalities: Estimating Correlated Joins with Deep Learningcited by 64
- 2020Bao: Learning to Steer Query Optimizerscited by 62
- 2023POPGym: Benchmarking Partially Observable Reinforcement Learningcited by 59
- 2017Markov Decision Processes with Continuous Side Informationcited by 54
- 2022Provable Benefits of Representational Transfer in Reinforcement Learningcited by 38
- 2022Doubly Robust Distributionally Robust Off-Policy Evaluation and Learningcited by 34
- 2018Learning to Optimize Join Queries With Deep Reinforcement Learningcited by 32
- 2023Near-Minimax-Optimal Risk-Sensitive Reinforcement Learning with CVaRcited by 32
- 2021Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluationcited by 30
- 2018Deep Reinforcement Learning for Join Order Enumerationcited by 25
- 2022Balsa: Learning a Query Optimizer Without Expert Demonstrationscited by 18
- 2019SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learningcited by 17
- 2018Learning State Representations for Query Optimization with Deep Reinforcement Learningcited by 14
- 2021Reinforcement Learning for Datacenter Congestion Controlcited by 11
- 2017Size bounds and query plans for relational joinscited by 10
- 2022AutoCAT: Reinforcement Learning for Automated Exploration of Cache-Timing Attackscited by 9
- 2019Estimating Cardinalities with Deep Sketchescited by 4
- 2023Deep learning based Auto Tuning for Database Management Systemcited by 1
Built on by
Citing papers per year: 2024: 1.
1 paper.