テクニカル・サマリー：q-errorはいつプランのレグレット（後悔）を予測できるのか？

問題提起

カーディナリティ推定（CE）の分野では、伝統的に推定器の評価に q-error ($\max(\hat{c}/c, c/\hat{c})$) が用いられてきた。q-errorは、部分式における最大誤差を抑えればプランの劣最適性を抑えられるという最悪ケースの保証を提供するが、経験的な証拠によれば、この境界はしばしば緩慢で実用的ではないことが示唆されている。具体的には、q-errorの大幅な改善が必ずしもより良いクエリプランの改善には結びつかず、逆に大きなq-errorが必ずしも悪いプランをもたらすわけでもない。本研究が取り組む核心的な問題は、「いつ」q-errorが信頼できるプラン・レグレット（真のカーディナリティ下での最適プランに対する選択されたプランのコスト比）のプロキシ（代理指標）となるのかを特定すること、およびq-errorが機能しない場合にレグレットを予測する指標が何であるかを特定することである。

手法

著者らは、プラン選択を（対数カーディナリティ空間における）区分線形コスト景観上の $\text{argmin}$ 操作としてモデル化している。彼らは、推定誤差（$\sigma$）の大きさに定義される3つの異なるレジーム（領域）にわたって、推定誤差とプラン・レグレットの関係を分析している。

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): 劣最適性の理論的な上限。

   • 指標: 最大劣最適性 (MSO)。これは $\max_k r_k$ （ここで $r_k$ はプラン $k$ の最適プランに対する真のコスト比）として定義される。

著者らは、$ACS_\infty$ が、カーディナリティに依存しない組合せ論的な重み（$\pi_k$）を用いて、真のコスト比スペクトル ($\{r_k\}$) の加重和として表現できるという 極限法則 (limit law) を導出している：
$$ACS_\infty(q) = \sum_{k} r_k \pi_k$$
これは、最大値による重み付けを行う MSO や、最近接ギャップによる重み付けを行う $\kappa$ とは対照的である。

実験設定

• データセット: STATS-CEB（推定器が不正確であることが判明しているもの）および JOB-light (IMDB スキーマ)。
• 推定器: 4つの公開されている推定器 (BayesCard, DeepDB, FLAT, NeuroCard) およびネイティブの DuckDB オプティマイザ。
• 検証:
  • 合成データ: レジームの遷移をテストするために、誤差注入（varying $\sigma$）を行う。
  • 実世界データ: 推定されたカーディナリティを PostgreSQL 13.1 に注入し、実際の実行時レグレットを測定し、理論的な $C_{out}$ モデルの予測と比較する。
• 厳密性: 統計的妥当性を確保するため、拒絶された仮説や記録に残された「ニアミス」を含む 事前登録された決定ルール (pre-registered decision rules) を用いている。

主な結果

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$ が優れた予測因子である: $ACS_\infty$ は、STATS-CEB においてクエリ・レグレットとの Spearman 相関 $\rho \approx 0.54$ を達成し、q-error や $\kappa$ ($\rho \approx 0.20$) を大幅に上回った。
• PostgreSQL による検証: 実際の PostgreSQL の実行時間に対してテストした際、$ACS_\infty$（DBを見ることなく $C_{out}$ の幾何学のみから計算されたもの）は $\rho = 0.42$ で実行時レグメントを予測したが、q-error は負の相関 ($\rho = -0.16$) を示した。

3. 極限法則

• 論文では、$\sigma \to \infty$ となるにつれ、オプティマイザの選択がカーディナリティに依存しないミニマックス・ランク・ルールに収束することを証明している。
• $ACS_\infty$ は、真のコスト比スペクトルと、プランの集合系によって決定される組合せ論的な重みに分解される。これにより、$ACS_\infty$ は 推定器に依存しない クエリの難易度尺度となる。

主張と意義

本論文は、新しい推定器を提案することではなく、「q-error vs プラン・コスト」の緊張関係を 概念的および経験的に 解明することを控えめに主張している。

• レジーム依存の予測: 単一のスカラー指標（q-error のようなもの）では、すべての誤差の大きさにおいてプラン・レグレットを予測することはできないということを本論文は確立している。予測力は完全に誤差のレジームに依存する：
  • 小誤差: 条件数 ($\kappa$) によって予測される。
  • 大誤差: 平均ケースの劣最適性 ($ACS_\infty$) によって予測される。
  • 最悪ケース: 最大劣最適性 (MSO) によって境界づけられる。
• 幾何学的洞察: これら3つの指標は、同じ基礎となるプラン・コスト比スペクトル ($\{r_k\}$) に対する異なる重み付けであることが明らかになった。
• 実用的な意味合い: デプロイされた学習済み推定器（大誤差レジームで動作するもの）にとって、q-error はプランの質を示す指標としては不適切である。$ACS_\infty$ は、最悪ケースに頑健なクエリ最適化の相棒として、特定の推定器の使用に関わらず、プランのコスト幾何学によって本質的に「レグレットが発生しやすい」クエリを特定するための、平均的な難易度尺度として機能する。

著者らは、自らの貢献が、精度指標がいつプランの質を追跡するかを特性化し、事前登録された厳格な手続きと実世界の実行時テストを通じて検証された $ACS_\infty$ を、クエリレベルの難易度尺度として導入した点にあると強調している。