When Does q-error Predict Plan Regret? Three Regimes of Cardinality-Estimation Error Madhulatha Mandarapu∗
Sandeep Kunkunuru†
arXiv:2606.15600v1 [cs.DB] 14 Jun 2026
VaidhyaMegha Private Limited, India https://samyama.ai/ June 2026
Abstract Cardinality-estimation (CE) research ranks estimators by q-error, yet it is well known that q-error is an imperfect proxy for query-plan quality. We give a measurement-driven account of when it is a good proxy and when it is not, and why. Modeling plan selection as an argmin over a piecewise-linear cost landscape, we find that plan regret (the cost of the chosen plan relative to the optimal, under true cardinalities) is governed by plan-cost geometry in a regime-dependent way. (i) For small errors, a true-point condition number κ predicts regret and out-predicts q-error; its predictive power decays to zero as error grows, as a local linearization must. (ii) For large errors—where deployed learned estimators operate—an estimator-independent average-case sub-optimality measure ACS∞ predicts which queries are regret-prone (Spearman ρ ≈ 0.54 on STATS-CEB), while q-error is nearly uninformative at the query level (ρ ≈ 0.05). (iii) The worst case is Haritsa’s maximum sub-optimality (MSO). The P three are one cost-ratio spectrum under three weightings. We prove a limit law ACS∞ (q) = k rk πk with cardinality-independent combinatorial weights, and validate every claim on STATS-CEB and JOB-light with four released estimators under pre-registered decision rules, and confirm on real PostgreSQL runtime that ACS∞ predicts regret where q-error does not. The contribution is conceptual and empirical—an average-case companion to worst-case robust query optimization, and a characterization of when an accuracy metric tracks plan quality—rather than a new estimator. Code and the full pre-registration are public.1
1
Introduction
A cardinality estimator predicts the size of a (sub-)query result; the query optimizer feeds these estimates to a cost model and chooses a plan. Errors propagate, and bad estimates yield bad plans [Leis et al., 2015]. The field measures estimator quality with q-error, max(ĉ/c, c/ĉ), which enjoys a worst-case guarantee: bounding the maximum q-error over a plan’s sub-expressions bounds the plan’s sub-optimality [Moerkotte et al., 2009]. Yet that bound is loose—“impractically large when the estimation error is significant, as is often the case” [Haritsa, 2020]—and empirical studies repeatedly find that large q-error improvements need not improve plans [Han et al., 2022, Lee et al., 2023]. ∗
[email protected] [email protected] 1 https://github.com/samyama-ai/ce-metric-eval †
1
Query q : perturb sub-plan cardinalities by estimation error σ which regime? (size of the error)
Large error ACS∞ (this work)
Small error condition number κ distance to nearest plan-switch wall
predicts regret ρ ≈ 0.70 (beats q-error)
Worst case MSO (Haritsa)
average over cost cells
maximum over cells
predicts which queries ρ ≈ 0.54 (qerror: 0.05)
worst-case bound (prior art)
One cost-ratio spectrum {rk } of the candidate plans, three weightings: P κ ∼ nearest gap • ACS∞ = k rk π k (minimax-rank average) • MSO = maxk rk
Figure 1: The three regimes. Which plan-cost-geometry quantity predicts plan regret depends on the size of the cardinality-estimation error; all three are weightings of the same plan cost-ratio spectrum {rk }, and q-error—an estimate-magnitude scalar—is orthogonal to that geometry. We ask a sharper question: when does a smaller q-error mean a better plan, and what does predict plan regret when q-error does not? Treating plan choice as an argmin over a piecewise-linear (in log-cardinality) cost landscape, we find a clean, regime-dependent answer (Figure 1): 1. Small-error regime. A per-query condition number κ—the distance to the nearest plan-switch boundary—predicts regret and out-predicts q-error; its power decays to zero as error grows, because the underlying forward ≈ condition-number × backward-error relation is local (Section 3). 2. Large-error regime. Where deployed learned estimators sit, local quantities stop working. An estimator-independent average-case sub-optimality ACS∞ predicts which queries are regret-prone (ρ ≈ 0.54 on STATS-CEB), against ρ ≈ 0.05 for q-error at the query level (Section 4). P
3. A limit law. ACS∞ (q) = k rk πk , where rk are true plan cost-ratios and πk are cardinalityindependent combinatorial weights; the worst-case companion is MSO(q) = maxk rk [Haritsa, 2020] (Section 5). This reconciles the long-running “q-error vs. plan-cost” tension as two regimes of one phenomenon. The result is modest and stands entirely on prior work (Section 6); we make no claim to a new estimator. All experiments use pre-registered decision rules—including one hypothesis we rejected and one near-miss we kept on record—and all code is public.
2
Setup
A query q has valid plans P1 , . . . , PK ; plan k’s internal (join) nodes form a set Ik of connected table-subsets S. Under a cardinality vector c (one entry per subset), the cost is the Cout model 2
Plan-optimality cells: one query, the cost-ratio spectrum {rk} large error: lands in any cell (ACS = average, MSO = worst) r = 2.0
log cardinality (sub-plan B)
r = 3.0 r = 1.3 Pc , (true) r=1
small error: stays in P ( )
r = 6.1 (MSO)
r = 1.8
r = 2.4
log cardinality (sub-plan A)
Figure 2: Plan-optimality cells. Log-cardinality space tiles into cells where each plan is optimal—a plan diagram [Reddy and Haritsa, 2005]. Small error keeps the estimate in the optimal cell, so the condition number κ is the distance to the nearest wall; large error lands it in any cell, where ACS∞ averages the cost-ratios and MSO takes the worst. P
Ck (c) = S∈Ik cS . The optimizer chooses k̂ = arg mink Ck (ĉ) under estimates ĉ; the truth-optimal plan is k ∗ = arg mink Ck (c). Plan regret (equivalently P-error / Plan-Cost [Negi et al., 2021, Han et al., 2022]) is C (c) ρ(ĉ) = k̂ ≥ 1, Ck∗ (c) i.e. the chosen plan’s cost under truth relative to optimal. Let rk = Ck (c)/Ck∗ (c) ≥ 1 be plan k’s true cost-ratio; {rk } is the query’s cost-ratio spectrum. We model estimation error as log ĉS = log cS + εS , εS ∼ N (0, σ 2 ) i.i.d., sweeping σ from small (accurate) to large (inaccurate); q-error of a subset is e|εS | .
3
Small error: a condition number
Regret is a forward error; q-error is a backward error; the missing factor is a condition number. For the optimal plan P ∗ and an alternative P ′ , the smallest L∞ log-perturbation that flips the choice has the closed form δ = 12 ln(A/B), where A, B are the true-cardinality sums over the plans’ non-shared internal nodes; we set κ = 1/ minP ′ δ. Intuitively, a query whose true cardinalities sit near a plan-switch boundary is ill-conditioned (Figure 4). Result. At small σ, the per-query Spearman correlation ρ(regret, κ) is 0.70 on STATS-CEB and 0.79 on JOB-light (an independent IMDB-schema workload), exceeding the correlation with realized q-error, robust to query size (partial ρ ≈ 0.65 controlling for the number of tables), and decaying to ≈ 0 as σ grows (Figure 3, left). This is the local prediction made explicit: the condition number governs regret precisely while the linearization holds. The decay—and the failure of κ at large error—is not a defect but a signature of locality, and it motivates Section 4.
3
predicts regret
only at small error
Large-error regime (STATS-CEB)
STATS-CEB job-light
0.6
0.6 (query regret, predictor)
(plan regret, condition number )
0.8
0.4 0.2 0.0
0.55
0.5 0.4 0.3 0.20
0.2 0.1
0.2 0.5
1.0 1.5 2.0 2.5 estimation error scale (lognormal)
0.05
0.0
3.0
q-error
(local)
ACS
Figure 3: Left: the true-point condition number κ predicts plan regret only for small estimation error, decaying to ≈ 0 as error grows (both benchmarks). Right: in the large-error regime where deployed estimators operate, ACS∞ predicts which queries suffer regret far better than q-error or κ (STATS-CEB, query-level Spearman).
4
Large error: average-case sub-optimality
At large σ the estimate is displaced far across the cost-cell complex, so true-point quantities ( κ, and—we verify—cost-weighted and discriminative variants ) stop predicting regret. We instead define the average-case sub-optimality
ACS∞ (q) = lim Eε ρ(ĉ) , σ→∞
the average-case analogue of Haritsa’s worst-case MSO [Haritsa, 2020]. Intuitively ACS∞ is “the typical badness of a random plan for this query”: a query whose cost-ratio spectrum is dispersed is intrinsically regret-prone under poor estimation, independent of the estimator. Result (pre-registered). On STATS-CEB—where the four released estimators (BayesCard, DeepDB, FLAT, NeuroCard) are inaccurate (median q-error 2 to ∼105 )—ACS∞ predicts per-query regret at ρ ≈ 0.54, against ρ ≈ 0.05 for q-error and ρ ≈ 0.20 for κ (Table 1, Figure 3 right). Under a pre-registered, margin-primary rule, the bootstrap 95% confidence interval of the margin ρACS∞ − ρq is [0.22, 0.74]; the effect holds on held-out query halves and on a fifth, unseen estimator (the DuckDB optimizer’s native estimates); and it is regime-specific—ACS∞ does not win on the small-error JOB-light workload, where κ does. Because ACS∞ uses no estimator outputs, every test on real estimators is intrinsically out-of-sample. ACS∞ is a query-level measure: it predicts which queries CE error endangers, not estimator-to-estimator variation within a query. Validation on a real optimizer (PostgreSQL). A natural objection is that Cout is a simplified cost model. We therefore re-measured regret as actual PostgreSQL 13.1 runtime: injecting each estimator’s join cardinalities into the optimizer, executing the chosen plan, and taking the ratio to the true-cardinality plan’s runtime (median of three warm runs; a plan exceeding the timeout is recorded as a regret lower bound, so the highest-regret queries are kept). On full coverage (110/111
4
Condition number = 1/ : distance to the nearest plan-switch boundary 5000
cost of P (truth-optimal) cost of alternative P 0
plan cost Cout
4000
= 12 ln(A/B) (nearest wall)
3000 2000 P stays optimal (small error)
1000 1.5
1.0
plan flips to P 0
0.5 0.0 0.5 1.0 1.5 2.0 2.5 log-perturbation u toward the boundary (u = logq-error)
3.0
Figure 4: The condition number. Two plans’ costs cross at δ = 12 ln(A/B); within δ the truthoptimal plan survives, beyond it the choice flips. We set κ = 1/δ for the nearest such boundary. Table 1: Predicting query-level regret in the large-error regime (STATS-CEB, Spearman ρ). ρ(regret, ·)
Predictor q-error (estimate magnitude) κ (true-point, local) ACS∞ (average-case, this work)
0.05 0.20 0.54
queries), ACS∞ — computed purely from Cout geometry, never seeing PostgreSQL — predicts real runtime regret with ρ = 0.42, versus ρ = −0.16 for q-error, with a bootstrap 95% CI of the margin = [0.34, 0.82] (Figure 5). The headline regrets are genuine plan changes (e.g. 32.6 s vs. 1.3 s). So the regimes are not an artifact of the abstract cost model. (A plan-cost arm via plan pinning is infeasible: the estimator-induced bad plans are near-cartesian join orders that hint tools will not reproduce under true cardinalities — reported as a limitation, not hidden.)
5
A limit law
Theorem 1 (informal). As σ → ∞, optimizer selection converges to the cardinality-free minimaxrank rule k̂ → arg mink maxS∈Ik εS , and ACS∞ (q) =
K X
rk πk ,
k=1
where rk are the true cost-ratios and πk are cardinality-independent selection probabilities determined solely by the plan set-system {Ik }. Sketch. In log-space log Ck (ĉ) = LSES∈Ik (log cS + εS ), a log-sum-exp. As σ → ∞ the ε-spread dominates the O(1) cost terms, so log Ck (ĉ) → maxS∈Ik εS with probability → 1; the argmin then depends only on the ranks of {εS } and on which subsets lie in which plans. Hence πk is combinatorial, and ACS∞ factorizes into a cardinality part (the cost-ratio spectrum {rk }) and a structure part 5
( real PG runtime regret , predictor )
Predicting real PostgreSQL runtime regret (k=3, 110/111 queries; injected estimator cardinalities) 0.5
+0.42
0.4 0.3 0.2 0.1 0.0
-0.02
0.1 0.2 0.3
-0.16 (local)
q-error
ACS
Figure 5: Real PostgreSQL runtime. ACS∞ (from Cout geometry) predicts actual PostgreSQL runtime regret; q-error and the local κ do not (k=3, 110/111 queries, injected estimator cardinalities). ({πk }). The worst-case dual is MSO(q) = maxk rk : the same spectrum under a max instead of the minimax-rank average. Validation. The cardinality-aware large-σ estimate of ACS∞ matches Monte-Carlo at Spearman 0.99. Cardinality-independence of πk is confirmed numerically: the correlation between the cardinality-aware and cardinality-free estimates rises monotonically with σ (0.985 at σ=8, 0.990 at 15, 0.994 at 30), so the residual is finite-σ slack, not cardinality dependence.
6
Related work and reconciliation
This work builds on, and does not originate, the geometry it uses. The partitioning of selectivity/cardinality space into plan-optimality regions is the plan diagram / POSP line [Reddy and Haritsa, 2005, Harish et al., 2008]; our “cost-cells” are theirs. The q-error bound and its looseness for large error are due to Moerkotte et al. [2009] and restated by Haritsa [2020]. Maximum suboptimality (MSO) and worst-case robust query processing are Haritsa’s; ACS∞ is the average-case companion to MSO. Wolf et al. [2018] define per-plan robustness by integrating a fixed plan’s cost over a cardinality range, for plan selection; ACS∞ instead measures expected sub-optimality over the optimizer’s plan choice, as a per-query difficulty predictor—related but distinct. P-error / Plan-Cost as the regret metric is from Negi et al. [2021]; the STATS-CEB benchmark from Han et al. [2022]; and the closest empirical error-injection study is Lee et al. [2023], which measures plan-quality impact but does not define a condition number, a regime crossover, or a κ-vs-q-error comparison. Against this backdrop the contributions are narrow and specific: the average-case predictor ACS∞ , its limit theorem, the κ/ACS∞ /MSO regime taxonomy, and the pre-registered demonstration that q-error fails to predict query-level regret in the large-error regime where ACS∞ succeeds. The “q-error vs. plan-cost” debate is thus two regimes of one phenomenon; deployed estimators straddle the boundary, which is why no single scalar error metric predicts their regret cleanly.
6
7
Limitations
Our geometric quantities are defined under the Cout cost model; we validated that the largeerror regime survives on real PostgreSQL runtime (Section 4), but the exact crossover location is cost-model-dependent, and the noise-free plan-cost arm was not obtainable (hint-pinning cannot reproduce the estimators’ near-cartesian plans). Coverage on STATS-CEB is 123/146 queries (the rest have a sub-plan join whose true COUNT(*) exceeds a timeout at up to 1010 rows); JOB-light is fully covered. ACS∞ is a query-level measure and does not predict per-estimator variation. The limit law is a σ → ∞ statement, whereas deployed estimators sit at finite σ, where a cardinality correction to πk remains. We invite corrections and pointers to prior art we may have missed.
8
Conclusion
Whether q-error predicts plan regret depends on the error regime, and in each regime a specific plan-cost-geometry quantity does the predicting: a condition number for small errors, average-case sub-optimality for large errors, and maximum sub-optimality for the worst case—one cost-ratio spectrum under three weightings. The average-case piece, ACS∞ , is an estimator-independent querydifficulty measure with a clean limit law, complementing the worst-case robust-query-optimization literature. Code and the complete pre-registration, including a rejected hypothesis and a near-miss, are public. Code and data availability. All code, benchmarks, figures, and the complete pre-registration trail—including the rejected hypothesis and the near-miss—are public at https://github.com/ samyama-ai/ce-metric-eval.
References Yuxing Han, Ziniu Wu, Peizhi Wu, Rong Zhu, Jingyi Yang, Liang Wei Tan, Kai Zeng, Gao Cong, Yanzhao Qin, Andreas Pfadler, Zhengping Qian, Jingren Zhou, Jiangneng Li, and Bin Cui. Cardinality estimation in dbms: A comprehensive benchmark evaluation. Proceedings of the VLDB Endowment, 15(4):752–765, 2022. doi: 10.14778/3503585.3503586. D. Harish, Pooja N. Darera, and Jayant R. Haritsa. Identifying robust plans through plan diagram reduction. Proceedings of the VLDB Endowment, 1(1), 2008. doi: 10.14778/1453856.1453976. Jayant R. Haritsa. Robust query processing: Mission possible. Proceedings of the VLDB Endowment, 13(12):3425–3428, 2020. doi: 10.14778/3415478.3415561. Kukjin Lee, Anshuman Dutt, Vivek Narasayya, and Surajit Chaudhuri. Analyzing the impact of cardinality estimation on execution plans in microsoft sql server. Proceedings of the VLDB Endowment, 16(11):2871–2883, 2023. doi: 10.14778/3611479.3611494. Viktor Leis, Andrey Gubichev, Atanas Mirchev, Peter Boncz, Alfons Kemper, and Thomas Neumann. How good are query optimizers, really? Proceedings of the VLDB Endowment, 9(3):204–215, 2015. doi: 10.14778/2850583.2850594. Guido Moerkotte, Thomas Neumann, and Gabriele Steidl. Preventing bad plans by bounding the impact of cardinality estimation errors. Proceedings of the VLDB Endowment, 2(1), 2009. doi: 10.14778/1687627.1687738. 7
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. Naveen Reddy and Jayant R. Haritsa. Analyzing plan diagrams of database query optimizers. In Proceedings of the 31st International Conference on Very Large Data Bases (VLDB), 2005. Florian Wolf, Michael Brendle, Norman May, Paul R. Willems, Kai-Uwe Sattler, and Michael Grossniklaus. Robustness metrics for relational query execution plans. Proceedings of the VLDB Endowment, 11(11):1360–1372, 2018. doi: 10.14778/3236187.3236191.
8