q-error并非总是能预测查询计划错误，三种误差情形下表现各异。
When Does q-error Predict Plan Regret? Three Regimes of Cardinality-Estimation Error
- 根据误差大小划分三种情形，用几何特性解释计划后悔值
- 大误差时q-error几乎无用，而新指标ACS-infinity相关性达0.54
- 适合关注查询优化鲁棒性的数据库研究人员阅读
基数估计研究常以q-error排名估计器，但其作为查询计划质量代理并不完善。本文通过将计划选择建模为分段线性成本景观下的最小化问题，发现计划后悔值（即所选计划相对于真实基数最优计划的成本差）受成本几何结构在不同误差区间下的调控。第一，在小误差下，真实点条件数κ可预测后悔值，优于q-error，但随误差增长预测力衰减至零；第二，在大误差（实际学习型估计器工作范围）下，与估计器无关的平均情况次优度度量ACS-infinity可预测高后悔查询（STATS-CEB上斯皮尔曼相关性~0.54），而q-error在查询层面近乎无信息（相关性~0.05）；第三，最坏情况对应哈里塔萨最大次优性（MSO）。三者构成单一成本比谱，具不同加权。我们证明了极限律ACS-infinity = sum_k r_k pi_k，其中权重为基数无关组合权重，并在STATS-CEB和JOB-light数据集上，使用四个公开释放的估计器及预注册决策规则验证所有结论，且在真实PostgreSQL运行时确认ACS-infinity可预测后悔，而q-error不能。贡献为概念与实证性：提供对最坏情况鲁棒查询优化的平均情况补充，以及对准确率指标何时追踪计划质量的刻画，非提出新估计器。代码与完整预注册公开。
原文摘要 · Abstract (English)
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 kappa 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-infinity predicts which queries are regret-prone (Spearman rho ~ 0.54 on STATS-CEB), while q-error is nearly uninformative at the query level (rho ~ 0.05). (iii) The worst case is Haritsa's maximum sub-optimality (MSO). The three are one cost-ratio spectrum under three weightings. We prove a limit law ACS-infinity = sum_k r_k pi_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-infinity 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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。