WorksComputer Science
Probe-Based Routing for Join Optimizer Selection
Abstract
In optimizers that choose a join-order solver by a size rule, join ordering is an algorithm-selection problem, because dynamic programming (DP), genetic search (GEQO), and Monte Carlo tree search (MCTS) each win on different queries. PostgreSQL nevertheless chooses among them by relation count alone, although queries with the same relation count can favor different solvers. This paper introduces two landscape features that a probe computes from random join orders in microseconds per query. The tail spacing describes how the costs of the best sampled orders are spaced, and the crossover surprise describes how far the cost of a crossover child deviates from the mean cost of its parents. The router clusters training queries by these features and the relation count, assigns a solver to every cluster that this solver wins in total end-to-end time by a margin, and leaves all other queries to PostgreSQL's default rule. On JOB and IMDb-CEB, the router lowers mean end-to-end time relative to the default rule, and on IMDb-CEB the probe features nearly double the gain obtained from the relation count alone, so they carry information about the queries that the relation count lacks.
Introduction
A query optimizer with several join-order solvers must decide which of them receives a query before join enumeration begins. PostgreSQL makes this decision with its GEQO threshold. By default, queries with fewer than 12 relations go to dynamic programming (DP) and larger ones to the genetic optimizer GEQO [1]. The rule is free to evaluate, but it sees nothing of a query except its relation count.
The choice matters for end-to-end time, which includes both planning and execution. On JOB, JOB-Complex, and IMDb-CEB, each of DP, GEQO, and the Monte Carlo tree search (MCTS) solver of [2] is the fastest on roughly a quarter to a half of the queries (Table 2). Even PostgreSQL’s two native solvers split JOB almost evenly, with DP ahead of GEQO on 60 of 113 queries. Because one slow choice on an expensive query can outweigh many correct choices on cheap ones, a router has to be judged by total end-to-end time rather than by the share of queries it routes correctly.
| Workload | Winners | DP (s) | GEQO (s) | MCTS (s) | Default (s) | Oracle (s) |
| JOB | 38/29/46 | 4041.00 | 3944.92 | 3534.52 | 4061.79 | 3311.15 |
| JOB-Complex | 7/9/13 | 2053.51 | 1935.56 | 1787.24 | 1874.02 | 1600.68 |
| IMDb-CEB | 52/57/91 | 8378.48 | 7632.37 | 7030.49 | 8009.86 | 6463.76 |
Table 2. Total end-to-end time per workload in seconds. Winners counts the queries on which DP, GEQO, and MCTS are fastest.
Existing systems make this choice in one of two ways. Deployed optimizers apply size rules, as PostgreSQL does with its GEQO threshold, Spark SQL with a relation-count limit on DP join reordering, and Umbra with its switch among Phyp, linearized DP, and greedy search [3]. Learned selectors predict the choice from query features instead. AlphaJoin 2.0 learns a per-query choice between a learned MCTS solver and PostgreSQL’s optimizer [4], and SATzilla-style portfolios predict the runtime of each solver and run the fastest one [5].
Size rules cannot separate queries of equal size. JOB queries 28a and 33c both join 14 relations, so PostgreSQL sends both to GEQO, yet GEQO is the slowest solver on 28a and beats DP on 33c (§ 3.2). Join-graph features do not resolve such cases either, because they describe the shape of the graph and not how plan costs are distributed over join orders, which is what governs the behavior of randomized solvers such as GEQO and MCTS.
The router proposed here uses two features of that distribution (Figure 1). A probe scores random left-deep join orders with an estimated cost and derives the tail spacing and the crossover surprise from these scores in at most 0.06 ms per query (§ 3.2). Offline, the router clusters the training queries of a workload by these features and the relation count. A cluster that one solver wins in total end-to-end time by a margin, and that spans enough query templates, is dominant and stores this solver, while all other clusters are mixed. Online, a shallow tree maps an incoming query to a cluster, and the query either runs with the solver of its dominant cluster or keeps PostgreSQL’s default rule. Queries of the second kind are planned exactly as in stock PostgreSQL, so every difference from the default comes from the solvers that dominant clusters store.

Figure 1. The router. Offline, each workload receives its own scaling, clusters, dominance labels, and tree. Online, a query in a dominant cluster runs with the cluster winner, and every other query keeps PostgreSQL’s default rule.
The evaluation replays recorded end-to-end times on 50 random 80/20 splits of each workload, with one router configuration that is chosen on JOB and reused unchanged on all three workloads. The router lowers mean end-to-end time relative to the default rule by 12.3% on JOB and 8.5% on IMDb-CEB (Table 3), and on IMDb-CEB the probe features nearly double the gain obtained from the relation count alone (Table 5). On JOB-Complex, whose 29 queries are hand-crafted hard cases, the router stays within 3% of the default. Simple policies on the same splits, such as always running MCTS or a learned relation-count threshold between DP and MCTS, show how much of the gain comes from the larger portfolio and how much from routing (Table 4).
| Workload | Default (s) | Router (s) | Mean | P90 | P95 | Near oracle | Fallback |
| JOB | 837.18 | 737.51 | 12.26% | 27.89% | 44.73% | 59.48%→66.43% | 1 of 23 |
| JOB-Complex | 423.00 | 426.32 | −2.81% | 18.21% | 23.70% | 63.00%→63.67% | 0 of 6 |
| IMDb-CEB | 1659.23 | 1511.31 | 8.53% | 27.88% | 43.09% | 56.55%→57.40% | 2 of 40 |
Table 3. Router against PostgreSQL’s default rule over 50 random 80/20 splits, with held-out times in seconds and metrics as defined in § 4.3. Near oracle is given first for the default rule and then for the router.
| Policy | JOB | JOB-Complex | IMDb-CEB |
| Default rule | 0.00% | 0.00% | 0.00% |
| DP, GEQO, and MCTS | |||
| Always-MCTS | 12.12% | −1.06% | 11.33% |
| Learned DP/MCTS threshold | 10.83% | 0.91% | 11.98% |
| Router | 12.26% | −2.81% | 8.53% |
| DP and GEQO only | |||
| Always-DP | 0.59% | −15.11% | −5.70% |
| Always-GEQO | 4.15% | −2.67% | 4.86% |
| Learned DP/GEQO threshold | 3.93% | −0.76% | 4.20% |
| Router | 3.02% | −7.72% | 3.94% |
| Oracles, DP, GEQO, and MCTS | |||
| Per-count oracle | 17.10% | 11.51% | 15.17% |
| Per-query oracle | 18.61% | 12.35% | 18.97% |
Table 4. Mean reduction of held-out time relative to PostgreSQL’s default rule on the same 50 splits. Negative values are increases.
Table 5: IMDb-CEB feature ablation with DP, GEQO, and MCTS. Reduction of held-out time relative to the default rule over 50 splits (§ 4.3).
| Features | Router (s) | Mean | Min | P5 | P95 | Max |
| Default rule | 1659.23 | 0.00% | 0.00% | 0.00% | 0.00% | 0.00% |
| 1476.19 | 10.74% | −3.38% | 1.38% | 19.17% | 20.80% | |
| 1472.45 | 10.95% | −3.38% | 2.79% | 18.23% | 21.24% | |
| 1454.73 | 12.01% | −3.38% | 1.23% | 21.59% | 23.61% | |
| 1542.72 | 6.76% | −3.38% | −1.85% | 14.44% | 16.26% | |
| 1511.31 | 8.53% | −3.30% | −0.73% | 19.80% | 22.17% | |
| 1481.28 | 10.55% | 0.49% | 3.23% | 18.93% | 23.20% | |
| 1451.22 | 12.24% | −3.38% | 3.29% | 21.28% | 23.27% |
Table 5.
The paper makes four contributions.
Two landscape features for solver selection, the tail spacing and the crossover surprise, which a probe computes in at most 0.06 ms per query.
A router that assigns a solver only to dominant clusters of these features and leaves all other queries to PostgreSQL’s default rule.
An evaluation on JOB, JOB-Complex, and IMDb-CEB in which the router and simple baseline policies share the same splits, which separates the effect of adding MCTS, of moving the relation-count threshold, and of choosing the solver per query.
A feature ablation on IMDb-CEB with and without MCTS in the portfolio.
Related Work
Join-Order Search and Learned Optimization
System R introduced cost-based DP for left-deep join orders, and Volcano and Cascades organized optimizer search around extensible rules [6, 7, 8]. Later DP algorithms exploit join-graph connectivity and hypergraph structure to enumerate bushy plans [9, 10], while randomized search, iterative DP, query simplification, and adaptive linearization give up completeness in order to bound planning effort on large joins [3, 11, 12, 13]. All of these methods change how a single solver searches, whereas this paper asks which solver should receive a query.
Learned optimizers widen the set of actions available to the optimizer. ReJOIN, Neo, and Balsa learn to construct join orders or plans [14, 15, 16], whereas Bao, FASTgres, AutoSteer, and Lero keep the native optimizer and learn hint selection or plan preference [17, 18, 19, 20]. Kepler generates a plan set offline and uses uncertainty-aware prediction to avoid regressions, and GenJoin predicts how to transform an input set of subplan hints [21, 22]. Because these systems choose plans, preferences, or hints after the solver has been chosen, they can run on top of whichever solver the router selects.
AlphaJoin uses learned MCTS for join ordering, and HybridQO uses MCTS inside a pipeline that generates and selects candidate plans [4, 23]. Its successor AlphaJoin 2.0 learns for each query whether its MCTS solver or PostgreSQL’s optimizer should plan the query [4]. The router described here chooses among three solvers instead of two and decides per cluster of queries rather than per query. It assigns a solver to a cluster only after the dominance test of § 3.3 and leaves the queries of all other clusters to PostgreSQL’s choice.
Offline Optimization and Robustness
Offline learned optimization moves expensive exploration out of query planning. QO-Advisor, AutoSteer, and Kepler execute alternative plans offline and keep the plan changes they have verified [19, 21, 24]. BayesQO searches plans by Bayesian optimization with execution as an offline step, and LimeQO models the matrix of query and hint latencies as low rank in order to choose which entries to measure [25, 26]. Both target recurring analytic workloads, in which the offline work is spread over many executions. The router also executes alternatives offline, but it stores a rule for choosing a solver instead of verified plans, so every new query is planned from scratch without a plan tested offline.
Cost and cardinality estimates do not reliably predict the quality of the plan that an optimizer finally selects [27], and Izenov et al. show that Q-error is a weak indicator of plan suboptimality, proposing a classifier based on L1 error instead [28]. The evaluation in this paper therefore relies on measured end-to-end times rather than on estimated costs. ROME executes complementary plans in parallel and returns the first result [29], whereas the router runs a single solver per query, so a wrong choice costs its full end-to-end time.
Algorithm Selection and Portfolios
Per-instance algorithm selection maps instance features to a solver under an application-specific cost [30], and algorithm portfolios exploit solvers that win on different instances [31]. SATzilla made feature cost, timeouts, and cost-sensitive selection explicit, and later variants are covered by surveys [5, 32]. Solver selection in a database shares this asymmetry, in which one slow choice can account for a large share of workload time even when most choices are correct.
Several portfolio methods contain parts of the router. ISAC clusters instances and assigns a configuration to each cluster [33], exploratory landscape analysis combines sampled instance features with cost-sensitive learning [34], and cost-sensitive hierarchical clustering forms regions with a common solver [35]. Hydra constructs complementary solver configurations, confidence-aware recourse falls back to a default solver, and AutoFolio constructs the selector itself [36, 37, 38]. Clustering, cost-sensitive assignment, and fallback are thus well established, and what is new here is their use for join-order solver selection, with features computed during planning, end-to-end time as the loss, a separate model for each workload, and PostgreSQL’s default rule as the fallback.
Query Regions, Plan Reuse, and Adaptivity
Parametric query optimization partitions the parameter space into regions in which different plans are best [39, 40]. Parametric plan caching clusters parameter bindings that can share a plan, and PLASTIC clusters past queries and classifies new ones for plan reuse [41, 42]. RankPQO ranks a compact plan cache, Plan Stitch combines subplans observed in earlier executions, and PLARQ retrieves and ranks candidates from a precomputed pool [43, 44, 45]. These methods select or build a plan, usually for recurring instances of a parameterized template, whereas the clusters of the router group queries that share a fastest solver. The chosen solver still plans every query from scratch, and the router does not need to know the template of a query online.
Adaptive query processing acts after optimization has begun. Eddies route tuples continuously, progressive optimization triggers reoptimization at checkpoints, and SkinnerDB learns join orders from execution progress [46, 47, 48]. The router, in contrast, makes a single decision before join enumeration and leaves both the chosen solver and the executor unchanged.
Router Design
Solvers and Default Rule
The router chooses among three solvers, , which trade planning effort against plan quality in different ways. DP enumerates the configured plan space, so its planning effort grows quickly with the number of relations [6, 10], whereas GEQO bounds this effort by randomized genetic search [11, 49] and MCTS searches partial join orders with tree exploration and cost-guided rollouts [2, 50]. For query and solver , the router optimizes the end-to-end time
which includes planning because a solver that finds a slightly faster plan can spend more time in planning than it saves in execution.
Stock PostgreSQL chooses between DP and GEQO by relation count alone. With the number of base relations that enter join enumeration for query , GEQO enabled, and geqo_threshold at its default of 12, it uses
This default rule is both the baseline of the evaluation and the fallback of the router.
Probe Features
Features for this decision have to be computed during planning, before any solver runs, and have to describe how plan costs are distributed over join orders rather than how the join graph looks. The probe obtains such features by scoring a few random left-deep join orders, which yields the probe features
For a random permutation of the relations, let be the optimizer’s cardinality estimate of base relation and the number of join-graph edges among the first relations. With the selectivity fixed at , the score of the order is
The score is the classical cost, the sum of estimated intermediate result sizes along the order, computed in log space from base cardinalities and a single fixed selectivity. Working in log space avoids overflow on large joins and makes scores comparable across queries.
The tail spacing summarizes the low end of the sampled cost distribution, where the competitive orders lie. The probe draws random orders within a time cap and sorts their scores as . With and , the tail spacing is
a Hill-style statistic of the spacing among the lowest sampled scores, measured from the sample minimum. Before scaling, the router replaces by to reduce its range, which yields the model vector
The crossover surprise asks whether recombining two sampled orders yields an order of predictable cost, which is the step GEQO relies on. The probe draws pairs of parents from the sampled orders and produces one child per pair with edge-recombination crossover (ERX), which builds a child order from adjacencies of both parents and is the recombination operator of PostgreSQL’s GEQO [1]. The surprise of child and the crossover surprise are
where is the sample variance of the scores of the sampled orders and the sample variance of the surprises. As a variance ratio, the crossover surprise ranges from zero upward and can exceed one. Its error decreases as , so gives an error of order at a probe cost that is linear in , and is sized to supply about orders for the parent pool and the variance .
The three features relate to different solvers. The relation count sets the size of the search space and thus the planning time of DP. The tail spacing indicates how close the best sampled orders lie to the minimum. A small value means that many sampled orders lie near the best observed cost, so random sampling has many chances to find a competitive order, whereas a large value means that such orders are rare. The crossover surprise indicates whether recombination preserves useful structure. A small value means that children cost about as much as their parents on average, as expected when the orders share reusable adjacencies, whereas a large value means that join decisions interact, so that good parents can produce poor children.
JOB queries 28a and 33c both join 14 relations, but 28a has a crossover surprise of 3.55, about twice the 1.79 of 33c. GEQO needs 18.1 s on 28a, where DP needs 10.2 s, but only 0.99 s on 33c, where DP needs 1.34 s. GEQO is thus the slowest solver on the query with the higher crossover surprise, a difference that the identical relation counts cannot reveal.
Clusters and Dominance
Assigning one solver to a group of queries is safe only if that solver wins on the group as a whole and the group does not consist of variants of a single template. The first offline layer therefore clusters the training queries of each workload and accepts a cluster winner only under both conditions. It uses the training queries with complete probe features and a configured subset of the model vector , which in the configuration of § 5.2 consists of and . Coordinates with zero variance in training are dropped, and the remaining ones are scaled either by the training mean and standard deviation or, for robust scaling, by the median and the interquartile range. -means with squared Euclidean distance, a fixed seed, and 20 initializations then assigns each training query to a cluster .
For cluster and solver , let denote the total end-to-end time of solver in the cluster, let be the solver with the lowest total, and let be the second lowest total. The cluster is dominant when
and mixed otherwise. The margin is a hyperparameter, and the support counts distinct template groups (§ 4.2), with a threshold of five for JOB and JOB-Complex and three for IMDb-CEB. Exact ties are resolved in the order DP, GEQO, MCTS. A dominant cluster stores as its cluster winner.
Cluster Classifier
Online, a query has to be mapped to its cluster with a few comparisons, and a wrong mapping costs nothing when it leaves the solver unchanged but can cost orders of magnitude when it does not. The second offline layer is therefore a shallow tree that predicts the cluster from the scaled probe features and is trained on a loss in end-to-end time rather than on cluster labels. The action of a cluster is its winner if the cluster is dominant and otherwise. For training query and candidate cluster , the loss is the increase in end-to-end time when the query receives the action of cluster instead of the action of its own cluster . A decrease counts as zero, so this positive-excess loss ignores gains from a wrong prediction. Each leaf receives the cluster with the lowest summed loss. The tree tests at most eight rank-spaced split points per feature and keeps at least of the training queries in every leaf. Remaining ties are resolved first by the number of cluster errors and then by the cluster ID.
Decision for an Incoming Query
The router acts once per query, after the optimizer has estimated the cardinalities of the base relations and before join enumeration starts, so the chosen solver plans the query as usual. It computes the probe features of an incoming query from the optimizer’s cardinality estimates and the join graph, applies the stored scaling, and evaluates the tree, which returns a cluster . The router then chooses the solver
where is the winner of cluster from Equation (7), and a query without probe features also receives . The model stored for a workload consists of the scaling parameters, the tree, and the winner or mixed label of every cluster. A deployment configures one such model per workload, and without the router PostgreSQL behaves exactly as .
Experimental Methodology
Hardware and Workloads
All measurements ran on a compute node with an AMD EPYC 9654 (Zen 4) processor providing 96 vCPUs at 2.4 GHz and 192 GB of RAM, running Ubuntu 24.04 LTS and PostgreSQL built from its master branch (version 19devel, February 2026).
The workloads combine a standard benchmark, a set of hard queries, and a generated workload with many variants per template. JOB is the 113-query Join Order Benchmark over IMDb [27], and JOB-Complex contains queries with more complex structure [51], of which one of 30 is excluded because both MCTS and PostgreSQL with GEQO exceeded the three-minute timeout on it. IMDb-CEB comes from the IMDb workload of the Cardinality Estimation Benchmark [52], and the evaluation uses 200 of its queries with at least nine relations, sampled in nearly equal numbers from 14 templates. The three workloads, whose sizes are listed in Table 1, are separate query distributions, each with its own model.
| Workload | Queries | Groups | Solver runs |
| JOB | 113 | 33 | 1,017 |
| JOB-Complex | 29 | 29 | 261 |
| IMDb-CEB | 200 | 14 | 1,800 |
| Total | 342 | 76 | 3,078 |
Table 1. Workloads in the evaluation. Groups are template groups, and solver runs count three solvers and three repetitions per query.
To reduce timing noise, the end-to-end time of each query and solver is the median of three measurements. The MCTS solver uses the negative-log reward, a tree depth of 10 before a rollout is forced, 10 best-plan replay candidates per restart phase, and 480 iterations in the first of its Luby restart phases [2]. Each query record also contains , , , and the probe time, the latter taken from runs separate from the solver runs.
Repeated Random Splits
Because every solver has been measured on every query, policies can be compared by replaying recorded end-to-end times instead of running them again. The evaluation does so over 50 random splits per workload, with split seeds from 1 to 50. Each split holds out a random 20% of the queries, fits the scaling, the clusters, the cluster winners, the dominance labels, and the tree on the remaining 80%, and then routes the held-out queries. Template groups enter only the support count of the dominance test. A template group is the set of letter variants of a JOB template, such as 28a, 28b, and 28c, the set of hashed variants of an IMDb-CEB template, or a single JOB-Complex query.
The router configuration is chosen once on JOB by a grid search over 20 random splits (§ 5.2) and applied unchanged to all three workloads.
Simple policies show how much of the gain a choice without probe features already achieves, and they run on the same 50 splits (Table 4). Always-DP, always-GEQO, and always-MCTS run a single solver on every query. A learned threshold runs DP below a relation count and another solver at or above, with chosen on the training queries of each split. The learned DP/MCTS threshold
chooses from 8 to 12, and the learned DP/GEQO threshold chooses it from 0 to 20. Two oracles use the held-out times, the per-count oracle choosing the fastest solver for each relation count and the per-query oracle the fastest solver for each query. They bound what a choice by relation count and a choice per query can achieve.
Metrics
The metrics charge the router for everything it adds to a query. The router time of a query is its end-to-end time with the chosen solver plus its probe time if the query passed through the tree, while the default rule incurs no probe time. Classifier time was not measured and is set to zero. The held-out time of a policy is the total router time, or end-to-end time for the baselines, over the held-out queries of a split, and its reduction is the fraction by which it falls below the held-out time of the default rule, so a negative reduction is an increase. Reported reductions are means over the 50 splits. For the comparison with the default rule (Table 3), three more quantities are averaged over the splits. They are the 90th and 95th percentiles of the per-query reduction (P90 and P95), the near-oracle share of held-out queries whose time is within 5% of the oracle time , and the number of held-out queries that fall back to the default rule. For the feature ablation, the spread of the reduction over the 50 splits is summarized by its minimum, 5th and 95th percentiles (P5 and P95), and maximum.
Results
Room for Choosing the Solver
A router can gain only if the solvers win on different queries and a choice per query beats the best single solver, and both hold on all three workloads (Table 2). Every solver wins some queries of every workload, and no single solver comes close to the per-query oracle. Always-MCTS is the best single policy on all three workloads and saves between 5% and 13% of the default total, yet the per-query oracle is another 6% to 10% faster. In the native portfolio the oracle likewise stays five to six percentage points below the better of DP and GEQO, so choosing the solver per query has room in both portfolios.
For the probe features to support such a choice, queries with the same fastest solver should lie close together in the feature space. In Figure 2, the probe features of each workload are projected to two dimensions with UMAP, and each query is colored by its fastest solver. The queries of JOB and IMDb-CEB form compact groups, whereas the 29 JOB-Complex queries spread out. Within a group the fastest solver often varies, which is why the router assigns a solver only to clusters whose winner leads in total end-to-end time and leaves the other clusters to the default rule.
Figure 2. UMAP projection of the probe features of each workload to two dimensions, with colors showing the fastest solver of each query.
Router Against the Default Rule
All results use a single router configuration, found by a grid search on JOB over 20 random 80/20 splits. The grid covers from 3 to 5 clusters, standard and robust scaling, tree depths 2 and 3, dominance margins of 0, 0.05, and 0.1, and the two feature sets and . The configuration with the highest mean reduction on the held-out queries, which is applied unchanged to all three workloads, has , robust scaling, the features and , the margin , and a tree of depth 2.
Against the default rule, the router lowers mean held-out time on JOB and IMDb-CEB (Table 3). On JOB-Complex the mean held-out time rises although the upper percentiles of the per-query reduction are positive, so a few expensive regressions outweigh many smaller gains. The share of queries within 5% of the oracle grows by about seven percentage points on JOB and by less than one point elsewhere, and only a few held-out queries per split fall back to the default rule. All router times include the probe, which takes a median of about and at most per query, or at most 5 ms per workload.
Part of this gain could also come from a better fixed policy, such as running MCTS everywhere. The router is therefore compared with the baseline policies on the same splits (Table 4). On JOB, the router reaches the gain of always-MCTS, the best single solver there, without being told in advance which solver is best, since its cluster winners come from the training queries. On IMDb-CEB, the learned DP/MCTS threshold and always-MCTS lead the router by about three percentage points, and with DP and GEQO only, always-GEQO leads it on all three workloads. On JOB-Complex, only the learned DP/MCTS threshold avoids a regression. No evaluated policy is best on all three workloads, so even a fixed policy has to be chosen per workload, and the router makes this choice from the training queries. The per-query oracle reaches about 19% on JOB and IMDb-CEB, above every evaluated policy.
Contribution of Each Feature
To measure how much each probe feature contributes, the router configuration is kept fixed and only the feature set is varied on IMDb-CEB (Tables 5 and 6). With MCTS in the portfolio, every feature set lowers mean held-out time, and either probe feature alone already outperforms the relation count alone, at about 11% against 7%. The full set of three features gives the largest mean reduction, 12.2%. The probe features thus carry information about IMDb-CEB queries that the relation count lacks, and combining the tail spacing with the crossover surprise gives more than either alone. The configuration chosen on JOB uses only the relation count and the tail spacing and reaches 8.5% here, so choosing the feature set per workload could raise the gain of the router further. The relation count alone and the relation count with the tail spacing still raise held-out time on at least 5% of the splits.
Without MCTS, the router chooses only between DP and GEQO, and the mean reductions shrink to between 2.5% and 4.1%. The crossover surprise alone does best in this portfolio, as expected for a feature that measures how well the recombination step of GEQO works on a query (Section 3.2). Every feature set raises held-out time on at least 5% of the splits, so with the native portfolio the gain of the router is smaller and varies more between splits than with MCTS.
Reproducibility
The router code, the recorded measurements, the grid search of § 5.2, and the scripts that produce Table 1, Table 2, Table 3, Table 5, and Table 6 are available at https://anonymous.4open.science/r/qorouter-anon.
Table 6: IMDb-CEB feature ablation with DP and GEQO only, with columns as in Table 5.
| Features | Router (s) | Mean | Min | P5 | P95 | Max |
| Default rule | 1659.23 | 0.00% | 0.00% | 0.00% | 0.00% | 0.00% |
| 1608.50 | 2.86% | −7.29% | −4.65% | 9.69% | 15.18% | |
| 1589.08 | 4.08% | −5.45% | −2.54% | 14.03% | 16.73% | |
| 1613.27 | 2.54% | −7.29% | −3.88% | 8.82% | 15.18% | |
| 1594.59 | 3.80% | −13.10% | −2.87% | 12.86% | 15.18% | |
| 1591.17 | 3.94% | −6.11% | −3.31% | 12.83% | 15.18% | |
| 1594.90 | 3.81% | −13.10% | −2.87% | 11.47% | 15.18% | |
| 1601.83 | 3.20% | −7.67% | −4.25% | 11.67% | 18.07% |
Table 6.
Limitations and Future Work
The evaluated workloads are small, with 33 template groups in JOB, 29 queries in JOB-Complex, and 14 templates in IMDb-CEB, which limits how rich a model they can support without overfitting. JOB-Complex consists of hand-crafted hard queries, so its results describe worst-case solver behavior more than the behavior of a learned router. The replay combines probe times and solver times from separate runs, and classifier time was not measured.
A first direction for future work is the selection of training data. The evaluation labels every query with all three solvers and three repetitions, which suits replay but exceeds what training needs. In a replay with labels for only half of the training template groups, the router still lowers mean held-out time by 9.0% on JOB and 8.0% on IMDb-CEB, compared with 12.3% and 8.5% with all labels. A deliberate selection would measure alternative solvers only where the router lacks evidence, for example for templates whose cluster is not yet dominant, and would reuse the end-to-end times that the default rule already produces in normal operation.
Another direction is the handling of mixed clusters. The router currently leaves their queries to the default rule, which ensures that every difference from PostgreSQL comes from the cluster winners but also caps the gain. On IMDb-CEB the learned DP/MCTS threshold outperforms the router by about three percentage points (Table 4), so a learned threshold, a finer clustering, or a per-query choice inside mixed clusters could recover part of this gap.
Conclusion
Join-order solvers differ in how they respond to the distribution of plan costs over join orders, and the relation count that PostgreSQL routes by does not describe this distribution. Two probe features computed in microseconds describe it well enough for a router that acts only on clusters with a clear winner to lower mean end-to-end time on JOB and IMDb-CEB. The per-query oracle is still about six percentage points ahead of the router on JOB and ten on IMDb-CEB, and the first places to close this gap are the queries of mixed clusters and the choice of training data.
References
- [1]PostgreSQL Global Development Group. Genetic query optimizer. PostgreSQL 16 Documentation, Chapter 60, 2025.
- [2]Vladimir Burlakov, Alena Rybakina, Sergey Kudashev, Konstantin Gilev, Alexander Demin, Denis Ponomaryov, and Yuriy Dorn. Practical mcts-based query optimization: A reproducibility study and new mcts algorithm for complex queries. arXiv preprint arXiv:2603.16474, 2026.arxiv.org/abs/2603.16474
- [3]Thomas Neumann and Bernhard Radke. Adaptive optimization of very large join queries. In Proceedings of the 2018 International Conference on Management of Data, pages 677–692, New York, NY, USA, 2018. Association for Computing Machinery. doi: 10.1145/3183713.3183733.DOI
- [4]Ji Zhang. AlphaJoin: Join order selection à la AlphaGo. In Proceedings of the VLDB 2020 PhD Workshop, volume 2652 of CEUR Workshop Proceedings, pages 1–4, Aachen, Germany, 2020. CEUR-WS.org. URL https://ceur-ws.org/Vol-2652/paper05.pdf.
- [5]Lin Xu, Frank Hutter, Holger H. Hoos, and Kevin Leyton-Brown. Satzilla: Portfolio-based algorithm selection for sat. Journal of Artificial Intelligence Research, 32:565–606, 2008.DOI
- [6]Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, and Thomas G. Price. Access path selection in a relational database management system. In Proceedings of the 1979 ACM SIGMOD International Conference on Management of Data, pages 23–34, New York, NY, USA, 1979. Association for Computing Machinery. doi: 10.1145/58259.58209.
- [7]Goetz Graefe and William J. McKenna. The volcano optimizer generator: Extensibility and efficient search. In Proceedings of the Ninth International Conference on Data Engineering (ICDE), pages 209–218, Los Alamitos, CA, USA, 1993. IEEE Computer Society Press.
- [8]Goetz Graefe. The cascades framework for query optimization. IEEE Data Engineering Bulletin, 18(3):19–29, 1995.
- [9]Guido Moerkotte and Thomas Neumann. Analysis of two existing and one new dynamic programming algorithm for the generation of optimal bushy join trees without cross products. In Proceedings of the 32nd International Conference on Very Large Data Bases (VLDB), pages 930–941, New York, NY, USA, 2006. VLDB Endowment.
- [10]Guido Moerkotte and Thomas Neumann. Dynamic programming strikes back. In Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data, pages 539–552, New York, NY, USA, 2008. Association for Computing Machinery. doi: 10.1145/1376616.1376672.DOI
- [11]Yannis E. Ioannidis and Younkyung Cha Kang. Randomized algorithms for optimizing large join queries. In SIGMOD, pages 312–321, New York, NY, USA, 1990. Association for Computing Machinery. doi: 10.1145/93597.98740.DOI
- [12]Donald Kossmann and Konrad Stocker. Iterative dynamic programming: A new class of query optimization algorithms. ACM Transactions on Database Systems, 25(1):43–82, 2000. doi: 10.1145/352958.352982.DOI
- [13]Thomas Neumann. Query simplification: Graceful degradation for join-order optimization. In Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data, pages 403–414, New York, NY, USA, 2009. Association for Computing Machinery. doi: 10.1145/1559845.1559889.DOI
- [14]Ryan Marcus and Olga Papaemmanouil. Deep reinforcement learning for join order enumeration. In Proceedings of the First International Workshop on Exploiting Artificial Intelligence Techniques for Data Management, pages 1–4, New York, NY, USA, 2018. Association for Computing Machinery. doi: 10.1145/3211954.3211957.DOI
- [15]Ryan Marcus, Parimarjan Negi, Hongzi Mao, Chi Zhang, Mohammad Alizadeh, Tim Kraska, Olga Papaemmanouil, and Nesime Tatbul. Neo: A learned query optimizer. Proceedings of the VLDB Endowment, 12(11):1705–1718, 2019. doi: 10.14778/3324263.3324264.DOI
- [16]Zongheng Yang, Wei-Lin Chiang, Sifei Luan, Gautam Mittal, Michael Luo, and Ion Stoica. Balsa: Learning a query optimizer without expert demonstrations. In Proceedings of the 2022 ACM SIGMOD International Conference on Management of Data, pages 931–944, New York, NY, USA, 2022. Association for Computing Machinery. doi: 10.1145/3514221.3517885.DOI
- [17]Ryan Marcus, Parimarjan Negi, Hongzi Mao, Nesime Tatbul, Mohammad Alizadeh, and Tim Kraska. Bao: Making learned query optimization practical. In Proceedings of the 2021 ACM SIGMOD International Conference on Management of Data, pages 1275–1288, New York, NY, USA, 2021. Association for Computing Machinery. doi: 10.1145/3448016.3452838.DOI
- [18]Lucas Woltmann, Jerome Thiessat, Claudio Hartmann, Dirk Habich, and Wolfgang Lehner. FASTgres: Making learned query optimizer hinting effective. Proceedings of the VLDB Endowment, 16(11):3310–3322, 2023. doi: 10.14778/3611479.3611528.DOI
- [19]Christoph Anneser, Nesime Tatbul, David Cohen, Zhenggang Xu, Prithviraj Pandian, Nikolay Laptev, and Ryan Marcus. AutoSteer: Learned query optimization for any SQL database. Proceedings of the VLDB Endowment, 16 (12):3515–3527, 2023. doi: 10.14778/3611540.3611544.DOI
- [20]Rong Zhu, Wei Chen, Bolin Ding, Xingguang Chen, Andreas Pfadler, Ziniu Wu, and Jingren Zhou. Lero: A learning-to-rank query optimizer. Proceedings of the VLDB Endowment, 16(6):1466–1479, 2023. doi: 10.14778/3583140.3583160.DOI
- [21]Lyric Doshi, Vincent Zhuang, Gaurav Jain, Ryan Marcus, Haoyu Huang, Deniz Altınbüken, Eugene Breydo, and Campbell Fraser. Kepler: Robust learning for faster parametric query optimization. Proceedings of the ACM on Management of Data, 1(1), 2023. doi: 10.1145/3588963.DOI
- [22]Pavel Sulimov, Claude Lehmann, and Kurt Stockinger. GenJoin: Conditional generative plan-to-plan query optimizer that learns from subplan hints. Proceedings of the ACM on Management of Data, 3(4):1–25, 2025. doi: 10.1145/3749165.DOI
- [23]Xiang Yu, Chengliang Chai, Guoliang Li, and Jiabin Liu. Cost-based or learning-based? a hybrid query optimizer for query plan selection. Proceedings of the VLDB Endowment, 15(13):3924–3936, 2022. doi: 10.14778/3565838.3565846.
- [24]Wangda Zhang, Matteo Interlandi, Paul Mineiro, Shi Qiao, Nasim Ghazanfari, Karlen Lie, Marc Friedman, Rafah Hosn, Hiren Patel, and Alekh Jindal. Deploying a steered query optimizer in production at Microsoft. In Proceedings of the 2022 International Conference on Management of Data, pages 2299–2311, New York, NY, USA, 2022. Association for Computing Machinery. doi: 10.1145/3514221.3526052.DOI
- [25]Jeffrey Tao, Natalie Maus, Haydn Jones, Yimeng Jacob R. Gadbo R. Gard, and Ryan Marcus. Learned offline query planning via bayesian optimization. Proceedings of the ACM on Management of Data, 3(3), 2025. doi: 10.1145/3725316.
- [26]Zixuan Yi, Yao Tian, Zachary G. Ives, and Ryan Marcus. Low rank learning for offline query optimization. In Proceedings of the 2025 ACM SIGMOD International Conference on Management of Data, New York, NY, USA, 2025. ACM. doi: 10.1145/3725412.DOI
- [27]Viktor Leis, Andrey Gubichev, Atanas Mirchev, Peter Boncz, Alfons Kemper, and Thomas Neumann. How good are query optimizers, really? Proc. VLDB Endow., 9(3):204–215, 2015.DOI
- [28]Yesdaulet Izenov, Asoke Datta, Brian Tsan, and Florin Rusu. Sub-optimal join order identification with L1-error. Proceedings of the ACM on Management of Data, 2(1), 2024. doi: 10.1145/3639272.DOI
- [29]Ziyun Wei and Immanuel Trummer. ROME: Robust query optimization via parallel multi-plan execution. Proceedings of the ACM on Management of Data, 2(3), 2024. doi: 10.1145/3654973.DOI
- [30]John R. Rice. The algorithm selection problem. Advances in Computers, 15:65–118, 1976.DOI
- [31]Carla P. Gomes and Bart Selman. Algorithm portfolios. Artificial Intelligence, 126(1–2):43–62, 2001. doi: 10.1016/S0004-3702(00)00081-3.DOI
- [32]Lars Kotthoff. Algorithm selection for combinatorial search problems: A survey. AI Magazine, 35(3):48–60, 2014.
- [33]Serdar Kadioglu, Yuri Malitsky, Meinolf Sellmann, and Kevin Tierney. ISAC—instance-specific algorithm configuration. In ECAI 2010: 19th European Conference on Artificial Intelligence, volume 215 of Frontiers in Artificial Intelligence and Applications, pages 751–756, Amsterdam, The Netherlands, 2010. IOS Press. doi: 10.3233/978-1-60750-606-5-751.DOI
- [34]Bernd Bischl, Olaf Mersmann, Heike Trautmann, and Mike Preuß. Algorithm selection based on exploratory landscape analysis and cost-sensitive learning. In Proceedings of the 14th Annual Conference on Genetic and Evolutionary Computation, pages 313–320, New York, NY, USA, 2012. Association for Computing Machinery. doi: 10.1145/2330163.2330209.DOI
- [35]Yuri Malitsky, Ashish Sabharwal, Horst Samulowitz, and Meinolf Sellmann. Algorithm portfolios based on cost-sensitive hierarchical clustering. In Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, pages 608–614, Palo Alto, CA, USA, 2013. AAAI Press.
- [36]Lin Xu, Holger H. Hoos, and Kevin Leyton-Brown. Hydra: Automatically configuring algorithms for portfolio-based selection. Proceedings of the AAAI Conference on Artificial Intelligence, 24(1):210–216, 2010. doi: 10.1609/aaai.v24i1.7565.DOI
- [37]Carlos Ansótegui, Meinolf Sellmann, and Kevin Tierney. Self-configuring cost-sensitive hierarchical clustering with recourse. In Principles and Practice of Constraint Programming, volume 11008 of Lecture Notes in Computer Science, pages 524–534, Cham, Switzerland, 2018. Springer. doi: 10.1007/978-3-319-98334-9_34.DOI
- [38]Marius Lindauer, Holger H. Hoos, Frank Hutter, and Torsten Schaub. AutoFolio: An automatically configured algorithm selector. Journal of Artificial Intelligence Research, 53:745–778, 2015. doi: 10.1613/jair.4726.DOI
- [39]Yannis E. Ioannidis, Raymont T. Ng, Kyuseok Shim, and Timos K. Sellis. Parametric query optimization. In Proceedings of the 18th International Conference on Very Large Data Bases, pages 103–114, San Francisco, CA, USA, 1992. Morgan Kaufmann.
- [40]Arvind Hulgeri and S. Sudarshan. Parametric query optimization for linear and piecewise linear cost functions. In Proceedings of the 28th International Conference on Very Large Data Bases, pages 167–178, San Francisco, CA, USA, 2002. Morgan Kaufmann.DOI
- [41]Güneş Aluç, David Daehan, and Ivan T. Bowman. Parametric plan caching using density-based clustering. In Proceedings of the 28th IEEE International Conference on Data Engineering, pages 402–413, Piscataway, NJ, USA, 2012. IEEE. doi: 10.1109/ICDE.2012.57.DOI
- [42]Antara Ghosh, Jignashu Parikh, Vibhuti S. Sengar, and Jayant R. Haritsa. Plan selection based on query clustering. In Proceedings of the 28th International Conference on Very Large Data Bases, pages 179–190, San Francisco, CA, USA, 2002. Morgan Kaufmann. doi: 10.1016/B978-155860869-6/50024-X.DOI
- [43]Songsong Mo, Yue Zhao, Zhifeng Bao, Quangqing Xu, Chuanhui Yang, and Gao Cong. RankPQO: Learning-to-rank for parametric query optimization. Proceedings of the VLDB Endowment, 18(3):863–875, 2024. doi: 10.14778/3712221.3712248.DOI
- [44]Bailu Ding, Sudipto Das, Wentao Wu, Surajit Chaudhuri, and Vivek Narasayya. Plan stitch: Harnessing the best of many plans. Proceedings of the VLDB Endowment, 11(10):1123–1136, 2018. doi: 10.14778/3231751.3231761.DOI
- [45]Hai Lan, Yang Yu, Zhifeng Bao, Zi Huang, and Yuwei Peng. Practical parameterized query optimization via efficient plan reuse and list-wise ranking. Proceedings of the ACM on Management of Data, 4(1):1–26, 2026. doi: 10.1145/3788254.DOI
- [46]Ron Avnur and Joseph M. Hellerstein. Eddies: Continuously adaptive query processing. In Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data, pages 261–272, New York, NY, USA, 2000. Association for Computing Machinery. doi: 10.1145/342009.335420.DOI
- [47]Volker Markl, Vijayshankar Raman, David E. Simmen, Guy M. Lohman, Hamid Pirahesh, and Miso Cilimdzic. Robust query processing through progressive optimization. In Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data, pages 659–670, New York, NY, USA, 2004. Association for Computing Machinery. doi: 10.1145/1007568.1007642.DOI
- [48]Immanuel Trummer, Junxiong Wang, Deepak Maram, Samuel Moseley, Saehan Jo, and Joseph Antonakakis. SkinnerDB: Regret-bounded query evaluation via reinforcement learning. In Proceedings of the 2019 International Conference on Management of Data, pages 1153–1170, New York, NY, USA, 2019. Association for Computing Machinery. doi: 10.1145/3299869.3300088.DOI
- [49]Michael Steinbrunn, Guido Moerkotte, and Alfons Kemper. Heuristic and randomized optimization for the join ordering problem. The VLDB Journal, 6(3):191–208, 1997. doi: 10.1007/s007780050040.DOI
- [50]Levente Kocsis and Csaba Szepesvári. Bandit based monte-carlo planning. In ECML, pages 282–293, Berlin, Heidelberg, 2006. Springer.
- [51]Johannes Wehrstein, Timo Eckmann, Roman Heinrich, and Carsten Binnig. JOB-Complex: A challenging benchmark for traditional and learned query optimization. In Proceedings of the VLDB 2025 Workshop on Applied AI for Database Systems and Applications (AIDB 2025), pages 1–8, London, United Kingdom, 2025. VLDB Endowment. URL https://www.vldb.org/2025/Workshops/VLDB-Workshops-2025/AIDB/AIDB25_8.pdf.arxiv.org/abs/2507.07471
- [52]Parimarjan Negi, Ryan Marcus, Andreas Kipf, Hongzi Mao, Nesime Tatbul, Tim Kraska, and Mohammad Alizadeh. Flow-loss: Learning cardinality estimates that matter. Proceedings of the VLDB Endowment, 14(11):2019–2032, 2021. doi: 10.14778/3476249.3476259.DOI
