PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning to Optimize Join Queries With Deep Reinforcement Learning

Sanjay Krishnan, Zongheng Yang, Ken Goldberg, Joseph Hellerstein, Ion Stoica

arXiv:1808.03196v2cs.DB

TL;DR

Join-order optimizers rely on heuristics because exhaustive search is combinatorially expensive, but those heuristics can be suboptimal under nonlinear cost models. DQ uses reinforcement learning connected to dynamic-programming enumeration to learn dataset-specific search strategies, and across workloads it achieves much faster planning while essentially matching native optimizers’ execution times. Its current scope is select-project-join optimization, with limitations in feature scope and the data demands of more end-to-end learning.

  • Problem

    Join-order heuristics avoid combinatorial exhaustive search but can be significantly suboptimal for nonlinear cost models, motivating dataset- and workload-specific search strategies.

  • Method

    DQ embeds Q-learning into classical join enumeration to learn search decisions from prior planning results for join ordering and physical operator selection.

  • Results

    DQ achieves planning speedups up to > 200× over dynamic-programming enumeration while essentially matching execution times of native optimizers’ optimal plans.

  • Takeaways & Limitations

    DQ provides a data-efficient learning-based alternative to programmed join-search heuristics that can integrate with existing DBMS optimizers.

  • Takeaways & Limitations

    The presented featurization targets inner joins over foreign-key relations, while an end-to-end runtime-mapping optimizer would require a significant corpus of runtime data and further model changes.

Abstract

from arXiv · show

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

1 INTRODUCTION

Join-order heuristics reduce a combinatorially complex search but can produce poor plans under nonlinear costs. DQ replaces fixed pruning with an RL-based strategy integrated into classical enumeration, achieving faster planning while retaining near-optimal plan quality.

  • Motivation: Join optimization’s combinatorial complexity makes heuristics ubiquitous, but restricted plan shapes and randomized pruning can fail in edge cases.System R-style dynamic programs often restrict plans to lef-deep shapes, while larger queries may use genetic or randomized search.
  • Motivation: Learning can synthesize dataset-specific join search strategies from prior planning outcomes for a given cost model and plan space.The goal is to tailor future searches to a particular dataset and workload while reducing search time.
  • Approach: DQ maps the sequential structure of join ordering onto reinforcement learning and applies learned policies wherever classical enumeration is used.This connection supports integration with System R-style optimizers and reduces training cost through the problem’s nested structure.
  • Approach: Q-learning relaxes exact dynamic-programming memoization by predicting the value of the next join decision from previously observed subplan costs.The classical lookup table is treated as a model that summarizes enumerated subplans and predicts subsequent decisions.
  • System integration: DQ optimizes select-project-join blocks, covering join ordering and physical operator selection, and has implementations for Calcite, PostgreSQL, and SparkSQL.The PostgreSQL and SparkSQL integrations each required fewer than 300 lines of code, with training data collected during normal DBMS operation at minimal overhead.
  • Training: DQ’s training data can include final plans, total costs, subplans, and recursively enumerated memoization contents from a single query.This structure provides abundant high-quality examples despite reinforcement learning’s typical data inefficiency.
  • Evaluation: > 200× planning speedups were achieved relative to dynamic-programming enumeration while execution times essentially matched native optimizers’ optimal plans.Across Join Order Benchmark and TPC-DS, DQ also improved plan quality under nonlinear cost models and enabled broader plan spaces.
  • Evaluation: Figure 1 evaluates cost suboptimality under three Join Order Benchmark cost models, where the classical lef-deep dynamic program fails in the two nonlinear scenarios.The models vary by inexpensive index lookups, limited-memory hybrid hash joins, and reuse of previously built hash tables.

2 BACKGROUND

Join optimization is difficult because exhaustive search is combinatorial, while heuristics can fail under non-linear cost models. The paper frames join enumeration as sequential decision-making and motivates Q-learning as a way to reduce search cost while preserving plan quality.

  • Join optimization background: Non-linear join costs can make classical heuristics dramatically suboptimal, with left-deep plans nearly 50x more costly than optimal in the cited scenario.Under index-join-favoring costs, the same heuristic was only 2x above optimal, but hybrid hash joins with spilling or hash-table reuse exposed its weakness.
  • Join enumeration: A query graph represents relations as vertices and join predicates as edges, while each join action merges two connected vertices.Each merge reduces the number of vertices by one and updates incident edges through union.
  • Markov model of enumeration: The join-ordering process defines an MDP in which the query graph is the state, a join is the action, transitions merge vertices, and reward is negative cost.This representation maps sequential plan construction onto reinforcement-learning terminology.
  • Long-term reward: Greedy join selection costs 140 versus 110 for the optimal plan, although greedy search runs in O(|V|^3).The gap arises because local choices neglect their future effects.
  • Applying reinforcement learning: Deep RL approximates a global Q-function so repeatedly choosing the lowest-Q join can yield a provably optimal sequence with greedy-search complexity.The learned model can also generalize Q-function estimates across similar subplans when graph and join features are sufficiently expressive.
  • Applying reinforcement learning: Q-learning is selected because it exploits optimal substructures, scores every available join, integrates with existing optimizer state, and supports top-k planning.The paper contrasts this with policy learning, which selects only the best join.

3 OPTIMIZER ARCHITECTURE

DQ replaces traditional join-search algorithms with a learned Q-learning strategy while retaining the classical select-project-join focus. Its training uses optimizer-generated offline data, including optimal subplans and deliberately diversified decisions.

  • DQ focuses on learning plan search for the classical select-project-join kernel rather than replacing cost or selectivity estimation.
  • Training Data: Q-learning uses offline state-decision-transition-cost records, allowing training independently of the data-collection policy when decisions are sufficiently covered.
  • Architecture and API: DQ requires workload generation, optimizer-based cost sampling, and selectivity estimation hooks to collect training data.The API includes train(query) and selectivity(predicate) interfaces.
  • Efficient Training Data Generation: A single classically optimized query supplies final-plan, optimal-subplan, and other memoized training examples, making join-specific data collection efficient.The principle of optimality lets one plan emit multiple examples sharing the same long-term cost.
  • Efficient Training Data Generation: DQ uses Q-learning because join plans contain optimal substructures, whereas episodic methods learn from complete decision sequences and final cumulative rewards.
  • Efficient Training Data Generation: Training data must balance optimal plans with diverse costly subplans; DQ injects random join choices with probability ϵ to encourage exploration.The optimizer otherwise chooses the lowest-cost valid join.

4 REALIZING THE Q-LEARNING MODEL

DQ represents query states and join decisions with features describing visible attributes, selections, and physical operators, then learns a Q-function to choose joins. At execution, it repeatedly selects the candidate with the lowest estimated Q-value.

  • Featurizing the Join Decision: DQ’s featurization describes the overall query graph and both sides of a candidate join using concatenated binary one-hot attribute encodings.For a query graph G and decision c, the overall representation is fG ⊕ fc.
  • Featurizing the Join Decision: Selection features scale attribute slots using estimated predicate selectivities, while physical-operator features append a one-hot implementation vector.The operator vector can distinguish choices such as IndexJoin and HashJoin.
  • Extensibility: DQ initially focuses on foreign-key equality joins, although its architecture can incorporate additional properties relevant to join-cost prediction.
  • Q-Learning Model: A two-layer MLP represents the Q-function, taking the combined query-and-decision featurization as input and training with stochastic gradient descent.The reported training-time constraint is under 10 minutes.
  • Operating the Model: During execution, DQ featurizes each candidate join, selects the lowest estimated Q-value, updates the query graph, and repeats.Batched neural-network evaluation provides vectorization opportunities across candidate joins.

5 FEEDBACK FROM EXECUTION

DQ can use execution feedback to correct mismatches between optimizer cost models and observed runtimes. Fine-tuning freezes learned representation layers and retrains only a newly initialized output layer on real execution data.

  • Cost models may diverge from runtimes because of poor cardinality estimates or unrealistic estimation rules, motivating execution feedback for learned Q-functions.
  • Fine-Tuning: Fine-tuning first pre-trains DQ on inexpensive cost-model samples, then freezes the first two layers and retrains a reinitialized output layer on execution runtimes.
  • Fine-Tuning: The retained network layers learn general subplan features, while the retrained output layer projects those features onto real runtimes.
  • Execution Data: Fine-tuning records per-operator execution times in (Graph, Join, Graph’, OpTime) data, obtainable through instrumentation or EXPLAIN ANALYZE in Postgres.

6 EVALUATION

DQ is evaluated across workloads, cost models, training regimes, and database systems. It remains competitive in plan quality while substantially reducing optimization time, with benefits extending to execution performance after learning.

  • Evaluation scope: DQ is evaluated on standalone workloads and integrated PostgreSQL and SparkSQL systems across multiple cost models and training settings.The experiments address plan quality, optimization efficiency, data requirements, and real-world deployment.
  • Plan quality: DQ stays within 22% of the lef-deep solution on average and is at most 1.45× worse in the worst case.These results concern cases where effective heuristics already exist.
  • Plan quality: 1.68× average relative cost: DQ remains close to exhaustive enumeration under CM2, where heuristics fail by orders of magnitude.Its worst query is about 12× the optimal cost, while mixed lef-deep and right-deep structures are needed.
  • Planning latency: Up to 10,000× faster than exhaustive enumeration and > 10× faster than lef-deep: DQ’s largest-join planning speedups arise from bounded neural evaluations and batching.DQ upperbounds neural-network invocations by the number of relations in a query.
  • Deployment: DQ can collect training data from an existing system with relatively minimal execution impact, especially when logging is asynchronous.This supports deployment alongside production-grade optimizers.
  • System integration: 14% average execution speedup: DQ outperforms PostgreSQL across the JOB workload while planning up to 3× faster for large joins.Small joins incur neural-network overhead, but fine-tuning with real runtimes can reduce execution time from 70.0s to 20.3s.
  • System integration: 3.6× mean optimization speedup and 1.0× mean execution speedup: DQ matches SparkSQL execution while planning TPC-DS queries faster.The largest TPC-DS query reaches a maximum optimization speedup of 250×.

7 RELATED WORK

Related work spans learned cost functions, learned cardinality and query representations, adaptive query optimization, robustness, and scalable randomized enumeration. DQ differs by learning workload-level join search strategies rather than replacing cost estimation or adapting tuple processing.

  • Cost Function Learning: Cost-function learning uses execution feedback or statistical models to correct inaccuracies in query cost estimation.Prior systems such as LEO target the cost model rather than join-search strategy.
  • Cost Function Learning: A neural selectivity estimator required 1000 queries for an attribute with 10k distinct values, illustrating the data demands of cost-function learning.The approach also depends heavily on learning structure in literal values.
  • Learning in Query Optimization: Prior learning-based query optimization work includes query representations, cardinality estimates, and the preliminary deep-RL join optimizer ReJOIN.These approaches provide related ways to place learning inside query optimizers.
  • Adaptive Query Optimization: Adaptive query optimization makes sequential decisions over tuples during execution, whereas DQ adapts at the workload level during fixed-database optimization.The paper notes that continuously updating a neural network is challenging for fine-grained tuple-level adaptivity.
  • Robustness: DQ is agnostic to piecewise-linear cost-model structure and learns heuristics for different cost regimes from data.This contrasts with parametric query optimization, which studies piecewise-linear cost models explicitly.
  • Join Optimization At Scale: Randomized and genetic algorithms scale join optimization pragmatically, often becoming relevant when the number of tables grows beyond a threshold.Their challenge is that scalable search methods trade exhaustive coverage for efficiency.

8 DISCUSSION, LIMITATIONS, AND CONCLUSION

DQ is presented as a step toward learning query optimizers, with a featurization currently designed for foreign-key inner joins and a broader algebraic scope envisioned. The paper also identifies the need for substantial runtime data for end-to-end learning.

  • Limitations: The current featurization targets inner joins over foreign-key relations, while extensions to conjunctive binary join predicates are described as relatively straightforward.The restriction reflects benchmark composition rather than a fundamental limitation.
  • Conclusion: DQ is proposed as a step toward learning query optimizers beyond select-project-join blocks, including outer joins, cross-block optimizations, and non-relational operators.The paper frames these extensions as algebraic transformation spaces amenable to dynamic programming.
  • Limitations: End-to-end learning would map subplan features to measured runtimes, but it would require a significant corpus of runtime data.The paper presents this as an architectural ambition rather than the implemented approach.

A STANDALONE OPTIMIZATION EXPERIMENT SETUP

The standalone experiments compare DQ with representative enumeration algorithms and heuristics across three cost models, including memory and hash-table-reuse effects. They use true or constructed cardinality estimates and evaluate suboptimality against exhaustive enumeration.

  • Cost models: Three cost models capture index and hash joins, memory-limit nonlinearities, and reuse of already-built hash tables.The latter two models make intermediate-relation sizes or plan shape important to cost.
  • Evaluation: The experiments use true single-table predicate cardinalities and standard independence assumptions for more complicated estimates.The authors state that DQ also remains effective with PostgreSQL and SparkSQL native cost models and cardinality estimates.
  • Baselines: The baselines include exhaustive, left-deep, right-deep, zig-zag, IK-KBZ, QuickPick-1000, Minimum Selectivity, and Linearized Dynamic Program algorithms.These methods represent exhaustive enumeration, restricted plan spaces, randomized search, and heuristic approaches.
  • Evaluation: EX is the optimal baseline, and results are reported as cost_algo/cost_EX across all 113 JOB queries, with 80 training and 33 test queries.LDP was omitted from the main body because its results were highly correlated with IK-KBZ and left-deep enumeration.
  • Findings: Threshold nonlinearities, particularly those represented by CM3, cause the most problems for heuristics.The study omits a simplified join-order-only model because the techniques showed no differences there.

C ADDITIONAL STANDALONE EXPERIMENTS

The additional standalone experiments characterize when DQ works and how efficiently.

  • The experiments subsequently characterize when DQ is expected to work and how efficiently.

C.1 Sensitivity to Training Data

DQ’s performance varies with training data but shows relatively low variance and remains competitive in macro-benchmarks. Under noisy cardinalities, it is no more sensitive than KBZ and closely imitates exhaustive enumeration.

  • Sensitivity to Training Data: DQ’s randomness comes from the training data it sees, unlike the deterministic baselines except QuickPick-1000.The variance experiment uses five training datasets and evaluates 20 hold-out queries.
  • Sensitivity to Training Data: DQ’s performance variance is relatively low and remains competitive in macro-benchmarks even under the worst observed case.Its variance is also substantially lower than QuickPick-1000’s.
  • Sensitivity to Faulty Cardinalities: Cardinality estimates from underlying RDBMSs are often not up to date, motivating sensitivity analysis for DQ and classical optimizers.
  • Sensitivity to Faulty Cardinalities: The faulty-cardinality microbenchmark trains DQ on noisy relation sizes and tests it on true cardinalities across 20 JOB queries with 6–11 relations.Perturbations multiply selected true cardinalities by factors from {2, 4, 8, 16}.
  • Sensitivity to Faulty Cardinalities: DQ is no more sensitive than KBZ under cardinality perturbations and closely imitates exhaustive enumeration when trained on EX plans with faulty estimates.The text notes only a slight degradation for N = 4 execution.
  • Sensitivity to Training Data: Fine-tuning is the most effective DQ variation among fully offline, fine-tuned, and fully online approaches for q10c.Figure 12 compares single-query runtime in milliseconds.

C.3 Ablation Study

The ablation study evaluates DQ’s feature representation and finds that removing query-graph features and selectivity scaling substantially worsens training loss.

  • Table 9 reports an ablation study of DQ’s featurization.
  • 3.5× more training loss occurs without query-graph features and selectivity scaling.
  • The results suggest that the different feature types contribute positively to performance.

D DISCUSSION ABOUT POSTGRES EXPERIMENT

The PostgreSQL experiments examine online-only training, plan-space restrictions, and comparison with the genetic optimizer. DQ’s execution advantage can persist within the native plan space and is especially large against GEQ, despite slightly slower planning.

  • Online-only training failed to converge even when optimizing a single query in the idealized Q10c workload.The authors attribute the discrepancy to the added difficulty of physical operator selection.
  • Physical operator selection makes the learning problem significantly harder than selecting logical plans while leaving physical choices to PostgreSQL.
  • DQ retained a statistically significant execution-time speedup when restricted to the same left-deep plan space as native PostgreSQL.
  • The evaluated plan spaces compare DQ’s execution-time speedup over PostgreSQL using workload-average and best-case single-query measures.
  • The authors speculate that DQ’s speedup may reflect smoothing inconsistencies caused by imprecision in PostgreSQL’s cost model.
  • DQ was about 7% slower than GEQ in planning but nearly 10× faster in execution on JOB’s 10 largest joins.One outlier query accounted for much of the execution difference, with GEQ 37× slower there.
Loading 1808.03196v2…