# 外部マージソート ## 定義 外部マージソート(external merge sort)は、主記憶に収まらない大規模データをソートするための手法で、入力をディスクへスピル可能な断片(ラン)に分割してそれぞれをソートした後、複数のソート済みランをマージして最終的な順序を得る。[[DuckDB]]は「二相マージソート(two-phase merge sort)」という変種を実装しており、フェーズ➊(スレッドローカルソート)とフェーズ➋(T-wayマージ)の両フェーズで利用可能な全CPUコアを使い切る設計を採る(Source: [[@2026__DiDi__Sorting Large Tables]] p.04)。 フェーズ➊では、T個のスレッドそれぞれが入力の1/T断片を読み、対象列からペイロード行をデータページ(256KB単位)上に構成し、ソートキーを[[キー正規化]]した上でスレッドローカルにソート済みランを1本生成する(p.05)。フェーズ➋では、各ランをT個の非重複セグメントに事前分割し、セグメント単位で独立にT-wayマージを実行、マージ結果をチャンク単位で下流のクエリプランへ即座に出力する(p.04, p.09)。 ソート戦略は事前ソート済み入力への適応(pre-sorted input data adaptation)も備え、主記憶を超える大テーブルはディスクへのスピルで処理する設計を志向する。ただし「ソートは原理的に入力テーブル全体を実体化する必要がある(最後の入力行が結果の先頭になり得るため)」という制約は変わらない(p.03)。 ## 横断的知見 - **単一マシン向けの外部マージソートは、分散バッチ処理のシャッフルにおけるマッパー側処理としてそのまま再利用される**: DuckDBの二相マージソート(フェーズ➊のスレッドローカルソート→フェーズ➋のT-wayマージ)が単一プロセス内のマルチコア並列を対象とするのに対し、[[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 11 Batch Processing]] が説明するMapReduceのシャッフル機構は、各マッパーが「メモリ上のソート済み構造に蓄積→セグメントファイルとして書き出し→段階的にマージ」という同一の外部マージソート技法をローカルディスク上で実行してから、キーのハッシュに基づきリデューサへ振り分ける。GNU Coreutilsの`sort`コマンド(ディスクスピル+自動並列化)も同様の原理をUnixツールレベルで実装しており、単一マシン・分散バッチシステムの双方で「メモリ上のソート済みチャンクをディスクへ書き出し、複数ランをマージする」という同一アルゴリズムが繰り返し採用されていることが分かる。(Source: [[@2026__DiDi__Sorting Large Tables]], [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 11 Batch Processing]]) ## 未解決の問い - フェーズ➋のT-wayマージにおいて、全CPUコアがどう均等に貢献できるか(スライドp.09末尾で明示的に問われているが、本資料内では回答されていない。DiDi講義シリーズの後続回(#05以降)で扱われる可能性が高いが未確認)。 - フェーズ➊とフェーズ➋の間で、ディスクスピルが具体的にどのタイミング・粒度で発動するか(p.03で「スピル可能」と述べられるのみで、詳細は本資料からは確認できない)。 - Vergesort・Ska Sort・Pattern-defeating QuickSortの3アルゴリズムの切り替え条件(最初の64bitキーで順序が決まるかどうか)が、実運用データでどの程度の頻度で各アルゴリズムに分岐するか。 ## 関連 - [[@2026__DiDi__Sorting Large Tables]] — 本概念の一次ソース。 - [[DuckDB]] — 二相マージソートの実装元。バージョン1.4.0(2025年9月)で大規模書き換え。 - [[キー正規化]] — フェーズ➊でソートキーを固定長化する前処理。単一の`<`比較で行順序を決定可能にする。 - [[Torsten Grust]] / [[Universität Tübingen]] — 講義シリーズ発表者・所属。 - [[シャッフルと分散結合]] — MapReduceシャッフルのマッパー側処理として本アルゴリズムが分散環境に応用される。 - [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 11 Batch Processing]] — GNU sortの自動ディスクスピル・並列化、MapReduceシャッフルの分散版外部マージソート。 ## 出典 - [[@2026__DiDi__Sorting Large Tables]](p.03-05, p.09) - [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 11 Batch Processing]]("Sorting Versus In-Memory Aggregation"・"Shuffling Data" 節)