REVIEW 4 major objections 6 minor 25 references
A Novel Framework Using Deep Reinforcement Learning for Join Order Selection
T0 review · 4 major / 6 minor · reviewed 2026-08-11 · deepseek-v4-flash
Pith's one-line read The paper claims that a deep reinforcement learning agent can learn SQL join orders that match or beat a database's dynamic-programming optimizer, by encoding the query graph and partial join tree and training with Dueling-DQN and a…
desk verdict Plausible DRL join-order framework with a useful reward idea, but the headline empirical claim is undercut by modified baselines and no code. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing machinery is the state encoder paired with a normalized reward. For each query, a GNN over the join-graph adjacency matrix produces the query representation $R(q)$; the current partial plan is a forest of join trees, encoded by n-ary Tree-LSTM for each tree (preserving the order in which joins were chosen) and child-sum Tree-LSTM for the whole forest (independent of how many trees remain), giving $R(F)$. The state is the concatenation $R(s) = R(q) \oplus R(F)$, fed into Dueling-DQN, where the value stream estimates the worth of being in the state and the advantage stream estimates the relative worth of each action before the two are combined. The terminal reward is $r = \log(DP_{\text{feedback}} / GTDD_{\text{feedback}})$, compressing feedback from queries with very different cost magnitudes into a comparable scale. Curriculum learning sorts training queries by join count and adds harder partitions over time, and an action mask sets to zero any join that does not correspond to an existing join predicate. The framework's argument is that these pieces jointly give the agent a state representation that reflects both the query and the plan built so far, a reward that is comparable across heterogeneous queries, and an exploration space that excludes obviously invalid actions.
What would settle it
Run GTDD on a query set that includes cyclic join graphs where exhaustive dynamic programming, with cross joins allowed, shows that the cheapest plan uses an intermediate Cartesian product—for example, a three-table cycle with a selective cross join between non-adjacent tables. Because GTDD's action mask omits such joins, its best expressible plan will be worse than the unrestricted DP plan, so its MRC on those queries will exceed 1 and the claim of DP-level plan quality would fail exactly where the mask is active.
Extended reading notes
Core claim
The paper's central claim is that combining hierarchical plan representation with an improved deep-Q architecture yields better learned join orders than either ingredient alone. GTDD encodes a query at column, table, and query-graph levels—columns carry predicate and selectivity features, tables combine column embeddings with Node2Vec schema embeddings, and the query graph passes through a TransformerConv GNN—and encodes the current partial plan as a join forest using n-ary Tree-LSTM for each join tree and child-sum Tree-LSTM for the whole forest. That state feeds Dueling-DQN, which estimates state value and action advantage in separate streams. The reward is the log ratio of the DP baseline's cost (or latency) to GTDD's own, so queries of very different scales are scored on a common relative basis, and curriculum learning introduces queries with more joins only after simpler ones. On this setup the paper reports a mean relative cost (MRC) of 1.06313 for GTDD on JOB versus 1.13165 for the same framework with vanilla DQN (GTD), 1.22442 for RTOS, and 1.54444 for JOGGER; after latency tuning, the geometric mean relative latency (GMRL) is 0.60381 for GTDD versus 0.80425, 0.83313, and 1.16758 respectively, and 0.96399 on TPC-H. The authors take these numbers as showing that Dueling-DQN stabilises training and that the combination, not any single component, outperforms prior DRL join-order selection.
Load-bearing premise
The learned policy can only join tables that are connected by an explicit join condition in the query, so a plan that needs an intermediate cross join of unrelated tables can never be produced; if any query's optimal plan requires such a cross join, GTDD's search is restricted before learning begins.
Editorial extensions
If this is right
- A single learned policy can produce plans with DP-level estimated cost on a workload with up to 21 joins, meaning exhaustive enumeration is not necessary once the representation and reward are in place.
- The same framework with vanilla DQN (GTD) is measurably worse than GTDD, so the choice of Dueling-DQN's separated value and advantage streams contributes to plan quality, not just training speed.
- Cost-trained models transfer to latency tuning: GTDD's plans are about 40% lower in geometric-mean relative latency than DP plans on JOB, so a learned optimizer can be steered by real execution feedback rather than only by cost estimates.
- The log-ratio reward makes one reward scale work for queries with very different costs, which is a prerequisite for training a curriculum from 3-join to 21-join queries in a single agent.
- On the 8-table TPC-H schema, every learned method is close to DP, indicating the approach pays off where the join search space is large; that is the regime where traditional enumeration is most expensive.
Reading between the lines
- The paper leaves implicit that its action mask bans Cartesian-product joins; a testable extension is to relax the mask on cyclic or star-schema queries whose optimal plans may need a cross join, and check whether the log-ratio reward still converges to the unrestricted DP plan.
- The reward requires a DP baseline for every training query, which is the expensive computation a learned optimizer is meant to avoid in deployment; substituting a cheaper heuristic or learned baseline as the denominator would measure how much of the reported margin survives without oracle feedback.
- The saturation of all methods on TPC-H suggests the advantage is concentrated in large search spaces, so one prediction is that on schemas with more tables or cyclic join graphs the gap over attention-based JOGGER widens unless the action mask becomes the binding restriction.
- The reported similarity between GTD and RTOS in final GMRL (0.804 vs 0.833), despite very different state encoders, suggests the dueling architecture rather than the GNN may be the main driver of latency improvement; separately ablating GNN and Tree-LSTM under the same RL algorithm would isolate the contributions.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes GTDD, a deep reinforcement learning framework for join order selection that combines graph neural networks, Tree-LSTM, and Dueling-DQN, together with a log-ratio reward and curriculum learning. The authors evaluate GTDD on JOB and TPC-H, reporting that it outperforms the DRL-based baselines RTOS and JOGGER and performs comparably to PostgreSQL's dynamic programming optimizer. The central claim is that GTDD achieves a 'clear advantage' over state-of-the-art techniques in both estimated cost (MRC) and true latency (GMRL).
Significance. If the central claim were supported, GTDD would be a useful contribution to learned query optimization, since it integrates several representation-learning ideas (GNN, Tree-LSTM) with a relatively advanced RL algorithm (Dueling-DQN) and a normalization-based reward. The paper deserves credit for including an ablation of the RL component (GTD vs. GTDD) and for reporting both cost and latency metrics. However, the experimental validation has serious methodological flaws that undermine the claim: the baselines are re-implemented with the proposed reward function instead of their original reward designs, the reported MRC values are the best observed during training rather than the final policy's performance, and the action mask restricts the search space without justification. These issues are load-bearing for the paper's main conclusion.
major comments (4)
- [§8.2] The sentence 'For the sake of fairness, all the related work employs the reward function we propose' indicates that RTOS and JOGGER are not evaluated with their published reward functions but with the authors' log-ratio reward (Eq. 5). This does not establish that GTDD outperforms the state-of-the-art methods as published; it only shows that GTDD with its reward outperforms re-implemented variants that share that reward. The reported margins (e.g., MRC 1.063 vs. 1.224 in Table 1) may be due to the reward function rather than the architectural contributions. The authors must compare against the original RTOS and JOGGER implementations with their original reward functions, or clearly frame the current comparison as an ablation of the reward component.
- [Tables 1 and 2] The MRC values reported in Table 1 are the 'Optimal MRC' values, i.e., the lowest MRC observed during training (as explicitly listed in Table 2), not the performance of the final policy at the end of training. This best-checkpoint reporting selects the most favorable evaluation point and overstates the methods' practical performance. Since these values are used as the headline numerical claims, the paper does not follow a standard evaluation protocol for RL agents. The authors should report the MRC of the final policy after a fixed training budget, or use a consistent protocol such as the average over the last K checkpoints.
- [§7.3] The action mask prohibits joins that produce Cartesian products, restricting the agent to plans that only join components connected by an edge in the query graph. The paper does not justify this restriction. For the connected query graphs in JOB and TPC-H, an optimal plan may often be representable without cross products, but this is not guaranteed in general, and the paper does not provide an argument or empirical evidence that the mask never excludes the optimal plan for the tested workloads. The authors should either justify the restriction (e.g., by proving that for connected graphs with standard cost models, the optimal plan can always be expressed without Cartesian products) or evaluate on workloads where cross products are necessary.
- [§8] All reported results are from a single run without error bars, standard deviations, or multiple seeds. DRL training is notoriously noisy, and the observed differences (e.g., GTDD MRC 1.063 vs. RTOS 1.224) may not be statistically significant. The paper should report the mean and standard deviation over multiple independent runs, or at least provide learning curves for all runs that substantiate the claimed stability and convergence advantages.
minor comments (6)
- [§2.1] There is a typo: 'quey' should be 'query'.
- [§4] The word 'presentation' appears to be a typo for 'representation' in several places, including the list of components and the text describing state representation.
- [§8.1.2] The paper first states that 90% of queries are used for training and 10% for testing, but Section 8.2.1 describes an 11-fold cross-validation with template-based splits. The relationship between these two evaluation protocols should be clarified.
- [References [7]] Reference [7] states only that the code is 'available upon request.' A public repository would support reproducibility and allow reviewers to verify the experimental setup; 'available upon request' is not sufficient for a scientific publication.
- [§8.1.1] The paper does not specify many hyperparameters used for GTDD or the baselines, such as hidden size, learning rate, batch size, replay buffer size, target network update frequency, exploration schedule, and curriculum parameters (k, I). These details are essential for reproduction.
- [Figures] Several figures (especially Figure 3) are low-resolution and difficult to read; higher-quality versions should be provided.
Circularity Check
No significant circularity: GTDD's architecture and reward are not derived from the results they predict; the evaluation concerns are methodological, not self-referential.
full rationale
The paper's central claim is empirical: GTDD (GNN + Tree-LSTM + Dueling-DQN, curriculum learning, log-ratio reward) outperforms RTOS/JOGGER and approaches DP. The log-ratio reward in Eq. 5 uses DP feedback only as an external baseline; MRC/GMRL in Eqs. 6-7 also normalize by DP. This reward-metric alignment is a design choice, not circularity: the model's parameters are learned from DBMS feedback and are not defined in terms of the evaluation metric, and DP is not produced by the model. The sentence 'For the sake of fairness, all the related work employs the reward function we propose' (Section 8.2) is a legitimate methodological concern—it changes the baselines relative to their published versions and conflates reward design with architecture—but it does not reduce the claimed advantage to an identity or to a fitted parameter. The action mask (Section 7.3) restricting actions to non-Cartesian joins is a search-space restriction, not a circular step; it may exclude some valid plans in general, but for the connected query graphs used here it does not make the result an input. The self-reference [7] ('The link to the code is available upon request') is an artifact notice, not load-bearing evidence. No step in the derivation defines X in terms of Y, fits a parameter and then renames it a prediction, or imports a conclusion from the authors' prior work. Therefore no circularity is present.
Assumptions & free parameters
free parameters (9)
- hidden size hs
- node2vec return parameter p
- node2vec in-out parameter q
- number of walks N
- maximum walk length W
- curriculum partition count k =
3
- curriculum updating interval I
- discount factor gamma
- learning rate
assumptions (4)
- domain assumption Join order selection can be modeled as a Markov Decision Process with state as a join forest, action as joining two tables, and reward as a log-ratio against DP feedback.
- domain assumption The cost and latency feedback from PostgreSQL accurately reflects plan quality.
- domain assumption Focus on SPJ (Select-Project-Join) queries is sufficient for evaluating join order selection.
- domain assumption Dueling-DQN with the proposed reward function converges to a policy that generalizes across templates.
Cite this review
Pith. "Pith review of A Novel Framework Using Deep Reinforcement Learning for Join Order Selection." pith.science (2026). https://pith.science/paper/QDCDICWT
@misc{pith2026241210253,
author = {Pith},
title = {Pith review of: A Novel Framework Using Deep Reinforcement Learning for Join Order Selection},
year = {2026},
howpublished = {\url{https://pith.science/paper/QDCDICWT}},
note = {Machine review of arXiv:2412.10253}
}
read the original abstract
Join order selection is a sub-field of query optimization that aims to find the optimal join order for an SQL query with the minimum cost. The challenge lies in the exponentially growing search space as the number of tables increases, making exhaustive enumeration impractical. Traditional optimizers use static heuristics to prune the search space, but they often fail to adapt to changes or improve based on feedback from the DBMS. Recent research addresses these limitations with Deep Reinforcement Learning (DRL), allowing models to use feedback to dynamically search for better join orders and enhance performance over time. Existing research primarily focuses on capturing join order sequences and their representations at various levels, with limited comparative analysis of reinforcement learning methods. In this paper, we propose GTDD, a novel framework that integrates Graph Neural Networks (GNN), Treestructured Long Short-Term Memory (Tree LSTM), and DuelingDQN. We conduct a series of experiments that demonstrate a clear advantage of GTDD over state-of the-art techniques.
Figures
Figures from the paper (6 more)
Reference graph
Works this paper leans on
-
[7]
GTDD. 2024. The link to the code is available upon request
work page 2024
-
[1]
Richard Bellman. 1957. Dynamic Programming. Dover Publications
work page 1957
-
[2]
Yoshua Bengio, Aaron Courville, and Pascal Vincent. 2014. Representation Learning: A Review and New Perspectives. arXiv:1206.5538 [cs.LG] https: //arxiv.org/abs/1206.5538 A Novel Framework Using Deep Reinforcement Learning for Join Order Selection EDBT 25, March 25-28, 2025, Barcelona, Spain
arXiv 2014
-
[3]
Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston. 2009. Curriculum learning. In Proceedings of the 26th Annual International Conference on Machine Learning (Montreal, Quebec, Canada) (ICML ’09). Association for Computing Machinery, New York, NY, USA, 41–48. https://doi.org/10.1145/ 1553374.1553380
arXiv 2009
-
[4]
Kristin Bennett, Michael Ferris, and Yannis Ioannidis. 1970. A Genetic Algorithm for Database Query Optimization. (02 1970)
work page 1970
-
[5]
Jin Chen, Guanyu Ye, Yan Zhao, Shuncheng Liu, Liwei Deng, Xu Chen, Rui Zhou, and Kai Zheng. 2022. Efficient Join Order Selection Learning with Graph-based Representation. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (Washington DC, USA) (KDD ’22). Association for Computing Machinery, New York, NY, USA, 97–107. ht...
arXiv 2022
-
[6]
Aditya Grover and Jure Leskovec. 2016. node2vec: Scalable Feature Learning for Networks. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (San Francisco, California, USA) (KDD ’16). Association for Computing Machinery, New York, NY, USA, 855–864. https: //doi.org/10.1145/2939672.2939754
arXiv 2016
-
[8]
Shengyi Huang and Santiago Ontañón. 2022. A Closer Look at Invalid Action Masking in Policy Gradient Algorithms. The International FLAIRS Conference Proceedings 35 (May 2022). https://doi.org/10.32473/flairs.v35i.130584
Show all 25 references
-
[9]
Ioannidis and Younkyung Cha Kang
Yannis E. Ioannidis and Younkyung Cha Kang. 1991. Left-deep vs. bushy trees: an analysis of strategy spaces and its implications for query optimization. SIGMOD Rec. 20, 2 (apr 1991), 168–177. https://doi.org/10.1145/119995.115813
1991
-
[10]
Sanjay Krishnan, Zongheng Yang, Ken Goldberg, Joseph Hellerstein, and Ion Stoica. 2019. Learning to Optimize Join Queries With Deep Reinforcement Learning. arXiv:1808.03196 [cs.DB] https://arxiv.org/abs/1808.03196
2019 arXiv
-
[11]
Viktor Leis, Andrey Gubichev, Atanas Mirchev, Peter Boncz, Alfons Kemper, and Thomas Neumann. 2015. How good are query optimizers, really? Proc. VLDB Endow. 9, 3 (nov 2015), 204–215. https://doi.org/10.14778/2850583.2850594
2015
-
[12]
Ryan Marcus and Olga Papaemmanouil. 2018. Deep Reinforcement Learning for Join Order Enumeration. In Proceedings of the First International Workshop on Exploiting Artificial Intelligence Techniques for Data Management (Houston, TX, USA) (aiDM’18). Association for Computing Mac...
2018
-
[13]
Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg Corrado, and Jeffrey Dean. 2013. Distributed Representations of Words and Phrases and their Compositionality. arXiv:1310.4546 [cs.CL] https://arxiv.org/abs/1310.4546
2013 arXiv
-
[14]
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. 2013. Playing Atari with Deep Reinforcement Learning. arXiv:1312.5602 [cs.LG] https://arxiv.org/abs/1312.5602
2013 arXiv
-
[15]
Larriba-Pey
Victor Muntés-Mulero, Josep Aguilar-Saborit, Calisto Zuzarte, and Josep-L. Larriba-Pey. 2006. CGO: A Sound Genetic Optimizer for Cyclic Query Graphs. In Computational Science – ICCS 2006 , Vassil N. Alexandrov, Geert Dick van Albada, Peter M. A. Sloot, and Jack Dongarra (Eds.)...
2006
-
[16]
Meikel Poess and Chris Floyd. 2000. New TPC benchmarks for decision support and web commerce. SIGMOD Rec. 29, 4 (dec 2000), 64–71. https://doi.org/10. 1145/369275.369291
2000
-
[17]
PostgreSQL. 2024. http://www.postgresql.org/
2024
-
[18]
Yunsheng Shi, Zhengjie Huang, Shikun Feng, Hui Zhong, Wenjin Wang, and Yu Sun. 2021. Masked Label Prediction: Unified Message Passing Model for Semi-Supervised Classification. arXiv:2009.03509 [cs.LG] https://arxiv.org/abs/ 2009.03509
2021 arXiv
-
[19]
Michael Steinbrunn, Guido Moerkotte, and Alfons Kemper. 1999. Heuristic and Randomized Optimization for the Join Ordering Problem. VLDB Journal 6 (12 1999). https://doi.org/10.1007/s007780050040
1999 doi
-
[20]
Michael Stillger and Myra Spiliopoulou. 1996. Genetic programming in data- base query optimization. In Proceedings of the 1st Annual Conference on Genetic Programming (Stanford, California). MIT Press, Cambridge, MA, USA, 388–393
1996
-
[21]
Kai Sheng Tai, Richard Socher, and Christopher D. Manning. 2015. Improved Semantic Representations From Tree-Structured Long Short-Term Memory Net- works. arXiv:1503.00075 [cs.CL] https://arxiv.org/abs/1503.00075
2015 arXiv
-
[22]
Ziyu Wang, Tom Schaul, Matteo Hessel, Hado van Hasselt, Marc Lanctot, and Nando de Freitas. 2016. Dueling Network Architectures for Deep Reinforcement Learning. arXiv:1511.06581 [cs.LG] https://arxiv.org/abs/1511.06581
2016 arXiv
-
[23]
Christopher Watkins and Peter Dayan. 1992. Technical Note: Q-Learning. Ma- chine Learning 8 (05 1992), 279–292. https://doi.org/10.1007/BF00992698
1992 doi
-
[24]
Xiang Yu, Guoliang Li, Chengliang Chai, and Nan Tang. 2020. Reinforcement Learning with Tree-LSTM for Join Order Selection. In2020 IEEE 36th International Conference on Data Engineering (ICDE) . 1297–1308. https://doi.org/10.1109/ ICDE48307.2020.00116
2020
-
[25]
Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. 2021. Graph Neural Networks: A Review of Methods and Applications. arXiv:1812.08434 [cs.LG] https://arxiv. org/abs/1812.08434
2021 arXiv
Reviewed August 11, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.