技术摘要：q-error 何时能预测计划遗憾（Plan Regret）？

问题陈述

基数估计（Cardinality Estimation, CE）领域传统上使用 q-error ($\max(\hat{c}/c, c/\hat{c})$) 来对估计器进行排名。虽然 q-error 提供了一种最坏情况下的保证，即通过限制子表达式的最大误差来限制计划的次优性，但经验证据表明这种界限通常过于宽松且不切实际。具体而言，q-error 的大幅改善并不总能转化为更好的查询计划；反之，巨大的 q-error 也并不总是导致糟糕的计划。本文旨在解决的核心问题是：何时 q-error 能作为计划遗憾（即在真实基数下的最优计划与所选计划的成本比）的可靠代理指标，并识别当 q-error 失效时，哪种度量指标可以预测遗憾。

研究方法

作者将计划选择建模为对对数基数空间中分段线性成本景观（piecewise-linear cost landscape）的 $\text{argmin}$ 操作。他们分析了估计误差与计划遗憾在由误差量级 ($\sigma$) 定义的三种不同机制（regimes）之间的关系：

1. 小误差机制（Small-Error Regime）： 估计误差足够小，使得估计基数仍处于真实最优计划的“计划最优单元”（plan-optimality cell）内。

   • 度量指标： 每个查询的条件数 ($\kappa$)，定义为距离最近的计划切换边界（即最优计划的成本等于另一种备选计划成本的边界）的倒数。
   • 假设： 遗憾由局部几何结构决定；只有当误差足够小以使局部线性化成立时，$\kappa$ 才能预测遗憾。

2. 大误差机制（Large-Error Regime）： 估计误差较大（这是已部署的学习型估计器的典型特征），导致估计值落在成本景观中的任何单元内，远离真实的最优单元。

   • 度量指标： 平均情况次优性 ($ACS_\infty$)。其定义为当误差方差趋于无穷大时 ($\sigma \to \infty$)，预期遗憾的极限。
   • 假设： 在此机制下，局部量化指标如 $\kappa$ 和 q-error 变得不再具有信息量。相反，遗憾由特定查询的一个随机计划的“典型糟糕程度”决定，且该程度与具体的估计器无关。

3. 最坏情况机制（Worst-Case Regime）： 次优性的理论上限。

   • 度量指标： 最大次优性 (Maximum Sub-optimality, MSO)，定义为 $\max_k r_k$，其中 $r_k$ 是计划 $k$ 相对于最优计划的真实成本比。

作者推导出了一个极限律（limit law），表明 $ACS_\infty$ 可以表示为真实成本比谱（$\{r_k\}$）与与基数无关的组合权重 ($\pi_k$) 的加权和：
$$ACS_\infty(q) = \sum_{k} r_k \pi_k$$
这与使用最大权重（max-weighting）的 MSO 以及使用最近间隙权重（nearest-gap weighting）的 $\kappa$ 形成了对比。

实验设置

• 数据集： STATS-CEB（其中估计器已知是不准确的）和 JOB-light（IMDB 模式）。
• 估计器： 四种发布的估计器（BayesCard, DeepDB, FLAT, NeuroCard）以及原生的 DuckDB 优化器。
• 验证：
  • 合成数据： 通过注入不同 $\sigma$ 的误差来测试机制转换。
  • 真实世界： 将估计基数注入 PostgreSQL 13.1 中以测量实际运行时的遗憾，并将其与理论上的 $C_{out}$ 模型预测进行比较。
• 严谨性： 本研究使用了预注册决策规则，包括一个被拒绝的假设和一个记录在案的“近失（near-miss）”假设，以确保统计有效性。

关键结果

1. 小误差机制

• 条件数 $\kappa$ 能够强有力地预测计划遗憾（在 STATS-CEB 上 Spearman $\rho \approx 0.70$，在 JOB-light 上 $\rho \approx 0.79$）。
• 在此机制下，$\kappa$ 的表现优于 q-error。
• 随着误差量级 ($\sigma$) 的增加，$\kappa$ 的预测能力衰减至零，证实了其作为局部线性化工具的本质。

2. 大误差机制

• 在已部署的学习型估计器所处的机制中（中位数 q-error 为 2 到 $10^5$），q-error 对于预测查询级遗憾几乎没有信息量（$\rho \approx 0.05$）。
• $ACS_\infty$ 是更优的预测指标： 它在 STATS-CEB 上实现了 $\rho \approx 0.54$ 的 Spearman 相关系数，显著优于 q-error 和 $\kappa$（$\rho \approx 0.20$）。
• PostgreSQL 验证： 当针对实际 PostgreSQL 运行时进行测试时，$ACS_\infty$（纯粹从 $C_{out}$ 几何结构计算，无需查看数据库内容）能够以 $\rho = 0.42$ 预测运行时遗憾，而 q-error 则显示出负相关性（$\rho = -0.16$）。

3. 极限律

• 论文证明，当 $\sigma \to \infty$ 时，优化器的选择收敛于一个与基数无关的极小极大秩规则（minimax-rank rule）。
• $ACS_\infty$ 分解为真实成本比谱与仅由计划集合系统（plan set-system）决定的组合权重，这使其成为一种与估计器无关的查询难度度量。

主张与意义

本文谦逊地声称其贡献在于提供了对 “q-error 与计划成本” 紧张关系的概念与实证调和，而非提出一种新的估计器。

• 依赖机制的预测： 论文确立了没有任何单一标量指标（如 q-error）可以跨所有误差量级预测计划遗憾。预测能力完全取决于误差机制：
  • 小误差： 由条件数 ($\kappa$) 预测。
  • 大误差： 由平均情况次优性 ($ACS_\infty$) 预测。
  • 最坏情况： 由最大次优性 (MSO) 限制。
• 几何洞察： 这三个指标被揭示为对同一底层计划成本比谱 ($\{r_k\}$) 的不同加权方式。
• 实际意义： 对于运行在大误差机制中的已部署学习型估计器，q-error 是衡量计划质量的糟糕指标。$ACS_\infty$ 可作为最坏情况鲁棒查询优化的伴侣，提供一种平均情况下的度量，用以识别哪些查询由于其计划成本几何结构而天生具有“易产生遗憾（regret-prone）”的特性，无论使用何种特定的估计器。

作者强调，其贡献在于刻画了精度指标何时追踪计划质量，并引入了 $ACS_\infty$ 作为一种查询级难度度量，并通过严格的预注册和真实世界运行时测试进行了验证。