Source-linked AI summary
Deep Reinforcement Learning for Join Order Enumeration
Ryan Marcus, Olga Papaemmanouil
TL;DR
Static join enumeration can repeatedly choose poor plans because it lacks feedback from prior optimization and execution. This paper introduces ReJOIN, a deep-reinforcement-learning join enumerator, and reports preliminary results matching or outperforming PostgreSQL in plan quality and enumeration efficiency.
Problem
Static query optimizers lack feedback about prior plan quality, so they may repeatedly select the same bad join plan.
Method
ReJOIN formulates join-order enumeration as reinforcement learning, using neural-network action probabilities and reciprocal join-tree cost as the terminal reward.
Results
ReJOIN can generate join orderings with cost and latency as good as, and often better than, PostgreSQL's plans.
Takeaways & Limitations
After 10,000 training queries, ReJOIN's average generated-plan cost reaches 80% of PostgreSQL's plan cost, indicating learning of effective join orderings.
Takeaways & Limitations
ReJOIN uses the cost model as a proxy reward rather than actual execution latency and currently handles only join-order selection.
Abstract
from arXiv · showhide
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.
1 Introduction
Join ordering strongly affects query performance, but exhaustive search increases optimization time and static optimizers do not learn from prior plans. The paper proposes deep reinforcement learning for adaptive, efficient join enumeration.
- Join ordering can drastically affect query performance, making selection of a cost-effective ordering a central database-systems problem.
- Larger candidate spaces increase the chance of finding low-cost orderings but require more query-optimization time.Enumerators therefore seek to minimize both the number of plans considered and the final plan cost.
- Traditional strategies include dynamic programming, greedy pair selection, and structurally constrained exhaustive enumeration.These approaches differ in how they restrict or search the space of possible join trees.
- Heuristic optimizers can miss good execution plans and static systems do not learn from previous successes or failures.Without feedback, an optimizer may repeatedly select the same bad plan.
- The paper proposes a learning-based optimizer using deep reinforcement learning to improve future query plans while reducing optimization time.The approach leverages information from previously processed queries and uses an artificial neural network.
- ReJOIN is a proof-of-concept deep-reinforcement-learning join enumerator that preliminary results indicate can outperform PostgreSQL in effectiveness and efficiency.
2 The ReJOIN Enumerator
ReJOIN formulates join-order enumeration as a deep reinforcement learning process that incrementally combines subtrees, represents query information as vectors, and updates a neural-network policy from episode rewards.
- ReJOIN Enumerator: ReJOIN is a proof-of-concept join-order enumerator driven entirely by deep reinforcement learning.It targets join ordering while leaving operator and index selection to other optimizer components.
- Framework Overview: Each query is an episode: states encode partial binary join trees and predicates, while actions combine two subtrees.The episode ends when all input relations form a complete ordering.
- Framework Overview: A terminal ordering receives reward equal to the reciprocal of its join-tree cost, whereas non-terminal partial orderings receive zero reward.The agent periodically uses accumulated experience to adjust the neural-network weights toward larger rewards.
- State Vectors: ReJOIN represents each subtree with relation-height vectors, join predicates with an n×n binary symmetric matrix, and selection predicates with a k-dimensional attribute vector.These representations encode tree structure, feasible equi-joins, and which attributes have selection predicates.
- Reinforcement Learning: A policy-gradient neural network converts vectorized states into action probabilities, samples join actions, and updates its parameters using experience from completed query episodes.The policy network balances exploration and exploitation through action sampling, while prior episodes provide observations for gradient estimation.
3 Preliminary Results
ReJOIN was evaluated on the Join Order Benchmark after training with 10,000 queries, showing improved plan quality and relatively stable planning time as query size grows.
- Experimental setup: ReJOIN was trained on 103 queries and tested on 10 queries from the Join Order Benchmark, using PostgreSQL on a 2-core, 4GB-RAM virtual machine.The benchmark contains 113 query instances spanning 33 templates, with queries joining 4–17 relations.
- Learning convergence: After 10,000 observed queries, ReJOIN generated plans averaging 80% of PostgreSQL’s cost.ReJOIN began finding lower predicted-cost plans at around 8,000 observed queries.
- Optimizer costs: ReJOIN produced plans averaging 20% lower PostgreSQL cost on the 10 test queries, with a worst case only 2% higher.The comparison used PostgreSQL’s cost model and included PostgreSQL, Quickpick, and ReJOIN.
- Query latency: ReJOIN’s executed plans matched or outperformed PostgreSQL’s latency in every test case under 10 cold-cache executions per query.Figure 5b reports minimum, maximum, and median latency improvement relative to PostgreSQL.
- Planning latency: ReJOIN’s planning time remains relatively flat as relations increase, while PostgreSQL’s optimization time grows worse-than-linearly.ReJOIN combines two subtrees per round, yielding model application time linear in the number of relations.
- Policy update overhead: Policy updates add less than 12ms per episode, and skipping updates after convergence reduces planning time by an additional 10% to 30%.The reported reduction applies once the ReJOIN model is sufficiently converged.
4 Open challenges & ongoing work
The paper identifies limitations in ReJOIN’s reward signal and scope, and proposes directions for using execution latency and broader optimizer decisions.
- Research direction: The authors characterize ReJOIN as a simple approach that opens research paths for applying deep reinforcement learning to query optimization.This conclusion is presented as an indication of room for further advancement.
- Latency optimization: ReJOIN uses the cost model instead of actual execution latency because cardinality estimates can be error-prone and executing early poor plans is costly.The authors are investigating expert-system bootstrapping to accelerate learning.
- End-to-end optimization: ReJOIN handles only join order selection, leaving operator selection, index selection, and predicate coalescing to other optimizer components.The proposed expansion would add operator-level decisions to the action space.