集約とソートの外部アルゴリズム(外部ソート・スピル)

メモリに載らない並べ替えという問題

ORDER BY・GROUP BY・DISTINCT・マージ結合の前処理など、データベースは至るところで「全体を並べ替える／まとめる」処理を行います。問題は、対象が work_mem（PostgreSQL）や sort_area_size 相当の作業メモリより大きいときです。素朴に全件をメモリへ載せようとすればスワップで壊滅的に遅くなる。そこで使われるのが、データの大半をディスクに置いたまま整列・集約を完結させる外部アルゴリズムです。本稿は外部ソート（多方向マージ・置換選択）とハッシュ集約のスピルを、I/O を最小化する原理から解説します。

ここで言う「スピル（spill）」とは、メモリに収まらない中間データを一時ファイルへ書き出すことを指します。スピルが起きた瞬間から処理は CPU 律速ではなく I/O 律速になり、何回データを読み書きするかが速度を決めます。

外部ソート：分割して整列し、まとめて併合する

外部ソートは二段構えです。第一段がラン生成（run formation）、第二段が**マージ（merge）**です。

-- フェーズ1: ラン生成
入力を「作業メモリに収まるチャンク」に区切って読む
  各チャンクをメモリ内でソート（quicksort など）
  ソート済みチャンク = ラン を一時ファイルへ書き出す（スピル）
-- フェーズ2: マージ
複数のソート済みランを併合して、全体がソートされた1本にする

第一段で作るのは、それぞれが内部的にソート済みの断片＝ランです。入力全体のページ数を N、作業メモリに同時に載るページ数を M とすると、初期ランの本数はおおむね N / M 本になります。これらは個々にソート済みですが、ラン同士の順序関係はまだ付いていません。

第二段の併合が外部ソートの核心です。ソート済みの列を複数まとめて1本のソート済み列にするのは、各ランの先頭を比べて最小値を1つ取り出し、取り出したランの次の要素を補充する、という操作の繰り返しで実現できます。これは追加メモリをほとんど使わずに行えます。

多方向マージ：K 本を一度に併合してパス数を減らす

2本ずつ併合していく素朴な方法では、ラン数が多いとマージのパス（入力全体を一巡する読み書き）が何段も必要になり、I/O が爆発します。そこで実用システムは、一度に **K 本のランを同時に併合する多方向マージ（K-way merge）**を使います。

各ランから1ページずつ入力バッファに読み込み、K 個の先頭要素のうち最小のものを出力する。K が大きいほど一度の併合で束ねられるランが増え、必要なパス数が減ります。K 本を毎回比較する際は、線形に走査せず敗者木（loser tree）やヒープを使うと、1要素あたりの比較が log2(K) で済みます。

-- K-way merge（ヒープ/敗者木で先頭最小を高速に取り出す）
各ラン r の先頭要素を heap に投入        -- K 要素
while heap が空でない:
    (v, r) = heap から最小を取り出す       -- log2(K) で取得
    v を出力
    ラン r の次の要素があれば heap に投入

マージのパス数は、初期ラン数を R0、マージファンイン（同時に併合できる本数）を K とすると、おおよそ ⌈logK(R0)⌉ 段になります。各パスでデータ全体を1回読み書きするため、外部ソートの総 I/O は概ね次の式で見積もれます。

総 I/O ≒ 2 × N × ( 1 + ⌈logK(R0)⌉ )
        └ ラン生成の読み書き ┘ └─ マージ各パスの読み書き ─┘

N が入力ページ数です。K を大きくすればパス数の対数の底が大きくなり、多くの実務ケースでは **1パスのマージ（logK(R0) = 1）**で済みます。つまり「ラン生成で全件を1回読み書き＋マージで全件を1回読み書き」の 4N 程度に収まる、というのが外部ソートが速い帯域です。

置換選択：ランを長くしてラン数を減らす

初期ランが長ければ、ラン本数 R0 が減り、マージのパス数 ⌈logK(R0)⌉ も減ります。素朴なラン生成は「メモリ1杯ぶん読んでソート」なので、ランの長さはちょうど作業メモリ分（M ページ）です。これを伸ばす古典的技法が**置換選択（replacement selection）**です。

考え方は、メモリ全体を1つの最小ヒープとして使い続け、出力した要素のぶんだけ入力から補充することです。

-- 置換選択：ヒープで「出せる限り」現在のランを伸ばす
メモリを入力で満たし、最小ヒープを構築
loop:
    最小値 v をヒープから取り出して現在のランに出力
    次の入力 x を読む
    if x >= 直前に出力した値:   x をヒープに入れる（同じランで使える）
    else:                        x を「次のラン用」として隔離（凍結）
    隔離が増えてヒープが空になったら、現在のランを閉じ、隔離分で次のランを開始

ポイントは、新しく読んだ要素が直前の出力値以上なら、まだ現在のランの末尾として出力できる点です。これにより、入力がランダムな並びでも、ランは平均して**作業メモリの約2倍の長さ（おおよそ 2M）**まで伸びます。入力がすでにほぼ整列していれば、ランはさらに長く（極端には1本に）なります。ラン数が半分になればマージの底入れが楽になり、logK(R0) を1段減らせる場合があるため、I/O 削減に直結します。

ハッシュ集約のスピル：GROUP BY がメモリを超えるとき

GROUP BY の集約には大きく2方式あります。入力をソートしてから隣接する同一キーをまとめるソート集約と、グループキーのハッシュテーブルに集約状態を持つハッシュ集約です。集約対象がソート不要なら、ハッシュ集約のほうが入力1回の走査で済み有利です。

-- ハッシュ集約（in-memory）
for each row in input:
    g = HashTable[ hash(row.key) ]     -- グループの集約状態を引く
    g に row を取り込む                 -- count++, sum+=val など
-- 走査完了後、HashTable の各エントリが1グループの集約結果

このハッシュテーブルが保持するのは一意なグループの数ぶんの状態です。グループ数が多く（高カーディナリティ）作業メモリを超えると、ハッシュ集約もスピルが必要になります。やり方はハッシュ結合のスピルと同型で、入力をハッシュ値で複数パーティションに振り分けて一時ファイルへ書き出し、パーティションごとに独立に集約し直すことです。

-- ハッシュ集約のスピル（メモリ超過時）
メモリに載るぶんのグループは in-memory で集約を続ける
載らない（新規の）キーは、その行を Part[ h(key) ] へ書き出す
全入力を処理後、各パーティション Part[i] を順に読み戻し、
  Part[i] 単独で再度ハッシュ集約する     -- なお大きければ別ハッシュで再帰分割

正しさの核心は、同じグループキーの行は同じハッシュ値なので必ず同じパーティションに入る点です。だからパーティションをまたいで同一グループが分断されることはなく、Part[i] を単独で集約すればそのパーティションぶんのグループは正しく完成します。1つのパーティションがなお載らないほど巨大なら、独立な別のハッシュ関数で再帰的に再分割します（同じハッシュで割り直しても、すでに同値の行ばかりなので分かれません）。I/O は再帰の段数に比例して増えるため、スピル段数がコストの支配項です。

カーディナリティ誤推定という落とし穴

ハッシュ集約のメモリ使用量は一意グループ数に左右されます。オプティマイザがこの数を小さく見誤ると、実行時に想定外の大量スピルが起き、4N どころか何倍もの I/O を払うことがあります。逆に過大に見積もればハッシュ集約を避けて高コストなソート集約を選んでしまう。だから集約系クエリのチューニングでは、まず推定グループ数と実測の乖離を疑うのが定石です。

PostgreSQL の EXPLAIN ANALYZE では、ソートノードに Sort Method（quicksort は in-memory、external merge はスピル）と Disk 使用量が、集約ノードに Batches・Memory Usage・Disk Usage が出ます。external merge や Batches > 1 が出たらスピルの合図で、work_mem を増やして in-memory に収まれば I/O が落ち桁で速くなることがあります。ただし work_mem はクエリ・ソート単位に確保されるため、増やしすぎは同時実行時のメモリ枯渇を招きます。なおスピルの読み書きはバッファプールを介さず一時ファイルへ直接行くため、調整の指針は通常のページキャッシュとは別に考える必要があります。

まとめ

• 外部ソートは、作業メモリ単位でソートしてランを書き出すラン生成と、複数ランを1本にまとめるマージの二段。I/O はマージのパス数 ⌈logK(R0)⌉ で決まり、K（ファンイン）を上げると段数が減るが、ランあたりバッファが痩せてランダム I/O が増える綱引きがある。
• 置換選択はメモリをヒープとして使い、平均で約2倍長のランを生成してラン数を減らす。マージ段数の削減＝I/O 削減に効くが、キャッシュ局所性を犠牲にするため万能ではない。
• ハッシュ集約は一意グループ数ぶんの状態をメモリに持ち、超過すると入力をパーティションへスピルして再帰的に集約する。コストはスピル段数に線形。
• グループ数が膨大／結果を整列したいときはソート集約が選ばれる。両者の選択はオプティマイザの推定グループ数次第で、カーディナリティ誤推定が想定外スピルの主因。
• 実行計画で external merge・Batches > 1・Disk Usage が出たらスピルの証拠。work_mem 調整と推定精度の改善が効く。実行モデルの全体像はクエリ実行モデル、大量集計の文脈はOLAPもあわせて参照してください。