Source-linked AI summary
Learning State Representations for Query Optimization with Deep Reinforcement Learning
Jennifer Ortiz, Magdalena Balazinska, Johannes Gehrke, S. Sathiya Keerthi
TL;DR
Query optimization remains difficult because existing cardinality estimates can produce poor plans. This paper learns incremental subquery representations and uses them to form neural state transitions for reinforcement-learning-based plan enumeration, reporting preliminary cardinality-estimation improvements over SQL Server while identifying reward and state-space limitations.
Problem
Query optimization remains difficult because simplifying assumptions in cardinality estimation can cause frequent errors and sub-optimal plan selections.
Method
A deep model recursively combines a subquery representation with a relational operation, predicting observed properties that train the latent state representation and transition function.
Results
The model eventually outperforms SQL Server’s cardinality estimates for selection queries with m = 3 and m = 5 columns.
Takeaways & Limitations
The learned representations provide an initial basis for using reinforcement learning to incrementally enumerate query plans.
Takeaways & Limitations
The approach currently builds only left-deep plans, and using cardinality estimates as rewards optimizes logical query plans only.
Abstract
from arXiv · showhide
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 variety of domains. In the database field, query optimization remains a difficult problem. Our goal in this work is to explore the capabilities of deep reinforcement learning in the context of query optimization. At each state, we build queries incrementally and encode properties of subqueries through a learned representation. The challenge here lies in the formation of the state transition function, which defines how the current subquery state combines with the next query operation (action) to yield the next state. As a first step in this direction, we focus the state representation problem and the formation of the state transition function. We describe our approach and show preliminary results. We further discuss how we can use the state representation to improve query optimization using reinforcement learning.
1 INTRODUCTION
Query optimization remains difficult because simplifying assumptions cause cardinality-estimation errors and poor plans. The paper proposes learned subquery representations and state transitions for incremental reinforcement-learning-based plan construction.
- Motivation: Simplifying assumptions about data distributions frequently cause cardinality-estimation errors and sub-optimal query plans.Existing systems avoid some richer estimation methods because of their overhead and complexity.
- Motivation: A deep model can learn data properties for cardinality prediction instead of relying entirely on basic, hand-designed statistics.The authors identify query and data representation as a central challenge.
- Approach: The proposed model incrementally generates a succinct representation of each subquery’s intermediate results from a subquery and a new operation.The learned properties can be used to derive subquery cardinalities.
- Approach: The learned state representation is intended to support reinforcement learning for incrementally constructing query plans.After training, the model can be fixed while reinforcement learning learns an action policy.
- Approach: Each query-plan action transitions a database or subquery representation to a new state through a recursive neural state-transition function.The function maps a previous representation and action to the next subquery representation.
2 BACKGROUND
The background introduces deep networks as nonlinear function approximators whose hidden layers can learn reusable representations, and reinforcement learning as trial-and-error action selection for cumulative reward.
- Deep Learning: Deep learning models approximate nonlinear functions by mapping inputs to outputs through learned parameters across multiple layers.Their hidden layers are learned rather than directly specified by the input data.
- State Transition: The state-transition-function example illustrates extracting a subquery representation from a hidden state and action using NNST.NNST is trained by predicting observed properties through NNObserved.
- Deep Learning: Hidden layers can learn representations indirectly while optimizing an objective, creating a trade-off between information preservation and useful properties.The representation’s context depends on the network’s output.
- Reinforcement Learning: Reinforcement learning maps observed scenarios to actions while maximizing cumulative reward through exploration and exploitation.Unlike supervised learning, it does not explicitly provide the best action.
3 LEARNING A QUERY REPRESENTATION
The paper learns compact query and relation representations recursively, using neural models to predict cardinalities and propagate subquery states through operations. Preliminary experiments on IMDB show that the models can match or outperform SQL Server estimates, although convergence slows as selections involve more columns.
- 3 LEARNING A QUERY REPRESENTATION: The approach learns compact representations of queries and relations by training them to predict subquery cardinalities.These representations are intended to capture informative properties without relying entirely on manually specified features.
- 3 LEARNING A QUERY REPRESENTATION: NNST recursively takes a subquery representation and relational operation, then predicts observed variables and the representation of the resulting subquery.NNinit and NNST are trained together so the hidden state supports both current and extended subqueries.
- 3 LEARNING A QUERY REPRESENTATION: NNinit maps database properties and an initial relational operation to a cardinality and learned initial representation.Its input includes per-attribute minimum, maximum, distinct-value count, and a one-dimensional histogram.
- 3 LEARNING A QUERY REPRESENTATION: The experiments use the real IMDB dataset from JOB, which contains skew and correlations across columns.The initial NNinit experiment generates 20k selection queries, using 15k for training and the remainder for testing.
- 3 LEARNING A QUERY REPRESENTATION: At the 6th epoch, NNinit performs similarly to SQL Server for three-column selections and subsequently outperforms it.With five selected columns, convergence takes longer, but the model still improves on SQL Server’s estimates by the 9th epoch.
4 QUERY PLAN ENUMERATION WITH REINFORCEMENT LEARNING
The design combines learned subquery representations with reinforcement learning to construct query plans incrementally. It specifies state context, Q-learning updates, and reward choices while identifying reward design and state-space size as open problems.
- Query-plan construction: The system uses subquery representations from NNST with reinforcement learning to identify good query plans.The representations support both cardinality estimation and query-plan construction.
- State representation: At each state, the model encodes remaining query operations in a contextual vector and transitions by selecting an operation from the query.The environment is model-free, so transition probabilities are not known in advance.
- Reward design: Negative cost estimates can reward plans but would make the system mimic the traditional optimizer and currently restrict construction to left-deep plans.The authors propose eventually using negative query execution time to capture physical plan properties.
- Reinforcement learning: Q-learning updates state-action values as the agent explores actions, using rewards observed in successor states and a greedy estimate of future value.Actions are usually selected with an ϵ-greedy behavior policy, while the target uses the maximum value at the subsequent state.
- Open problems: Reward-function choice and the large state space remain open problems because separately estimating values for each unique subquery makes initial Q-learning impractical.The stated action space already includes selections and joins.
5 RELATED WORK
Related work applies adaptive processing, feedback, neural networks, and reinforcement learning to database optimization. This paper differs by learning latent state vectors propagated across subqueries and using value-based iteration rather than policy gradients.
- Adaptive query processing: Eddies removes the optimizer and uses an eddy policy to determine operator order, while Tzoumas et al. formulate adaptive processing as reinforcement learning.In the latter formulation, states represent tuples with metadata about remaining operators and actions select operators.
- Learned estimation: Leo uses feedback from repeated similar queries, while Liu et al. apply neural networks mainly to cardinality prediction for selection queries.These approaches address optimizer estimates but differ in reuse requirements and query scope.
- Learned data representations: Kraska et al. use neural networks to learn attribute distributions for building fast indexes, whereas this paper targets cross-column correlations and query-plan construction.The related work therefore distinguishes index learning from query optimization.
- Deep reinforcement learning: Unlike Marcus et al., this approach learns latent vectors propagated across subqueries and proposes value-based iteration instead of policy gradients.Marcus et al. determine join orders for a fixed database using states that also represent subqueries.
6 CONCLUSION
The paper describes deep reinforcement learning for query optimization by incrementally learning subquery state representations. It proposes combining those representations with reinforcement learning to learn optimal plans.
- Conclusion: The model uses deep neural networks to incrementally learn state representations of subqueries from basic information about the data.This is presented as the paper’s deep reinforcement learning model for query optimization.
- Conclusion: Future work will combine the learned state representations with reinforcement learning to learn optimal query plans.The passage states this as a proposed next step rather than a completed result.