SQLチューニングの世界では、インデックス設計やSQLリライト以上に重要で、かつ見落とされがちな領域があります。それがカーディナリティ推定（Cardinality Estimation）です。
データベースのクエリオプティマイザは、実行計画を作る際に「各クエリステップで何行返ってくるか」を推定します。この推定値が実データとかけ離れると、最適化が崩れ、本来指数関数的に増えるべきでないコストが爆発します。
つまり、SQLが遅い原因の多くは「推定誤差」なのです。
■ カーディナリティ推定とは？
DBが実行計画を選ぶ際、以下を予測します：
- WHERE条件で何行残るか
- JOIN後に何行になるか
- GROUP BYで何グループにまとまるか
これらの推定はデータ分布統計（Statistics）を基に計算されます。
例：PostgreSQLのEXPLAINでの比較
Rows (estimated): 100 Rows (actual): 50,000 この差が「誤差」であり、誤差が大きいほど実行計画は破綻します。
■ 代表的な推定アルゴリズム
① 独立性仮定（Independence Assumption）
最も基本的で、最も壊れやすい仮定：
複数条件は互いに独立であるとみなす。
WHERE gender = 'M' AND pref = 'Tokyo' 実際には性別と地域には強い偏りがあるのに、DBは：
[ P(M AND Tokyo) = P(M) \times P(Tokyo) ]
と計算する。
② 均等分布（Uniform Distribution Assumption）
値が均等に分布していると仮定する。
現実：
- 売上の90%がトップ10商品
- 月末にデータが偏る
これは均等ではありません。
③ ヒストグラム（MCV / Frequency Histogram）
PostgreSQLやOracleは、代表値（Most Common Values）や値レンジ（Histogram）を持ち、偏りを部分的に反映します。
しかし、それでも複合条件やJOINでは誤差が積み上がるため不完全です。
■ 推定誤差が実行計画に与える致命的影響
① Nested Loop が選ばれるべきでない場面で選ばれる
例：
estimated rows: 100 actual rows: 100000 この誤差だと、オプティマイザは
「小さい表だからNested Loopが良いはず」
と安易に判断します。
→ 実際は10万行で爆死（指数関数コスト）
② Hash Join を選ばず、Seq Scanが乱発される
Hashが作れないと思われたら、低品質の実行計画が選ばれます。
③ GROUP BY で誤ったメモリ割り当てが行われる
予測が小さすぎると、Hash Aggregate が spill（ディスク退避）し、性能が激落ちします。
■ よくある推定誤差の原因
① 統計情報が古い
ANALYZE table_name; 更新直後のデータを扱う場合、大きくズレることがある。
② WHERE 条件の相関（Correlation）が無視される
WHERE sex = 'F' AND perfume_favorite = true 独立ではない条件の組み合わせが誤差を生む。
③ 複合インデックスが無い場合の誤差
単一カラムのヒストグラムでは、複合条件を正しく扱えない。
④ サブクエリでの選択度推定が破綻（特にNOT EXISTS）
WHERE NOT EXISTS (...) これは推定が極めて難しい。
■ PostgreSQLでの実際のEXPLAIN分析例
例：誤差が3桁以上に広がったパターン
EXPLAIN ANALYZE SELECT * FROM orders o JOIN customers c ON o.customer_id = c.id WHERE c.region = 'Kanto' AND c.gender = 'F'; 結果例：
Rows (estimated): 120 Rows (actual): 45,391 → Nested Loop が選ばれ、1秒のはずが50秒超え。
■ 推定誤差の改善方法
① 統計ターゲットの引き上げ（PostgreSQL）
ALTER TABLE customers ALTER COLUMN region SET STATISTICS 2000; ANALYZE customers; 高頻度アクセスのカラムは「統計精度を上げる」のが王道。
② 拡張統計の導入（Postgres 10+）
相関関係を学習できる。
CREATE STATISTICS stat_region_gender (dependencies) ON region, gender FROM customers; ANALYZE customers; これにより誤差が大きく改善される。
③ 複合インデックスの検討
CREATE INDEX idx_region_gender ON customers(region, gender); 推定精度の向上に直結。
④ クエリ rewrite（条件順序の変更）
推定誤差が小さい条件からフィルタするように書き換えると良い。
■ 推定誤差の数理的考察
推定誤差は、以下のような確率モデルのズレによって発生します。
[ EstimatedRows = TotalRows \times Selectivity ]
実際：
[ ActualRows = TotalRows \times (Selectivity + ε) ]
この誤差 ( ε ) が累積し、JOINが増えるほど指数的に膨張します。
JOIN深度 n の誤差：
[ Error \approx \prod_{i=1}^{n} (1 + ε_i) ]
小さなズレが多段JOINで巨大化する理由がここにあります。
■ まとめ
- カーディナリティ推定はSQL最適化の最も重要な基盤
- 誤差はNested Loop暴走・Hash失敗など深刻な性能劣化を招く
- 統計情報の精度・拡張統計・複合インデックスが改善の鍵
- 多段JOINでは誤差が指数的に膨らむため要注意
「SQLが遅い時、SQLを疑う前に推定誤差を疑え」 これはDBAの基本的な考え方です。
