Join-Order Optimization Under Cardinality Estimation Error
Plan join orders from noisy selectivity estimates alone
join_order_query_plan_runtimeChips & Compute SystemsData Systems
instruction.mdthis is what the agent is given
You inherit a query optimizer stub for an analytics workload of select-project-join queries
over a star/snowflake schema (4-15 relations per query). The optimizer must pick, for every
query, a left-deep join order and per-step physical operators — but the join selectivities it sees are noisy estimates from a
sample-based cardinality estimator, while the engine executes plans under the true selectivities.
Your submission is the optimizer itself (plan() in /app/methods/main/solver.py); it is re-run
on a sealed held-out workload of fresh queries, and your score is driven by the total true
execution cost of the plans it produces there.
Hard Constraints
Improve /app/methods/main/solver.pyin place; the grader re-runs exactly
plan(query) -> (order, ops) from that file. Keep the signature.
plan() receives only the estimated selectivities of a query (plus exact base-table
cardinalities). It must return a permutation of the query's relation ids and a list of
len(order) - 1 operators in {0=hash, 1=nested-loop, 2=sort-merge}.
The whole held-out workload (~120 queries, 4–15 relations each) must be planned within a
10-minute CPU budget in the grading container (4 CPUs, no GPU). Any illegal plan
(not a permutation, bad operator vector) scores 0 for that query.
You may use anything in /app (including fitting calibration models on the training split at
import time), but the grading container has no network — bake any learned parameters into your
files under /app/methods/.
Do not touch files outside /app.
What You Have
/app/data/train/relations.csv + joins_est.csv — an 80-query training workload in the same
format the grader uses: per-relation base cardinalities (exact) and per-join-edge estimated
selectivities.
/app/data/train/joins_true.csv — the true selectivities for the training queries only.
This is your window into how the estimator errs; the held-out workload ships no truth.
/app/methods/main/job_utils.py — the exact deterministic cost model the engine (and the
grader) uses to price a plan, plus workload loaders. Public and identical at grade time.
/app/methods/main/solver.py — the starter optimizer (written-order, all nested-loop). Weak
on purpose.
python /app/selfcheck.py — honest local proxy: runs your plan() on the estimate view of the
training queries and prices the plans under the training truth. Free, unlimited.
What You Submit
The improved optimizer under /app/methods/main/ (solver.py plus any helper/calibration files
it imports). No plan files: the grader calls your plan() on queries you have never seen.
How It Is Judged
The grader runs your plan() on each sealed held-out query (estimates only), prices the returned
plan under that query's true selectivities with the public cost model, and scores each query by
its true cost — lower is better — then averages across queries. The unmodified starter scores
reward 0; your score rises monotonically as the true workload cost falls. Beating a solid
conventional optimizer is the goal, and the reward is uncapped above it. A crashed / timed-out
run, or a workload with missing or extra query ids, scores 0.
Metric
mean true plan cost over the 90 sealed queries · lower is better
plan() replans each sealed query from noisy estimates; the public cost model prices that plan under true selectivities.
anchor
visible set
held-out
reward
B
shipped starter, all nested-loop
263,847.60
421,141.83
0.00
S
reference: exact DP on raw estimates
531.54
567.96
0.30
U
upper: exact DP on true selectivities
174.71
205.09
1.00
normalisation
m >= B
0
B > m >= S
0.3 * (ln B - ln m) / (ln B - ln S)
S > m >= U
0.3 + 0.7 * (ln S - ln m) / (ln S - ln U)
m < U
1 + 0.7 * (ln U - ln m) / (ln S - ln U)
m = this run's held-out metric · B = shipped starter, all nested-loop · S = reference: exact DP on raw estimates · U = upper: exact DP on true selectivities
Linear in log cost. Each query maps on its own floor/ref/upper, then the 90 rewards average; the table shows anchor means. Illegal plan: 0.
Rollouts
61 minwall clock
-spend
-tokens
7versions, 7 kept
keptrevertedno scoreturning point
v0Starter: relations in written order, every step nested-loop263,847.6
v1Left-deep DP on log-log calibrated selectivities, lognormal lift 1.31, hashSearch every left-deep prefix exactly, and plan on calibrated selectivities lifted to the lognormal mean, not the median.346.07
v2Lift raised 1.31 -> 1.85, chosen by 5-fold query CVFit on 64 queries, score true plan cost on the held 16; the CV mean prefers a lift more conservative than the identity.332.57
v3Calibration slope from a grid CV, B=0.80 instead of the OLS 0.824, A refit327.4
v4First DP join step weighted 0.20, downweighting its unreliable outputThe first join's estimated output is the least trustworthy term in the DP objective, so price it at a fifth of its weight.312.73
v5First-join weight 0.10 only when the raw estimated output is under 200 rows306.41
v6Cleanup: always hash, no inner operator search; v5 policy unchanged306.41
Seven snapshots over 61 min, none reverted; the harness reports no token or cost data. A t064-t079 slice was held out of every fit.
v0Starter: relations in written order, every step nested-loop263,847.63 min · $0.57
v1Exact left-deep subset DP on log-linearly calibrated estimates, best op per stepSearch every left-deep prefix exactly instead of trusting the written order, and plan on calibrated, not raw, selectivities.398.093 min · $0.75
v2Rewrite: self-contained at runtime, cartesian steps priced, beam fallback398.0922 min · $4.58
v3Calibration replaced by a Bayes posterior mean, baked as a 121-point tableEstimator log error is skewed (-0.83), so the posterior mean is not log-linear. Tabulated by quadrature, chosen by CV deviance.384.5522 min · $4.58
v4Robustness only: guarded fallbacks, exact DP to n<=18, beam then greedy, time limit384.5529 min · $6.28
v5Operator factor priced in expectation from the accumulated posterior log-variance384.5532 min · $7.12
v6Soft time limit degrades to a narrow beam or greedy, not a 3000-wide beam384.5553 min · $10.70
Seven snapshots, 53 min, $10.70. v1 took out 99.8% of the starter cost by minute 3; the five after it moved train 398.09 -> 384.55, under its ~50 sd.
v0Starter: relations in written order, every step nested-loop263,847.60 min · $0.13
v1Exact connected-subset DP on raw estimates, best operator per stepEnumerate every connected subset exactly instead of joining in the written order.531.542 min · $0.37
v2Bayesian shrinkage of two-table outputs from a cross-validated log-linear fitShrink each estimated two-table output toward a log-linear fit whose grid is picked by five-fold query CV.398.0928 min · $1.26
v3Robust calibration grid: slope 0.40 shrinkage plus a two-variance safety offset361.48810 min · $1.68
v4Tuned power law replaced by a smoothed empirical-Bayes posterior mean lookupPick the calibration on 1200 fresh generated workloads, not the visible mean: 339.87 vs v2 348.93, v3 357.50.385.32920 min · $3.31
v5Lookup compressed into a nine-parameter two-Gaussian error-mixture posterior385.2624 min · $4.13
v6Frontier-only DP enumeration and a legal disconnected-input fallback; plans unchanged385.2633 min · $6.54
Seven snapshots, 37 min, $7.79, none reverted. v4 gave up 24 visible points for a better fresh-workload mean; all 90 sealed plans match the Opus run.
v0Starter: relations in sorted-id order, every step nested-loop263,847.61 min · $0.23
v1Exact left-deep subset DP on raw estimates, model-optimal op per step531.542 min · $0.36
v2Log-linear selectivity calibration with risk offset, picked by 5-fold query CVEach candidate calibration is fitted on four query folds and judged by true plan cost on the fifth, not on the full-train mean.332.735 min · $0.64
v8Empirical-Bayes calibration adds the query's mean log base cardinality327.3922 min · $2.88
v14Dual-model gate: take the query-size calibration only if it wins by 0.75%324.45437 min · $5.45
v15Tuned gate replaced by jackknife agreement of the five leave-fold-out fits324.45639 min · $5.88
v16DP made faster: cached subset cardinalities, sort-merge proved dominated324.45644 min · $6.83
v17Join-output prior used when an estimated two-table output falls below 25 rowsThe estimator is least trustworthy where a near-empty intermediate dominates. Var(log J)=0.793 vs noise 0.651 gives weight 0.549.306.48453 min · $8.70
v18Trigger raised to 35 rows for queries of nine or more relations298.0656 min · $9.41
v19Fallback taken only when it overturns the raw-estimate preference296.62358 min · $9.90
v20Exact empirical-noise posterior and kNN local join-output maps303.5964 min · $11.92
v21Endpoint correction localised to anomalous edges only298.0564 min · $11.92
v22Scalarized multi-calibration DP over jackknife, anchor and raw scenarios324.4674 min · $15.56
v23Reverted to v18 after fresh workloads from the recovered generatorCandidates are now judged on repeated workloads from a recovered generator, and v19's 1.44-point visible gain is given up.298.0683 min · $18.57
v24Large-query cutoff swept 20-50 on 30x120 synthetic workloads; 35 kept298.0686 min · $19.71
v25Output-posterior confidence shift lowered to +0.75 on 40x120 workloads309.14389 min · $20.97
v26Large-query anomaly cutoff raised 35 -> 50 on 60x120 workloads319.77594 min · $23.00
v27Joint re-grid of cutoff and shift; robust midpoint shift 0.50 chosen329.25499 min · $25.10
v28Small-query cutoff sensitivity 10-40; differences under 1 cost, 25 kept329.254102 min · $26.29
19 snapshots of 29 experiments. Train fell to 296.62 by v19, then rose to 329.25 on purpose: from v23 selection ran on fresh generator workloads.
v0Starter: relations in sorted-id order, every step nested-loop263,847.61 min · $0.07
v1Exact left-deep subset DP on raw estimates, best operator per stepEnumerate every left-deep prefix exactly under the public cost model instead of joining in the written order.531.542 min · $0.11
v2Estimated selectivities scaled 1.5x; DP over sorted tuples, neighbour joins onlyUnderestimated selectivities are what pick nested-loop, so bias every estimate up by one flat factor swept on the train mean.377.64638 min · $0.43
v3Selectivity floor 1.8e-4 so zero-sample joins cannot underestimate outputA rare join with no sampled rows reads as selectivity zero; a floor keeps its intermediate large enough to price honestly.340.74744 min · $0.59
Four snapshots, 45 min, $0.67. Both constants, scale 1.5 and floor 1.8e-4, were swept directly on the visible train mean.