# Sorting Large Tables(DiDi #04) ## 概要 [[Torsten Grust]]([[Universität Tübingen]])による講義シリーズ「Design and Implementation of DuckDB Internals」(DiDi)第4回のスライド。全11ページ(実質9コンテンツページ)で、[[DuckDB]]がテーブルの大規模ソートをどう実装しているかを、二相マージソート戦略・キー正規化・並列マージの3点に絞って解説する。 ## 主要メッセージ - SQLのタプルモデルは本来「順序なしのバッグ」だが、`ORDER BY`・順序付き集約・ウィンドウ関数・`ASOF JOIN`・`LIMIT`/`OFFSET`の決定的動作など、実務上ソートが必要な場面は多い(p.02)。 - DuckDBのソート実装は「現在も作業台の上」(on the workbench)にあり、バージョン1.4.0(2025年9月)で内部ソートコードの大規模書き換えが行われた(p.03)。主記憶に収まらない大テーブルもディスクへのスピルで処理できる設計を志向する(p.03)。 - ソート戦略は二相マージソート(two-phase merge sort)で、フェーズ➊(スレッドローカルソート)とフェーズ➋(T-way マージ)の両方で全CPUコアを使い切る(p.04)。 ## 視覚的に重要な図表 **p.01 タイトルスライド** ![[_attachments/didi-04-sorting-large-tables/page-002.png]] 講義シリーズ「Design and Implementation of DuckDB Internals」第4回、テーマは「Sorting Large Tables」。日付は2026年4月7日、発表者は[[Torsten Grust]]([[Universität Tübingen]])。 **p.06 固定長キーの正規化(Key Normalization for Fixed-Size Keys)** ![[_attachments/didi-04-sorting-large-tables/page-007.png]] 可変長バイト列のソートキーを、既知の長さ`n`バイトから`⌈n/8⌉`個の`uint64_t`にグループ化して格納する`FixedSortKey`構造体と、`part0`/`part1`の辞書式比較で1回の`<`比較により行順序を決定する`LessThan`実装を示す。ペイロードなしクエリでは正規化キーのみを保持し、出力時に逆変換できるという脚注付き。 **p.09 フェーズ➋: T-way マージ** ![[_attachments/didi-04-sorting-large-tables/page-011.png]] フェーズ➊が生成したT本のソート済みラン(各ページに正規化キー`H_k`とペイロードへのポインタを保持)を、キー`H_k`上の`<`比較でマージし、ポインタを介してペイロードを参照しながら出力列をチャンク単位で生成する様子を図示する。スライド末尾は「マージ中に全CPUコアがどう均等に貢献できるか」という問いで締めくくられ、次回以降への布石になっている。 ## 概念・実体への接続 - [[外部マージソート]] — 二相マージソート戦略(フェーズ➊スレッドローカルソート、フェーズ➋ T-way マージ)、主記憶を超えるテーブルのディスクスピル。 - [[キー正規化]] — 型に応じた比較演算子の選択・NULL処理・辞書式順序を、単一の`<`比較で置き換える固定長キー(`FixedSortKey`)設計。 - [[DuckDB]] — バージョン1.4.0(2025年9月)でソートコードを大規模書き換え。Vergesort・Ska Sort・Pattern-defeating QuickSortを組み合わせて利用。 - [[Torsten Grust]] / [[Universität Tübingen]] — 本講義シリーズの発表者・所属。 ## 限界・不確実点 - 公式ページ(https://duckdb.org/library/design-and-implementation-of-duckdb-internals/)の`datePublished`はコースページ全体の日付として`2026-03-19`と記載されているが、本スライドのタイトルページ自体には「April 7, 2026」と明記されている。両者は一致しない(コースページ日付は講座開設日、スライド記載日は本チャプターの講義予定日とみられる)。出典優先度(スライド > 公式ページ)に従いスライド記載の2026-04-07を`date_published`として採用し、確度は`medium`とした。 - スライド内のCPU/データページ等のピクトグラム(⚙・🔑・📄等)はテキスト抽出では文字化けするため、画像を正として解釈した。 - p.09末尾の「マージ中にどう全CPUコアを均等に稼働させるか」という問いはスライド上で回答されておらず、後続回(DiDi #05以降)で扱われる可能性が高いが本資料からは確認できない。 - PDF抽出テキストにのみ現れる脚注番号(`#013`・`#014`)はスライド上のアイコンに紐づく社内的な図版IDと見られ、文脈上の意味は不明。