Header Ad Placement

Probe Routing Cuts JOB Time by 12.26% in Replay, but Simpler Policies Beat It on IMDb-CEB

DATABASES / QUERY OPTIMIZATION

A query's table count is a cheap guide to optimizer choice, not a complete description of its search space. New probe features help a solver router, while the paper's strongest baselines and missing online costs limit the deployment claim.

By Ossam Hashim

KEY FINDINGS

  • On 50 random 80/20 query splits, the selected router reports a mean held-out end-to-end time reduction of 12.26% on JOB and 8.53% on the evaluated IMDb-CEB subset versus PostgreSQL's default solver rule. JOB-Complex instead regresses by 2.81%.
  • The router is not the strongest practical policy everywhere. On IMDb-CEB, always using MCTS saves 11.33%, and a learned DP/MCTS relation-count threshold saves 11.98%, both above the selected router's 8.53%.
  • Probe time is small in the measured records: about 20 microseconds at the median and at most 57 microseconds. Classifier time is not measured and is treated as zero, and the evaluation replays separately recorded probe and solver measurements rather than timing the complete online path.
  • A three-feature ablation reaches a 12.24% mean reduction on IMDb-CEB, versus 6.76% using relation count alone. That is a different feature configuration from the selected two-feature router, not a replacement for its main 8.53% result or evidence of universal regression avoidance.

The decision before the join-order decision

A database optimizer does not only choose a plan. It also chooses how much effort to spend searching for one. Exhaustive or near-exhaustive enumeration can find a better join sequence, yet use more planning time than that sequence saves during execution. A cheaper randomized search can be the right answer even when its final plan is not the best one available.

PostgreSQL exposes this tradeoff through its genetic-query-optimizer threshold. Its query-planning documentation gives a default geqo_threshold of twelve FROM items, with counting details such as a full outer join being treated as one item. Below the configured boundary, the usual search is used; above it, GEQO bounds search effort through a genetic method. Join collapsing and other planner settings also affect the search problem presented to that rule.

The new probe-routing paper asks whether a small amount of information about the join-order cost landscape can improve that solver choice. It considers dynamic programming, GEQO and an added Monte Carlo tree search solver. It does not replace PostgreSQL's executor, and it does not demonstrate that MCTS is part of a stock PostgreSQL release.

The distinction matters because a faster portfolio can make a sophisticated selector look better even when selection itself adds little. The study includes simple policies on the same held-out splits, exposing how much of the gain comes from access to MCTS and how much comes from a more informed routing rule.

Optimize time, not the number of winning choices

The router's objective is planning time plus execution time. Selecting the fastest solver on the largest number of queries is not enough if the mistakes occur on the most expensive queries. A few large regressions can overwhelm many small improvements.

The paper gives a concrete reason to look beyond relation count. JOB queries 28a and 33c both have fourteen relations. GEQO takes 18.1 seconds on the former against DP's 10.2 seconds, while it takes 0.99 seconds on the latter against DP's 1.34 seconds. The same size rule sends both to GEQO, but the cost of that choice is different.

These are reported end-to-end measurements, not a new timing experiment performed for this article. They motivate the feature design without proving that one statistic causes GEQO's behavior. Estimated cardinalities, join predicates and the configured solver all influence the result.

The PostgreSQL GEQO documentation supports the underlying concern. It describes join sequences as integer encodings, edge-recombination crossover and fitness evaluations through the standard planner. It also notes that a useful partial sequence can depend on the rest of the join order. A crossover designed to preserve local adjacency is not guaranteed to preserve a good database plan.

A cheap sketch of the search landscape

The probe samples random left-deep join orders and scores them with a simplified estimate of intermediate-result sizes. It uses base-relation cardinality estimates, the join graph and a fixed selectivity of 0.1. The cost is computed in log space to avoid overflowing on large products.

This is not execution of the sampled plans, nor is it a full invocation of every candidate solver. It is a low-cost feature calculation before join enumeration. The resulting values describe the sampled surrogate landscape, which can be informative without perfectly predicting real execution time.

The first feature, tail spacing, describes the spacing among the lowest sampled scores relative to the best sample. The paper uses a Hill-style statistic, then applies log(1+alpha) before scaling. Its intended role is to distinguish landscapes with many competitive sampled orders from those where good orders are rarer.

The second, crossover surprise, compares the estimated cost of a recombined child order with the mean cost of its two parents. A normalized variance summarizes how unpredictable those deviations are. It can exceed one; it is not an accuracy score bounded between zero and one. The design uses the same broad edge-recombination idea that makes the feature relevant to GEQO.

The probe requests max(2n, 8) random orders and 2n parent pairs, subject to its time cap. These are sampling budgets, not enumeration of the search space or guarantees that the best join order is observed. A small probe can only supply evidence for selection, not certify the resulting plan.

The selected router does not use every proposed feature

Offline, training queries are scaled and clustered. For each cluster, the router totals each solver's measured end-to-end time and identifies the winner. A cluster can receive a solver only if its lead meets a configured margin and the cluster contains enough distinct template groups.

Other clusters keep PostgreSQL's default rule. Queries lacking probe features also fall back. This makes the fallback explicit, but it is not a theorem that every newly routed query will improve. A winning total on a training cluster does not guarantee that all its members, or future queries mapped there, benefit.

The selected configuration is especially important to state. A grid search on JOB chooses four clusters, robust scaling, relation count plus tail spacing, a depth-two tree and a dominance margin of zero. The proposed crossover-surprise feature is not in this main configuration. Describing the main result as a router using all three features would be inaccurate.

A zero margin also means the selected model does not require a positive percentage cushion over the second-best solver. The support-count condition remains: five template groups for JOB and JOB-Complex, three for IMDb-CEB. That is evidence against a cluster containing only variants of one template, not a formal protection against runtime regressions.

The shallow classifier is trained on time loss

The online model is a shallow tree that predicts a cluster. Its loss is based on positive excess end-to-end time relative to the training query's own cluster action, rather than simply counting wrong cluster labels. A mistaken label that leaves the solver unchanged is different from one that selects an expensive solver.

The tree evaluates a small number of candidate split points per feature and enforces minimum leaf support. Once the incoming query reaches a leaf, the associated cluster either supplies its solver or retains the PostgreSQL rule. The selected solver still plans the query from scratch.

This is solver routing, not cached-plan selection. It does not store a previously executed plan and assume that plan remains good for a new parameter binding. It also does not race several solvers online and return the first result. One routing mistake can therefore pay the full cost of the chosen solver.

Each workload receives its own scaling, clusters, dominance labels and tree. Reusing the configuration across workloads is not the same as transferring a single trained model unchanged. That difference narrows the generalization claim and makes the quality of the offline training measurements important.

What the replay actually tests

The experiment uses 113 JOB queries, 29 JOB-Complex queries and a 200-query IMDb-CEB subset with at least nine relations, sampled across fourteen templates. These are not the entire CEB collection. The CEB repository describes much larger IMDb workloads, while the JOB distribution repository identifies the original benchmark queries and warns that dataset choices affect their meaning.

One of thirty JOB-Complex queries is excluded because both MCTS and PostgreSQL with GEQO exceed the three-minute timeout. The retained total is 342 queries, each measured for three solvers and three repetitions, producing 3,078 solver runs. The paper uses the median of three timings for each query-solver pair.

Measurements run on an AMD EPYC 9654 node with 192 GB of memory and PostgreSQL 19devel from a February 2026 master build. This is a specific development snapshot, not evidence that the result holds for every currently deployed release, machine or cache state. The artifact documentation describes seeded cold-cache solver measurements.

For evaluation, each workload is randomly split by query fifty times. Training gets eighty percent, and the remaining twenty percent is routed using recorded measurements. Template groups contribute to the cluster-support rule; they do not define a leave-template-out holdout. Variants from one template can therefore appear on both sides of a split.

The router configuration is selected on twenty random JOB splits, then reused as a configuration for the other workloads. The experiment demonstrates behavior on these small query distributions. It does not establish performance on unseen schemas, a chronological workload shift or entirely new template families.

The headline gains and their stronger baselines

The selected router's mean reduction against the default is 12.26% on JOB and 8.53% on IMDb-CEB. On JOB-Complex it is negative: a 2.81% increase in held-out time. Those reductions are means of split-level reductions, so they should not be reconstructed by dividing the separately averaged time columns and expecting the same result.

On JOB, always-MCTS reaches 12.12%, almost the router's 12.26%. The learned DP/MCTS threshold reaches 10.83%. This says that the router can recover a good policy from training, but much of its headline improvement is also available through the stronger solver portfolio.

On IMDb-CEB, always-MCTS reaches 11.33%, and the learned DP/MCTS threshold reaches 11.98%. Both beat the selected router's 8.53%. On JOB-Complex, the threshold is the only listed practical policy with a positive reduction, at 0.91%, while always-MCTS also regresses. A favorable comparison with the stock threshold is not enough to establish the router as the best available selector.

The native DP/GEQO portfolio is even more cautionary. Its selected router gains 3.02% on JOB and 3.94% on IMDb-CEB, but loses 7.72% on JOB-Complex. Always-GEQO beats that router on all three workloads in the reported comparison. Adding a routing layer without the additional solver does not reproduce the headline gains.

Feature information is useful, but not a safety guarantee

The IMDb-CEB ablation asks a different question: what changes when the same router setup receives different feature sets? With all three solvers available, relation count alone yields a 6.76% mean reduction. Tail spacing alone yields 10.74%, crossover surprise alone 10.95%, and all three features together 12.24%.

That is evidence that the probes carry information beyond size. It is not evidence that the selected main configuration secretly obtains 12.24% on IMDb-CEB. The selected relation-count-plus-tail-spacing configuration remains at 8.53%. Choosing a feature set after examining a particular workload is an additional model-selection decision.

Split variation also matters. Most ablation feature sets have at least some negative split reductions. Without MCTS, every feature set increases held-out time on at least five percent of the splits. A favorable mean and an explicit fallback do not eliminate expensive mistakes.

The paper's P90 and P95 values in its main table are upper percentiles of per-query percentage reductions. They are not P90 or P95 query-latency improvements, and they do not describe the worst regressions. The negative JOB-Complex aggregate despite positive upper reduction percentiles shows why the distinction matters.

Microsecond probes are not the whole online cost

Reported probe time is roughly twenty microseconds at the median and at most fifty-seven microseconds per query. The replay charges that measured probe cost where the tree is used. That is encouraging for a lightweight selector, but it is not a complete measurement of deployment overhead.

Classifier time is set to zero because it is not measured. Probe timings and solver timings come from separate runs. The artifact includes PostgreSQL extensions and an offline analysis path, but the paper's performance result is still the replay of recorded measurements, not a fully timed integrated production rollout.

Offline labeling is more substantial than the online probe. The complete experiment runs all three solvers three times per query. The paper studies reduced labeling as future-work evidence, but it does not make this exploration free. A deployment would need to account for training cost, drift and the consequences of testing slow alternatives.

The useful operational implication is to compare the selector with cheap, strong policies on the same workload and include planning, execution and selection overhead. It is not a recommendation to disable PostgreSQL's normal safeguards or change a production threshold based only on this paper.

Assumptions and limitations

All database timings and router scores are the paper authors' reported measurements. Only the invented aggregation example was executed for this article. No PostgreSQL server, optimizer extension, model-training pipeline or benchmark replay was run independently. Reading the artifact is not an independent reproduction.

The evidence covers small IMDb-based workloads, random query-level holdouts, a particular development build and recorded median solver timings. It includes a timeout exclusion, configuration selection on JOB, separately recorded probe times and an unmeasured classifier cost. The fallback and training-cluster winner test are design choices, not a no-regression guarantee.

The contribution is a compact way to inspect the search landscape before choosing a search algorithm. Its most credible result is that those features add information beyond relation count. Whether the complete router is worth deploying remains a workload-specific comparison against simple thresholds, fixed solvers and the full cost of learning and routing.

Worked Example: More correct choices can still lose

This invented standard-library example uses ten fictional queries. A policy halves the first nine one-second queries but doubles one hundred-second query. It wins on nine of ten queries yet increases total time from 109 seconds to 204.5 seconds, an 87.61% increase. The output reports 9 wins and a negative reduction of about -87.61%. It illustrates a time-weighted objective, not the paper's recorded measurements or router implementation.

from math import fsum

baseline = [1.0] * 9 + [100.0]
chosen = [0.5] * 9 + [200.0]
wins = sum(a < b for a, b
           in zip(chosen, baseline))
old = fsum(baseline)
new = fsum(chosen)
reduction = 100 * (1 - new / old)
print("wins", wins)
print("seconds", old, new)
result = round(reduction, 2)
print("reduction", result)

Sources & Provenance

  • Probe-routing paper: complete main text, design equations, evaluation tables, baseline comparisons and stated limits; no appendices are present in the inspected version.
  • Router artifact documentation: extensions, recorded solver measurements, retrospective probe logs and offline replay boundary; not proof of independent reproduction.
  • PostgreSQL query-planning documentation: GEQO threshold, FROM-item counting and configurable search tradeoffs.
  • PostgreSQL GEQO documentation: genetic join-order representation, edge recombination and interaction between partial sequences.
  • JOB distribution repository: benchmark origin and dataset-version warning; this repository is not maintained by the original paper's authors.
  • CEB repository: broader workload scope and distinction between this study's selected 200-query subset and the larger benchmark.

The interpretation and fictional time-aggregation example are original analysis. No first-hand deployment, professional credential or new database-performance measurement is claimed.

Comments

Kubernetes Liveness Is Not Readiness: Why a Health Check Can Amplify an Outage

KUBERNETES FAILURE RECOVERY A failed health check is an observation. Restarting a container and withholding traffic are different responses, and choosing the wrong one can amplify an outage. By Hossam The important question is what failure should trigger A web application loses access to its shared database. Its processes are still running, but requests that require database access fail. A health endpoint reports the dependency problem. Should Kubernetes restart every application container, or stop directing those requests to it? The endpoint alone cannot choose the right recovery action. Kubernetes separates startup, liveness and readiness probes because they answer different operational questions. Startup protects initialization, liveness can trigger container termination and restart handling, and readiness controls eligibility for traffic from matching Services. A green check is meaningful only within the check and response that were designed. This is a documentation-based de...

Editorial Governance & Pages