カーディナリティ推定とヒストグラム・スケッチ

カーディナリティ推定とは何を計算しているのか

オプティマイザがプランを選ぶ唯一の数値的根拠は、各演算子が何行を出力するかの推定値です。これをカーディナリティ推定と呼びます。WHERE や JOIN を通すと行数がどう絞られるか、その比率が**選択率（selectivity, 0〜1）**で、推定出力行数は「入力行数 × 選択率」で計算されます。コスト見積もり（→ クエリオプティマイザの内部）は最終的にこの行数推定の上に乗るため、推定が外れれば最適なはずの計画が崩れます。本稿は、この推定を支える分布の要約構造とアルゴリズムを内部から追います。

列分布を要約する3つの統計

実データの全分布を保持するのは非現実的なので、ANALYZE は各列の分布を3種類のコンパクトな要約に圧縮します。

肝心なのは三者が役割分担している点です。MCV が偏りの大きい値を吸収し、ヒストグラムは MCV を除いた残りの値だけを対象に作られます。これにより「数件の超頻出値がヒストグラム区間を歪める」事態を防ぎ、両者を組み合わせて全体の選択率を再構成します。

等値条件：n_distinct と MCV

等値条件 col = v の選択率は、まず MCV リストに v があるかで分岐します。

if v が MCV にある:
    選択率 = その値の MCV 頻度（実測比率そのもの）
else:
    残余選択率 = 1 − (MCV 全体の頻度合計)
    残余の異なる値数 = n_distinct − (MCV 件数)
    選択率 = 残余選択率 ÷ 残余の異なる値数   # 残りは一様と仮定

v が最頻値なら実測比率をそのまま使えるので高精度です。MCV にない値は「残りの確率質量を、残りの distinct 値で均等割り」という一様仮定で近似します。ここで n_distinct の精度が選択率を直接左右します。n_distinct を 2 倍に誤れば、非 MCV の等値選択率は半分にずれます。

distinct 推定：なぜ HyperLogLog なのか

n_distinct は厄介な統計です。合計・最大は逐次集計できますが、異なる値の個数を正確に数えるには原理的に全ユニーク値を覚える必要があり、メモリは distinct 数に比例します。数億行・数千万 distinct では現実的でありません。そこで近似に確率的スケッチ（→ ブルームフィルタと確率的データ構造）の一種、HyperLogLog（HLL） を使います。

着想は「ハッシュ値の先頭に並ぶ 0 の最大数」を見ることです。一様なハッシュ値で先頭 0 が k 個続く確率は 2^-(k+1) なので、観測した最大先頭 0 数が大きいほど多くの異なる値を見たと推測できます。素朴に最大値1つだけ見ると分散が大きいため、HLL は値を m 個のバケットに振り分け、各バケットの最大先頭 0 数を保持し、それらを調和平均で束ねて分散を抑えます。

m 個のレジスタを用意（典型: m = 2^14 = 16384）
各値 x について:
    h = hash(x)
    先頭 p ビットでレジスタ番号 j を決める
    残りビットの先頭 0 の数 + 1 を rank とする
    register[j] = max(register[j], rank)
推定 distinct ≈ 補正係数 × m^2 ÷ Σ 2^-register[j]

この構造の効きどころは3点です。第一に、メモリは distinct 数に依存せずレジスタ数だけで固定（16384 レジスタなら約 12 KB）。第二に、標準誤差は約 1.04 / sqrt(m) で、m = 16384 なら誤差およそ 0.8%。第三に、2つの HLL は同じレジスタ位置の最大値を取るだけでマージ可能で、これは分散集計やパーティション統計の合算に直結します。COUNT(DISTINCT) の近似（PostgreSQL の拡張、Redis の PFCOUNT、各種 DWH の APPROX_COUNT_DISTINCT）の中核がこれです。

範囲条件：等深ヒストグラム

col < v や col BETWEEN a AND b の選択率はヒストグラムで推定します。ヒストグラムには2方式あります。

主要 RDB が採る等深ヒストグラムは、ソートした値を等頻度に区切る境界（バケット境界）の列だけを保持します。各バケットが全体の 1/N を担うので、範囲 col < v の選択率は「v より下に完全に収まるバケット数 × 1/N」に、v をまたぐバケットの寄与をバケット内一様仮定で按分して加えます。バケット内では値が均等に分布するとみなし、v がバケットの何割の位置かで部分寄与を線形補間するわけです。

等深が等幅より優れるのは、偏った分布でも各バケットが同じ行数を持つため、密な領域に自動的に細かい境界が割り当たる点です。代償として、1バケット内に強い山がある（例：ある一点に集中）と一様仮定が破れ誤差が出ますが、そうした極端な値は先に MCV へ抜けるため実害は抑えられます。

誤差の主因：独立性仮定とその崩壊

単一列の推定が正確でも、複数条件の合成で誤差が生まれます。多くのオプティマイザは WHERE a = 1 AND b = 2 の選択率を、各列の選択率の積で近似します。

sel(a=1 AND b=2) ≈ sel(a=1) × sel(b=2)   # 列 a と b は独立と仮定

これは a と b が統計的に独立なら正しいものの、相関があると崩壊します。典型は 都道府県 = '東京都' AND 市区町村 = '渋谷区'。渋谷区は東京都にしか存在しないため、sel(市区町村='渋谷区') は既に都道府県を含意しています。独立仮定の積はこれを二重に掛けて選択率を過小評価し、推定行数を実際より桁で小さく見積もります。結果、本来 Hash Join が適切な場面で Nested Loop を選ぶ、といった破綻が起きます。

緩和策は**複数列統計（拡張統計）**です。相関する列の組について、組み合わせの n_distinct や依存度を別途収集し、独立仮定の積ではなく実測寄りの選択率を使わせます（PostgreSQL の CREATE STATISTICS、他 RDB の複合ヒストグラムやカラムグループ統計）。ただし全列の組み合わせは爆発するため、相関が分かっている列に限って明示的に作るのが定石です。

推定が外れたときの読み方

統計の誤差は EXPLAIN ANALYZE（→ クエリ最適化）の推定行数（rows）と実測行数（actual rows）の乖離に現れます。読む順は、まずプラン木の葉に近いノードで両者が大きく食い違う箇所を探すこと。誤差は上へ増幅するので、最上位の乖離より最下流の乖離が根本原因に近いからです。

対処の優先順位は、第一に ANALYZE（→ 統計の鮮度を保つ／インデックス）で古い統計を更新、第二に相関列への拡張統計の付与、第三に統計の粒度（ヒストグラムバケット数や統計対象サンプル数）の引き上げです。実行計画ヒントによる結合方式の固定は、推定誤差そのものを直さないため最後の手段にとどめます。カーディナリティ推定は「分布をいかに少ないバイトで正確に要約するか」という近似アルゴリズムの問題であり、その限界を理解することが、壊れた計画を原理から直す近道になります。