JoinGym: An Efficient Query Optimization Environment for Reinforcement Learning

2023-07-21 · Kaiwen Wang, Junxiong Wang, Yueying Li, Nathan Kallus, Immanuel Trummer, Wen Sun

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.

📄 PDF Abstract BibTeX arXiv:2307.11704

Code (1)

kaiwenw/JoinGym 공식 구현 pytorch

Tasks

BenchmarkingCombinatorial OptimizationManagement reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Learning State Representations for Query Optimization with Deep Reinforcement Learning

2018-03-22 · Jennifer Ortiz, Magdalena Balazinska, Johannes Gehrke, S. Sathiya Keerthi

Deep reinforcement learning is quickly changing the field of artificial intelligence. These models are able to capture a high level understanding of their environment, enabling them to learn difficult dynamic tasks in a …

Deep Reinforcement Learning reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

FOSS: A Self-Learned Doctor for Query Optimizer

2023-12-11 · Kai Zhong, Luming Sun, Tao Ji, Cuiping Li 외

Various works have utilized deep learning to address the query optimization problem in database system. They either learn to construct plans from scratch in a bottom-up manner or steer the plan generation behavior of tra…

Deep Reinforcement Learning

Solving Packing Problems by Conditional Query Learning

2019-09-25 · Dongda Li, Changwei Ren, Zhaoquan Gu, Yuexuan Wang 외

Neural Combinatorial Optimization (NCO) has shown the potential to solve traditional NP-hard problems recently. Previous studies have shown that NCO outperforms heuristic algorithms in many combinatorial optimization pro…

Combinatorial Optimization

Join Query Optimization with Deep Reinforcement Learning Algorithms

2019-11-26 · Jonas Heitz, Kurt Stockinger

Join query optimization is a complex task and is central to the performance of query processing. In fact it belongs to the class of NP-hard problems. Traditional query optimizers use dynamic programming (DP) methods comb…

Attribute Deep Reinforcement Learning Ensemble Learning Q-Learning+3

Seq2SQL: Generating Structured Queries from Natural Language using Reinforcement Learning

2017-08-31 · ICLR 2018 1 · Victor Zhong, Caiming Xiong, Richard Socher

A significant amount of the world's knowledge is stored in relational databases. However, the ability for users to retrieve facts from a database is limited due to a lack of understanding of query languages such as SQL. …

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)Text-To-SQL