外部ソート完全ガイド：外部マージソートの仕組み・I/O最適化と実装ポイント
エバープレイ編集部外部ソートとは — 大量データをディスクで効率的に並べ替える技術
外部ソート（がいぶソート、external sort）は、メインメモリ（RAM）に収まらないほど大きなデータ集合をディスク（外部記憶）を使ってソートするための一連の手法・アルゴリズムの総称です。典型的にはデータベースやログ処理、大規模データ分析の場面で使われ、I/O（入出力）回数を最小化することが性能の鍵になります。
なぜ外部ソートが必要か
データサイズがメモリを超える場合、単純にメモリ上で全データをソートできない。
ディスクはメモリに比べてアクセスコスト（特にランダムアクセス）が大きく、I/O回数・アクセスパターンが性能を左右する。
外部ソートは「ディスク上での効率的な入出力設計」と「メモリ内処理の工夫」を組み合わせ、現実的に大規模ソートを実現する。
代表的なアルゴリズム：外部マージソート（External Merge Sort）
最も広く使われるのが外部マージソートです。基本は二段階：
- 初期ラン生成（Run generation）：ディスクからメモリにブロック単位で読み込める最大量を読み、内部ソート（例えばクイックソートやヒープソート）して「ソート済みラン（run）」としてディスクに書き出す。メモリにBページ（またはBレコード）入るとすると、初期ランの数は ceil(N / B)（Nは全ページ数）。
- マージフェーズ（Merge phase）：生成した複数のランをマルチウェイ（k-way）で逐次マージして最終的に一つのソート済みファイルにする。メモリをBバッファページとすると、通常はB-1入力＋1出力の構成でB-1ウェイマージが可能。
I/Oコストの簡易モデル
外部ソートの性能指標は主にディスクI/Oの回数で見ます。ページ単位で考えると：
- 初期ラン生成：ファイル全体を1回読み、1回書くので 2N のI/O（Nはページ数）。
- 各マージパス：各パスでファイル全体を読み書きするため 2N のI/O。
- マージパス数：初期ラン数 R = ceil(N / B)。1回のマージで同時に合成できるのは最大 B-1 ラン。したがってパス数は ceil(log_{B-1} R)。
合計I/Oはおおよそ 2N × (1 + ceil(log_{B-1} (ceil(N/B)))) となります（ディテールや境界条件で若干変わります）。この式から、メモリバッファ（B）を増やせばパス数が減り、I/Oが劇的に改善することが読み取れます。
初期ラン生成の改良：リプレースメント選択（Replacement Selection）
単純にB分ずつ切ってソートする方法では初期ランの長さはほぼBですが、リプレースメント選択という手法を使うと平均してランの長さを約2Bに延ばせます。やり方はヒープ（あるいは優先度付きキュー）を使い、読み込んだ新しいレコードを条件に基づいて現在のランに置くか次のランに回すかを決めます。これにより次のマージで消すべきラン数が減り、マージパスを減少できます。
k-way マージ時のデータ構造とコスト
マルチウェイマージでは、k 個のランの先頭要素から最小値を逐次選択して出力します。効率的に最小値を選ぶために用いられる典型的な構造がトーナメント木（勝者木 / Loser tree）です。Loser tree を使うと各出力につき O(log k) の比較で済み、実際の実装はキャッシュやバッファの管理と合わせて性能が出ます。
外部ソートのバリエーション
- ポリフェーズマージ（Polyphase merge）：Runの長さが不均衡なときに実I/Oを少なくする古典手法。ただし実装が複雑で現代ではあまり使われない。
- 外部基数ソート（External Radix Sort）：固定長キー向けに、キーのビットや桁毎に分配（ディストリビュート）していく方法。パス数はキー長に依存するため、適切ならばマージよりI/Oを減らせる。
- 分配ソート（Distribution sort）：ハッシュやサンプリングで範囲分割して各パーティションを個別にソートする。分散環境や並列ソートで有効。
実装上の考慮点・最適化
- ブロックサイズと連続I/O：ディスクはシーケンシャルアクセスが得意なので、できるだけ大きめのブロック（ページ）でまとめて読み書きする。OSやファイルシステムのプリフェッチを利用する。
- ダブルバッファリングと非同期I/O：読み込みと処理を重ねることで待ち時間を隠蔽する。
- ディスク種別：HDDではシーキングコストを避けることが重要。SSDではランダムアクセスの罠は緩和されるが書き込み量（寿命）やスループットを考慮する。
- メモリ配分：Bをページ数で考えるが、実装ではレコードサイズやアライメント、JVMや言語ランタイムのオーバーヘッドを考慮する。
- Loser tree等の比較回数削減：比較回数だけでなく、メモリアクセスパターン（キャッシュ効率）も重要。
- クラスタ・分散環境：データシャッフル（MapReduceやSparkのソート処理）ではネットワークI/Oがボトルネックになるため、ローカルソート＋分割（range partitioning）やサンプリングを利用する。
分散・並列外部ソート
ビッグデータ処理では、ノード間でデータを分割して並列にソートし、最後にマージまたは並列的に範囲を割って連結する手法が一般的です。MapReduceのシャッフル操作やSparkのrange-partition + local sort はその典型で、各ノードはローカルで外部ソート（必要ならディスクを使う）を行い、ネットワーク転送量を抑えるように設計されます。
実務での注意点
DBのソートメモリ設定（例：PostgreSQL の work_mem）や一時領域（temp files）に依存して、ソートがメモリ内で完結するか外部ソートになるかが決まる。外部ソートが発生するとディスクI/Oの影響でクエリ遅延が増える。
ログや監査データなど連続的に増加するデータのソートでは、事前にパーティショニングやインデックス設計でソート自体を回避できる場合がある。
大容量ソートではファイルシステムや一時領域の空き、IOPS制限にも注意。
まとめ
外部ソートは「メモリに載らないデータをいかに少ないディスクI/Oで並べ替えるか」を追求するアルゴリズム群です。外部マージソートが基本であり、初期ラン生成（単純ソート／リプレースメント選択）と効率的なk-wayマージ（Loser tree 等）を組み合わせます。実装ではバッファサイズ、ブロック化、非同期I/O、ディスク特性、さらには分散環境でのデータ配置・シャッフル設計が性能を左右します。用途に応じて外部基数ソートや分配ソート、並列処理を採用することでさらに最適化が可能です。
参考文献
- External sorting — Wikipedia
- Replacement selection — Wikipedia
- Loser tree — Wikipedia
- External memory algorithm — Wikipedia
- External Sorting — GeeksforGeeks
- PostgreSQL: Managing Work_mem and Temporary Files — PostgreSQL Documentation
投稿者プロフィール
