# 外部マージソート ## 定義 外部マージソート(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)。 ## 横断的知見 (単一ソースのみのため蓄積中。2ソース目以降、突き合わせで見えた観察をここに追記する。) ## 未解決の問い - フェーズ➋の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]] — 講義シリーズ発表者・所属。 ## 出典 - [[@2026__DiDi__Sorting Large Tables]](p.03-05, p.09)