Learning to Optimize Join Queries With Deep Reinforcement Learning

By Sanjay Krishnan, Zongheng Yang, Ken Goldberg, Joseph M Hellerstein, Ion Stoica. 2018

250 citations recorded by the source corpus.

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

Subfields: Artificial Intelligence, Computer Networks and Communications

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

Citations in the corpus

Learning to Generalize Across Long-Horizon Tasks from Human Demonstrations (2020, background): “Imitation Learning (IL) is a promising paradigm to train physical robots on complex manipulation skills by replicating behavior from expert demonstrations [32, 24].”
Bao: Making Learned Query Optimization Practical (2020, methodology): “First, the representation is agnostic to the underlying schema: while prior work [29,39,41] represented tables and columns directly in their vectorization scheme, Bao omits them so that schema changes do not necessitate starting over from scratch.”
ALEX: An Updatable Adaptive Learned Index (2019, background): “Multiple works [27, 19, 15, 25] propose ideas to use reinforcement learning and convolutional neural networks to predict cardinalities and to optimize join queries.”
Learned Cardinalities: Estimating Correlated Joins with Deep Learning (2018, methodology): “Deep learning has been applied to query optimization by three recent papers [13, 23, 27] that formulate join ordering as a reinforcement learning problem and use ML to find query plans .”
Neo: A Learned Query Optimizer (2019, methodology): “While prior works [22,34] have flattened the tree structure of each partial execution plan, our encoding preserves the inherent tree structure of execution plans.”
Learning scheduling algorithms for data processing clusters (2018, unknown): “, query optimization [12], device placements [16]).”