Query optimizers choose plans by minimizing a cost model over cardinality estimates, and cardinality-estimation (CE) research ranks estimators by q-error even though q-error is known to be an imperfect proxy for plan quality. A 2026 analysis (Mandarapu and Kunkunuru, arXiv:2606.15600) modeled plan selection as an argmin over a piecewise-linear cost landscape under i.i.d. Gaussian log-cardinality errors of scale σ, and proved two endpoint theorems: at small σ a per-query condition number κ governs regret, and in the σ → ∞ limit the expected regret converges to ACS_∞(q) = Σ_k r_k π_k, where r_k are true plan cost-ratios and π_k are cardinality-independent combinatorial selection probabilities. Deployed estimators, however, operate at finite σ, where a cardinality-dependent correction to π_k remains and is explicitly left as an open problem. This record states that open problem: characterize the expected plan regret at finite, practically relevant error magnitudes — equivalently the finite-σ correction to the selection probabilities — with quantitative validity bounds, and determine where the small-error condition-number regime crosses over to the large-error average-case regime, including the cost-model dependence of that crossover. The two sub-questions serve one objective: a finite-error account of plan regret bridging the two proven endpoint theories.

Background

A cardinality estimator predicts the size of a (sub-)query result, and the query optimizer feeds these estimates to a cost model to choose a join order and physical operators. The standard accuracy metric is q-error, max(ĉ/c, c/ĉ) between an estimate ĉ and the true cardinality c. It is well documented that large q-error improvements need not yield better plans: Leis et al. (PVLDB 2015) showed cardinality-estimation error is the dominant cause of poor plans on their Join Order Benchmark, and Lee et al. (PVLDB 2023) reached similar conclusions by injecting estimation errors in Microsoft SQL Server. Moerkotte, Neumann, and Steidl (PVLDB 2009) proved the main positive theoretical link: if every sub-expression estimate has q-error at most some bound, the chosen plan's cost is within a corresponding (loose) factor of optimal. Haritsa's line of work on robust query processing (PVLDB 2020) defines the worst-case counterpart, maximum sub-optimality MSO(q) = max_k r_k, and plan diagrams — partitions of selectivity/cardinality space into regions where each plan is optimal (Harish, Darera, and Haritsa, PVLDB 2008) — supply the geometric picture. A separate robust-optimization line (Wolf et al., PVLDB 2018; PARQO, PVLDB 2024; PAR2QO, PVLDB 2025) integrates a fixed plan's cost over a cardinality region to select robust plans, i.e., it changes the selection rule rather than analyzing the standard optimizer. The P-error metric (Negi et al., PVLDB 2021), which grades an estimator by the cost of the plans it induces rather than by estimate accuracy, and the STATS-CEB benchmark — a cardinality-estimation benchmark over the STATS database whose evaluation shipped several trained learned estimators (Han et al., PVLDB 2022) — made the empirical comparison of estimators by plan quality routine, and evaluation methodology itself has since been scrutinized (Rashedi and Moerkotte, PVLDB 2025; Izenov et al., SIGMOD 2024 proposed the L1-error surrogate). Into this landscape, Mandarapu and Kunkunuru (arXiv:2606.15600, June 2026) model a query q as a set of valid plans P_1, …, P_K whose costs under the true cardinality vector c are C_k(c) = Σ_{S∈I_k} c_S, the sum of true cardinalities over the plan's internal (join-)node subsets S, each plan with its set system I_k (this output-size-based cost is the paper's C_out cost model). The optimizer picks k̂ = argmin_k C_k(ĉ) from noisy estimates log ĉ_S = log c_S + ε_S with ε_S ~ N(0, σ²) i.i.d., and plan regret is ρ(ĉ) = C_k̂(c)/C_k*(c), the chosen plan's true cost relative to the true optimum; r_k = C_k(c)/C_k*(c) is the query's cost-ratio spectrum. They prove a regime taxonomy. (i) Small errors: the distance δ to the nearest plan-switch boundary in L_∞ log-space (closed form δ = (1/2)ln(A/B) for two plans' non-shared node sums A, B) gives a condition number κ = 1/min δ that predicts regret (per-query Spearman ρ = 0.70 on STATS-CEB, 0.79 on JOB-light, a reduced variant of the Join Order Benchmark on the IMDB schema), with predictive power decaying to zero as σ grows. (ii) Large errors: the average-case sub-optimality ACS_∞(q) = lim_{σ→∞} E_ε[ρ(ĉ)] predicts which queries are regret-prone (ρ ≈ 0.54 on STATS-CEB versus ≈ 0.05 for q-error; 0.42 versus −0.16 for real PostgreSQL runtime regret), and (iii) the worst case is Haritsa's MSO. The central structural result is a limit law: as σ → ∞ the optimizer's choice converges to the cardinality-free minimax-rank rule k̂ → argmin_k max_{S∈I_k} ε_S, so ACS_∞(q) = Σ_k r_k π_k factorizes into a cardinality part (the cost-ratio spectrum) and a purely combinatorial part (selection probabilities π_k determined by the plan set systems). Their own validation, however, shows the limit is approached only gradually: the cardinality-aware and cardinality-free estimates of ACS correlate 0.985 at σ = 8, 0.990 at σ = 15, and 0.994 at σ = 30, and deployed estimators on STATS-CEB sit at median per-subset q-error from roughly 2 to 10^5 — finite σ, where a cardinality-dependent correction to π_k persists. The unresolved target is the finite-σ middle of this theory.

Problem Statement

Under the setting of Mandarapu and Kunkunuru (arXiv:2606.15600): a query q has valid plans P_1, …, P_K with internal-node set systems I_k; under a true cardinality vector c the plan costs are C_k(c) = Σ_{S∈I_k} c_S (the C_out cost model); estimates satisfy log ĉ_S = log c_S + ε_S with ε_S ~ N(0, σ²) i.i.d.; the optimizer chooses k̂ = argmin_k C_k(ĉ) and regret is ρ(ĉ) = C_k̂(c)/C_k*(c). Two endpoint results are proven: the small-σ local theory, in which the true-point condition number κ = 1/min_{P'} δ with δ = (1/2)ln(A/B) predicts regret (A and B are the true-cardinality sums over the non-shared internal nodes of the optimal plan and its nearest alternative P'), and the σ → ∞ limit law ACS_∞(q) = Σ_k r_k π_k, where r_k = C_k(c)/C_k*(c) is the true cost-ratio of plan P_k, in which the selection probabilities π_k are cardinality-independent and purely combinatorial. The open problem is the finite-σ middle that deployed estimators inhabit (on STATS-CEB, released estimators have median per-subset q-error from roughly 2 to 10^5):

(1) Characterize the expected regret E_{σ,c}[ρ(ĉ)] at finite σ — equivalently, the finite-σ selection probabilities P_{σ,c}(k̂ = k) or the cardinality-dependent correction Δ(q, σ, c) in E_{σ,c}[ρ] = Σ_k r_k π_k + Δ(q, σ, c) — with quantitative validity bounds.

(2) As an integral part of the same finite-error account, determine the crossover location: the error scale σ_c at which the small-error condition-number regime gives way to the average-case regime — the σ beyond which κ loses predictive power and ACS_∞ gains it — including how σ_c depends on the cost model and optimizer (the source establishes the regimes under C_out and confirms survival on PostgreSQL runtime, but leaves the exact crossover cost-model-dependent).

The common objective of (1) and (2) is a finite-error theory of plan regret that predicts regret at the error magnitudes where real estimators operate, closing the gap between the two proven endpoint theories. (1) and (2) are jointly posed: (2) builds on the finite-σ correction of (1), and its dependence on the cost model and optimizer is not supplied by (1) alone, which is posed under C_out. The source's validation conventions (STATS-CEB and JOB-light with released estimators, seeded Monte-Carlo reference for E_ε[ρ]) are public.

References

  1. Mandarapu, M. and Kunkunuru, S. (2026). When Does q-error Predict Plan Regret? Three Regimes of Cardinality-Estimation Error. arXiv:2606.15600, DOI 10.48550/arXiv.2606.15600. https://arxiv.org/abs/2606.15600
  2. Mandarapu, M. and Kunkunuru, S. (2026). Filtered ANN as a Phase Transition: When Selectivity-Estimation Error Causes Plan Regret. arXiv:2606.16341, DOI 10.48550/arXiv.2606.16341. https://arxiv.org/abs/2606.16341
  3. Leis, V., Gubichev, A., Mirchev, P., Boncz, P., Kemper, A., and Neumann, T. (2015). How Good Are Query Optimizers, Really? Proceedings of the VLDB Endowment 9(3), 204-215, DOI 10.14778/2850583.2850594. https://doi.org/10.14778/2850583.2850594
  4. Leis, V., Gubichev, A., Mirchev, P., Boncz, P., Kemper, A., and Neumann, T. (2025). Still Asking: How Good Are Query Optimizers, Really? Proceedings of the VLDB Endowment 18(12), 5531-5536, DOI 10.14778/3750601.3760521. https://doi.org/10.14778/3750601.3760521
  5. Moerkotte, G., Neumann, T., and Steidl, G. (2009). Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors. Proceedings of the VLDB Endowment 2(1), 982-993, DOI 10.14778/1687627.1687738. https://doi.org/10.14778/1687627.1687738
  6. Haritsa, J. R. (2020). Robust Query Processing. Proceedings of the VLDB Endowment 13(12), 3425-3428, DOI 10.14778/3415478.3415561. https://doi.org/10.14778/3415478.3415561
  7. Han, Y., Wu, Z., Wu, P., Zhu, R., Yang, J., Tan, L. W., Zeng, K., Cong, G., Qin, Y., Pfadler, A., Qian, Z., Zhou, J., Li, J., and Cui, B. (2022). Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation. Proceedings of the VLDB Endowment 15(4), 752-765, DOI 10.14778/3503585.3503586. https://doi.org/10.14778/3503585.3503586
  8. Lee, K., Dutt, A., Narasayya, V., and Chaudhuri, S. (2023). Analyzing the Impact of Cardinality Estimation on Execution Plans in Microsoft SQL Server. Proceedings of the VLDB Endowment 16(11), 2871-2883, DOI 10.14778/3611479.3611494. https://doi.org/10.14778/3611479.3611494
  9. Negi, P., Marcus, R., Kipf, A., Mao, H., Tatbul, N., Kraska, T., and Alizadeh, M. (2021). Flow-Loss: Learning Cardinality Estimates That Matter. Proceedings of the VLDB Endowment 14(11), 2019-2032, DOI 10.14778/3476249.3476259. https://doi.org/10.14778/3476249.3476259
  10. Wolf, F., Brendle, M., May, N., Willems, P. R., Sattler, K., and Grossniklaus, M. (2018). Robustness Metrics for Relational Query Execution Plans. Proceedings of the VLDB Endowment 11(11), 1360-1372, DOI 10.14778/3236187.3236191. https://doi.org/10.14778/3236187.3236191
  11. Harish, D., Darera, P. N., and Haritsa, J. R. (2008). Identifying Robust Plans through Plan Diagram Reduction. Proceedings of the VLDB Endowment 1(1), 1124-1140, DOI 10.14778/1453856.1453976. https://doi.org/10.14778/1453856.1453976
  12. Xiu, H., Agarwal, P. K., and Yang, J. (2024). PARQO: Penalty-Aware Robust Plan Selection in Query Optimization. Proceedings of the VLDB Endowment 17(13), 4627-4640, DOI 10.14778/3704965.3704971. https://doi.org/10.14778/3704965.3704971
  13. Xiu, H., Li, Y., Yang, Q., Agarwal, P. K., and Yang, J. (2025). PAR2QO: Parametric Penalty-Aware Robust Query Optimization. Proceedings of the VLDB Endowment 18(11), 4532-4545, DOI 10.14778/3749646.3749711. https://doi.org/10.14778/3749646.3749711
  14. Izenov, Y., Datta, A., Tsan, B., and Rusu, F. (2024). Sub-optimal Join Order Identification with L1-error. Proceedings of the ACM on Management of Data 2(1), 1-24, DOI 10.1145/3639272. https://doi.org/10.1145/3639272
  15. Rashedi, N. and Moerkotte, G. (2025). The Accuracy of Cardinality Estimators: Unraveling the Evaluation Result Conundrum. Proceedings of the VLDB Endowment 18(11), 3744-3756, DOI 10.14778/3749646.3749651. https://doi.org/10.14778/3749646.3749651
  16. Kamali, A., Kantere, V., Zuzarte, C., and Corvinelli, V. (2025). Robust Plan Evaluation Based on Approximate Probabilistic Machine Learning. Proceedings of the VLDB Endowment 18(8), 2626-2638, DOI 10.14778/3742728.3742753. https://doi.org/10.14778/3742728.3742753