ハッシュ結合の内部：グレース法とハイブリッドハッシュ

メモリに載る前提が崩れるとどうなるか

Hash Join は等値結合の大集合に最も強い方式で、計算量は両表を1回ずつ読む O(N + M) です。ただしこの速さは「Build 側のハッシュテーブルが作業メモリに収まる」という前提に立っています。Build 側を R（行数 M）、Probe 側を S（行数 N）とすると、基本形は次の2フェーズです。

-- Build フェーズ: 小さい側 R を全部メモリに載せる
for each row r in R:
    HashTable[ hash(r.key) ].add(r)

-- Probe フェーズ: 大きい側 S を1行ずつ照合
for each row s in S:
    for each r in HashTable[ hash(s.key) ]:
        if r.key == s.key: emit (r, s)

問題は、R が work_mem（PostgreSQL）や sort_area_size 相当の作業メモリより大きい場合です。素朴に載せようとすればスワップで壊滅的に遅くなる。そこで RDB は、Build 側がメモリに載らないと判断した時点で Grace ハッシュ結合へ切り替えます。

Grace ハッシュ結合：分割統治で必ずメモリに載せる

Grace 法の発想は単純です。「全体が載らないなら、載るサイズの小片に分割してから結合すればよい」。両表を同じハッシュ関数 h1 で B 個のパーティションに振り分け、いったんディスクに書き出します（これがスピル）。

-- パーティショニング・パス（両表それぞれ1回読む）
for each row r in R:  書き出す: PartR[ h1(r.key) mod B ]
for each row s in S:  書き出す: PartS[ h1(s.key) mod B ]

-- 結合パス（パーティション i ごとに独立に処理）
for i in 0..B-1:
    HashTable ← PartR[i] をメモリに載せる   -- 小片なので載る
    for each s in PartS[i]:
        probe して一致を emit

正しさの核心は、結合キーが等しい行は h1 が同値なので必ず同じ番号のパーティション同士に入る、という点です。だから PartR[i] と PartS[i] だけ突き合わせれば十分で、異なる番号のペア（PartR[i] と PartS[j]、i が j と異なる）は一致しえないため処理しなくてよい。これが N×M の総当たりを避けられる理由です。

I/O コスト：スピル1段でデータを2回多く触る

Grace 法の代償は明確で、両表をいったんディスクへ書き、また読むぶんの I/O です。R と S のページ数を |R|・|S| とすると、

• 読み（パーティショニング時）: |R| + |S|
• 書き（スピル）: |R| + |S|
• 読み（結合パス）: |R| + |S|

合計 3 × (|R| + |S|) ページの I/O になります。in-memory なら |R| + |S|（1回読むだけ）で済むので、スピル1段あたりおおむね追加で 2×(|R|+|S|) を払う計算です。だから Hash Join が遅いと感じたら、まず「Build がメモリに載りきらずスピルしているか」を疑うのが定石になります。

ハイブリッドハッシュ結合：第1パーティションを常駐させる

Grace 法は「Build がわずかにメモリを超える」ケースでも、律儀に全パーティションをスピルしてしまうのが無駄です。Hybrid Hash Join はこの帯域を最適化します。発想は「余っているメモリで第1パーティション（partition 0）だけは最初からメモリに保持し、ディスクを経由させない」こと。

-- Build: partition 0 はメモリ常駐、残りはスピル
for each row r in R:
    p = h1(r.key) mod B
    if p == 0: HashTable[r] に直接入れる        -- 常駐
    else:      PartR[p] へ書き出す               -- スピル

-- Probe: partition 0 に当たる行は即照合（スピルしない）
for each row s in S:
    p = h1(s.key) mod B
    if p == 0: HashTable を probe して emit        -- ディスク不要
    else:      PartS[p] へ書き出す                 -- 後で処理

-- 残りパーティション 1..B-1 を Grace と同様に処理

partition 0 に入る行は書き出しも読み戻しもゼロになります。Build 側のうち partition 0 に当たる割合を f とすると、その f 分の I/O が丸ごと消える。メモリが「全部は載らないが、半分は載る」ような状況で効果が大きく、メモリが潤沢なら f → 1（実質 in-memory）、メモリが枯渇すれば f → 0（純粋な Grace）へと連続的に縮退するのが Hybrid の美点です。多くの商用 RDB・PostgreSQL の Hash Join はこの Hybrid 系を採用しています。

再帰分割：パーティションがなお載らないとき

h1 で分けても、データの偏り（同一キーの大量重複、ハッシュの片寄り）で特定パーティションだけ巨大化し、依然メモリに載らないことがあります。このとき RDB は、そのパーティションに対して別のハッシュ関数 h2 を使い、さらに細かく再分割します。これが再帰分割（recursive partitioning）です。

重要なのは h1 と異なる関数を使う点です。同じ h1 で割り直しても、すでに h1 値が同じ行ばかりなので分かれません。独立な h2 を用いて初めて分散します。再帰の各段で当該パーティションを読み・書き・読みするため、スピルが k 段に達すると I/O はおおむね (2k+1) × 該当データ量 と段数に線形で増えていきます。つまりスピル段数こそがコストの支配項です。

実務での読み方

PostgreSQL の EXPLAIN ANALYZE では、Hash ノードに Buckets・Batches・Memory Usage が出ます。Batches が 1 なら in-memory、2 以上ならスピル（Grace/Hybrid）が起きた証拠で、値が大きいほど多段分割を意味します。work_mem を増やして Batches が 1 に落ちれば、3(|R|+|S|) の I/O が |R|+|S| に減り、桁で速くなることがあります。ただし work_mem はクエリ・ソート単位に確保されるため、増やしすぎは同時実行時のメモリ枯渇を招く点に注意します。スピルの読み書きはバッファプールを経由せず一時ファイルへ直接行くため、設計や調整の指針も通常のページキャッシュとは別に考える必要があります。詳しい原理面はクエリ最適化もあわせて参照してください。

まとめ

• in-memory ⊃ Hybrid ⊃ Grace は、作業メモリに応じて連続的に縮退する一連の戦略。等値結合の正しさは「等しいキーは同じパーティションに入る」性質で担保される。
• Grace は両表をハッシュで分割してスピルし、PartR[i] と PartS[i] だけを突き合わせる。スピル1段で I/O は |R|+|S| から約 3(|R|+|S|) に増える。
• Hybrid は partition 0 をメモリ常駐させ、その分の書き戻し I/O を丸ごと省く。メモリが「ぎりぎり足りない」帯域で最も効く。
• 1パーティションが偏って載らなければ、独立な別ハッシュで再帰分割する。コストはスピル段数に線形で増える。
• 実行計画では Batches > 1 がスピルの合図。work_mem 調整と結合前の行数削減が効く一方、極端なキー偏りはハッシュでは救えない。