Practical MCTS-based Query Optimization: A Reproducibility Study and new MCTS algorithm for complex queries

Alena Rybakina; Alexander Demin; Denis Ponomaryov; Konstantin Gilev; Sergey Kudashev; Vladimir Burlakov; Yuriy Dorn

Learned MCTS join optimizers fail out of sample; native-cost Extreme UCT wins on complex joins

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.5

2026-07-13 23:43 UTC pith:U42RL2IA

load-bearing objection Solid reproducibility hit on learned-cost MCTS plus a practical GEQO-seeded Extreme-UCT alternative that helps mainly on ≥12-table joins; the superiority claim is real but narrower than the abstract suggests. the 4 major comments →

arxiv 2603.16474 v2 pith:U42RL2IA submitted 2026-03-17 cs.DB

Practical MCTS-based Query Optimization: A Reproducibility Study and new MCTS algorithm for complex queries

Vladimir Burlakov , Alena Rybakina , Sergey Kudashev , Konstantin Gilev , Alexander Demin , Denis Ponomaryov , Yuriy Dorn This is my paper

classification cs.DB

keywords join order optimizationMonte Carlo Tree Searchquery optimizationreproducibilitycost modelsExtreme UCTPostgreSQLJOB benchmark

verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Recent Monte Carlo Tree Search methods for choosing join order in databases claim large gains, but they rely on machine-learned cost models. This paper shows those gains do not hold under diverse workloads: the MCTS search itself is useful, yet the learned models collapse on out-of-distribution queries. The authors replace the learned model with the database engine's ordinary internal cost estimator and add an Extreme UCT selection rule that chases the single best plan rather than the best average. Seeded by a cheap genetic plan and refined in two stages, the method beats both the original learned MCTS systems and PostgreSQL's own optimizer on queries that join twelve or more tables. Full code and artifacts are released so the result can be checked and extended.

Core claim

AlphaJoin and HyperQO do not deliver their claimed speed-ups once tested beyond the original training distribution; the failure is caused by learned cost models, not by Monte Carlo Tree Search. A practical MCTS that uses only the DBMS native cost model together with Extreme UCT selection, seeded from a genetic starting plan, produces better execution times than both those learned systems and the production optimizer on complex multi-join queries.

What carries the argument

Extreme UCT: instead of average reward, the selection score uses the maximum observed reward of a child plus an exploration term raised to a tunable power γ, steering search toward the global best plan under the database's own cost estimates.

Load-bearing premise

The database's built-in cost numbers, even when they mis-estimate intermediate sizes, still rank join orders well enough for Extreme-UCT search to find faster plans than the default optimizer.

What would settle it

On a new suite of multi-join queries where the native cost model is known to be anti-correlated with true latency, run the two-stage Extreme-UCT procedure; if the forced plans are systematically slower than GEQO or dynamic programming, the central claim is false.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

Learned cost models attached to MCTS cannot be trusted for production without continual retraining on every new workload shape.
For queries with twelve or more tables, seeding MCTS from a genetic plan and refining under native costs improves plan quality over pure dynamic programming or GEQO alone.
Out-of-sample suites such as JOB-Complex expose generalization failures that the original JOB benchmark alone conceals.
Releasing complete, executable code and avoiding learned components lowers the barrier to practical use of MCTS inside query optimizers.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same Extreme-UCT plus native-cost pattern can be ported to any engine that already exposes a cost model and join-order hints.
Strong search heuristics may compensate for noisy cost models, reducing pressure on perfect cardinality estimation for large joins.
Hybrid classical-plus-MCTS pipelines are likely more deployable in the near term than pure learned optimizers.
Replacing the native cost model with any better non-learned estimator should be a direct, testable next experiment.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Desk Editor's Note

Solid reproducibility hit on learned-cost MCTS plus a practical GEQO-seeded Extreme-UCT alternative that helps mainly on ≥12-table joins; the superiority claim is real but narrower than the abstract suggests.

read the letter

The useful core of this paper is the reproducibility work. They actually re-ran AlphaJoin and HyperQO, documented the missing weights, CUDA lock-in, alias hard-coding, and near-total fallback on JOB-Complex, and isolated the OOD failure of the learned cost models. That diagnosis is clean and worth having on the record.

What they build next is incremental but sensible: two-stage left-deep MCTS that seeds from GEQO prefixes, uses PostgreSQL’s own EXPLAIN cost as the reward, and swaps in Extreme UCT (max reward + powered exploration term) instead of mean UCT. Code and artifacts are released. On the ≥12-relation slice of JOB and on JOB-Complex the method improves execution time relative to default PostgreSQL and the re-implemented learned baselines. That is a real, if modest, engineering result for the regime where commercial optimizers already abandon DP.

The soft spots are proportional, not fatal. Absolute results on full JOB are mixed (plenty of “worse” or “same”). Everything runs outside the kernel via leading hints, so planning overhead is invisible and E2E numbers are missing. The load-bearing assumption—that native cost remains correlated enough with latency for Extreme UCT to prefer better plans—is acknowledged by the authors themselves when they blame rare degradations on cost-model error, yet they never report the rank correlation on the exact subset they claim. Free parameters (iteration budgets, γ, mutation rates) exist but are not the main story. Extreme UCT itself is taken from Huang et al.; the novelty is the combination and the negative result on learned models.

This is for people who care about practical join-order search and about whether learned optimizers actually ship. It is not a conceptual breakthrough, but it is honest systems work with released code. I would send it to referees; the community needs more of these careful negative-plus-fix papers. Worth reading if you work on optimizers; skip if you only care about new theory.

Referee Report

4 major / 5 minor

Summary. The paper performs a reproducibility study of AlphaJoin and HyperQO (MCTS-based join-order optimizers that rely on learned cost models), finding that claimed gains on JOB do not reliably hold and that both methods fail to improve (or even run) on the OOD JOB-Complex benchmark; the authors attribute this to severe out-of-distribution errors in the learned models rather than to MCTS itself. They then introduce a two-stage, prefix-guided MCTS algorithm (Algorithm 1) that replaces the learned model with PostgreSQL’s native cost model as reward R(e) ← −Cost(e), adopts Extreme UCT selection (Eq. 3), and seeds search from GEQO-style prefixes. Experiments on JOB and JOB-Complex claim that the method outperforms the re-implemented learned baselines and improves upon PostgreSQL for queries with ≥12 relations, with full code and artifacts released.

Significance. A careful negative result on the deployment readiness of learned-cost MCTS optimizers, together with a fully reproducible hybrid that stays inside the native cost model, would be useful to the LQO community. The use of JOB-Complex as an explicit OOD test, the public artifacts, and the isolation of the search component from the learned estimator are genuine strengths. If the superiority claim for complex joins holds under tighter evaluation, the work supplies a practical, low-overhead alternative to both pure DP/GEQO and brittle learned methods.

major comments (4)

[§6.2, Figs. 2 and 4] §6.2 and Figs. 2/4: The abstract and conclusion claim “superiority over a SOTA query optimizer in complex join scenarios.” On the full JOB distribution (Fig. 2) the method is better on only 44.2 % of queries and worse on another 44.2 %. Gains appear concentrated on the ≥12-relation subset (Fig. 4), yet even there the relative-gap plot shows mixed signs and several large degradations. Without win-rate statistics, confidence intervals, or a clear statement that the claim is restricted to the ≥12 subset under a GEQO-style threshold, the superiority language overstates the evidence.
[Algorithm 1, Eq. (3), §5] Algorithm 1 and Eq. (3): The entire search is driven by the proxy R(e) ← −Cost(e) taken from PostgreSQL EXPLAIN. The paper itself notes that rare degradations are caused by cost-model error (§6.2) and that classical cardinality/correlation assumptions are known to be inaccurate (§2.2). No rank-correlation (Spearman/Kendall) between Cost(e) and true latency is reported on the exact plans explored for the ≥12-relation queries, nor is there an ablation that replaces Extreme-UCT with standard UCT or with random search under the same iteration budget. Without that measurement the claim that Extreme-UCT systematically improves true runtime (rather than merely lowering estimated cost) remains an untested hinge.
[§6.1, §7] §6.1 and §7: All evaluated methods, including the proposed one, run outside the kernel and inject leading hints. Consequently the reported latencies exclude MCTS search cost (T_pair + T_main iterations, each requiring an EXPLAIN). The authors acknowledge that E2E time cannot be measured consistently. For complex queries this overhead can dominate; the practicality claim relative to in-kernel GEQO therefore needs either an in-kernel prototype or an explicit accounting of planning time under realistic budgets.
[§3–4, abstract] §3–4 and the ablation claim: The abstract states that “while the MCTS search strategy is effective, the accompanying learned cost models suffer from severe out-of-distribution generalization errors.” The reproducibility experiments show that AlphaJoin and HyperQO fail, but they do not isolate the contribution of Extreme-UCT versus the native cost model versus the two-stage GEQO seeding. An explicit ablation (standard UCT vs. Extreme UCT, pure GEQO vs. GEQO-seeded MCTS, identical iteration budgets) is needed before the effectiveness of the search component can be asserted independently of the cost model.

minor comments (5)

[title page] Title and running headers lack spaces (“PRACTICALMCTS-BASEDQUERYOPTIMIZATION”); fix for readability.
[§5–6] Hyper-parameter values actually used for c, γ, T_pair, T_main, gp_rate, mutation_rate, etc. are never listed; only that they were “possibly tuned.” A table or appendix entry is required for reproducibility.
[Fig. 4] Fig. 4 y-axis label and caption use the abbreviation “AJ” without definition in the figure itself; expand or add a legend.
[§5, references] Citation for Extreme UCT (Huang et al.) appears only as “[n. d.]”; supply the full venue and year once available.
[§4] Several sentences in §4.1–4.2 mix past-tense reproduction narrative with present-tense claims; a light copy-edit would improve clarity.

Circularity Check

0 steps flagged

No circularity; empirical MCTS heuristic using native DBMS cost model is evaluated on external public benchmarks against reimplemented baselines.

full rationale

The paper's load-bearing claims are empirical: a two-stage prefix-guided MCTS (Algorithm 1) that seeds from GEQO edges, uses reward R(e) ← −Cost(e) from PostgreSQL EXPLAIN, and selects via Extreme UCT (Eq. 3) outperforms reimplemented AlphaJoin/HyperQO and native DP/GEQO on JOB/JOB-Complex execution latencies for ≥12-relation queries. Extreme UCT is adopted from Huang et al. as a known selection policy (not derived from the measured latencies). There is no parameter fitted to a data subset and then re-presented as a prediction, no self-definitional identity between inputs and claimed outputs, no uniqueness theorem imported from overlapping authors, and no ansatz smuggled via self-citation. The reproducibility critique of prior learned models and the new algorithm's results rest on independent runs against public benchmarks and the DBMS's own cost model; the derivation chain is therefore self-contained algorithmic proposal plus external evaluation.

Axiom & Free-Parameter Ledger

3 free parameters · 3 axioms · 1 invented entities

The central empirical claim rests on a small set of search hyper-parameters, the assumption that PostgreSQL’s cost model is a usable reward, and the standard combinatorial model of left-deep join trees. No new physical entities are postulated; Extreme UCT is imported.

free parameters (3)

T_pair / T_main (iteration budgets)
Number of MCTS iterations in the two stages; chosen by the authors and directly control search effort and reported quality.
c, γ (Extreme-UCT constants)
Exploration coefficient and exponent in Eq. (3); free knobs that trade exploration vs. exploitation of the best observed plan.
gp_rate, mutation_rate, exploration_rate, K
Evolutionary-operator rates inherited from the MCTS-4-SR base; affect how the search jumps in plan space.

axioms (3)

domain assumption PostgreSQL’s EXPLAIN total cost is a sufficiently informative reward for ranking join orders (R(e) ← −Cost(e))
Stated in Algorithm 1 and used throughout; known to be imperfect yet treated as the sole guidance signal.
domain assumption Left-deep join trees plus leading hints are an adequate search space for the evaluated workloads
Implicit in the algorithm design and the use of pg_hint_plan; bushy plans are not explored.
standard math Standard MCTS four-phase loop and UCT-style selection are valid for combinatorial plan spaces
Background from Chang et al. and Silver et al.; not re-proved.

invented entities (1)

Two-stage prefix-guided Extreme-UCT MCTS for left-deep joins independent evidence
purpose: Practical search procedure that seeds from GEQO and refines with Extreme UCT under the native cost model
The concrete algorithm (Alg. 1) is new engineering; Extreme UCT itself is cited from Huang et al., so the entity is the combination rather than a new mathematical object.

pith-pipeline@v1.1.0-grok45 · 18392 in / 2603 out tokens · 36781 ms · 2026-07-13T23:43:43.593684+00:00 · methodology

0 comments

read the original abstract

Monte Carlo Tree Search (MCTS) has been proposed as a transformative approach to join-order optimization in database query processing, with recent frameworks such as AlphaJoin and HyperQO claiming to outperform traditional methods. However, the fact that these frameworks rely on learned cost models raises concerns related to generalizability and deployment readiness. This paper presents a comprehensive reproducibility study of these methods, revealing that they often fail to support the claimed performance gains when subjected to diverse workloads. Through an ablation study, we diagnose the root cause of this instability: while the MCTS search strategy is effective, the accompanying learned cost models suffer from severe out-of-distribution generalization errors. Addressing this, we propose a novel MCTS framework. Unlike prior methods that rely on unstable learned components, our approach utilizes the database standard internal cost model, augmented by a new Extreme UCT (Upper Confidence Bound applied to Trees) selection policy to navigate the search space more robustly. We benchmark our method against the original AlphaJoin and HyperQO, as well as industry-standard baselines including Dynamic Programming (DP) and Genetic Query Optimization (GEQO), using the well-known Join Order Benchmark (JOB) and the new JOB-Complex benchmark. The results demonstrate that our approach outperforms learned MCTS methods and achieves superiority over a SOTA query optimizer in complex join scenarios on real-world data. We release the full implementation and experimental artifacts to support further research.

Practical MCTS-based Query Optimization: A Reproducibility Study and new MCTS algorithm for complex queries

Core claim

What carries the argument

Load-bearing premise

What would settle it

If this is right

Where Pith is reading between the lines

discussion (0)