# Managing Memory + Grouped Aggregation ## 概要 [[Torsten Grust]]([[Universität Tübingen]])による講義シリーズ「Design and Implementation of DuckDB Internals」(通称 DiDi)第3回のスライド。[[DuckDB]]のメモリ管理(メモリ階層、ページ化/非ページ化割り当ての統合管理、ベーステーブルのバッファリング、スピリング)と、ハッシュベースのグループ集約(`HASH_GROUP_BY`)の内部実装を扱う。全16ページ中14ページに本文があり(残り2ページは区切り用の空白ページ)、末尾はPhase 2(パーティション単位集約)の説明手前で終わっており、続きは同シリーズの後続回で扱われる可能性が高い。 ## 主要メッセージ - **メモリ階層のレイテンシ格差**(p.02): CPU L2キャッシュ(2.8ns)・RAM(≈100ns)・SSD(50-150μs)・HDD(1-10ms)の実レイテンシを「人間スケール」(1秒〜数十日)に換算して提示し、高速メモリほど容量が小さいという制約から「クエリ処理中はホットデータをRAMに保つ」設計方針を導く。 - **DuckDBは既定でホストRAMの80%を使用**(p.03。PostgreSQLの`shared_buffers`既定値128MBと対比)。`memory_limit`パラメータで上限を制御し、必要に応じて段階的にディスクベース処理へ移行する(out-of-core processing)。 - **ストリーミング実行(パイプライニング)**(p.04): 2048要素のベクトル単位でデータチャンクをクエリプランに流し込む。`WHERE`/`SELECT`、グループ数が少ないGROUP BY、`LIMIT N`、CSV→Parquetのコピー等は大きなテーブルでも`memory_limit`を超えずに評価できる。 - **スピリング対象**(p.05): グループ数の多いGROUP BY、`count(DISTINCT)`、両テーブルがメモリを超えるJOIN、`ORDER BY`、sweeping frameを持つウィンドウ関数はいずれもハッシュテーブル・ソート等の中間データ構造がメモリを超えうる。 - **統一メモリ管理**(p.06, p.08): 非ページ割り当て(ポインタベースの小さく断片化したデータ)とページ割り当て(32KB〜256KBのブロック単位、表データの一部を保持)を同一メモリ領域`memory_limit`で管理する。DuckDBはフラグメンテーション回避のためページ割り当てを優先する。3種の割り当て(非ページ中間データ/ページ中間データ/バッファ済みベーステーブルデータ)は、サイズ・生存期間・スピリング可否がそれぞれ異なる(p.08の表)。 - **ベーステーブルのカラム単位バッファリング**(p.07): `*.db`ファイルからのI/Oは256KBブロック単位で行い、クエリが参照するカラムだけをバッファする。不要になったページはLRUキューに入れて(unpin)、メモリが逼迫したときだけ追い出す(eviction)。バッファ済みページはディスクデータのキャッシュなので、追い出し時にディスクへの書き戻しは不要。 - **ページ化中間データのレイアウト**(p.09): ベーステーブルは列指向だが、中間データは行比較(ソート・ハッシュ・ジョイン)を高速化するため行指向レイアウトを採る。行サイズとカラムオフセットはクエリプラン生成時に確定するため、Data Pageごとに一度だけ保持する。 - **可変長カラムの扱い(German Strings)**(p.10): 12文字以下の短い文字列は`長さ(4B)+文字列(12B)`でインライン化。長い文字列は`長さ(4B)+プレフィックス(4B)+ポインタ(8B)`の16バイトで表現し、実データは別のVariable Data Pageに置く。この配置はUmbra(TU Munich)で普及した手法で、Apache ArrowやPolarsでも採用されている(p.10脚注3)。 - **ポインタ先を持つページのスピリング**(p.11): Variable Data Pageがスピル/再ロードされるとベースアドレスが変わりポインタが無効になりうる。DuckDBはベースアドレスをData Pageの先頭にメタデータとして保存し、次回参照時に遅延的にポインタを付け替える。 - **ハッシュベースグループ集約の基本**(p.12): TPC-H(sf=100)の`lineitem`(6億行)を`l_orderkey`でGROUP BYすると1.5億グループが生成される例を示し、`HASH_GROUP_BY`演算子がハッシュテーブルへの挿入と線形プロービングによる衝突解決で実装されることを説明。グループ数が静的に少ないと分かる場合(`l_returnflag`等)は`PERFECT_HASH_GROUP_BY`を使う。 - **外部グループ集約の2フェーズ設計**(p.13-p.14): 全コアの活用とスピリング可能性を両立するため、Phase 1(スレッドローカルな事前集約、モーセルごとに1スレッド)とPhase 2(パーティション単位集約)に分割する。Phase 1では入力を約10万行の「モーセル」に分割し、各スレッドがモーセルを読んでスレッドローカルなハッシュテーブルを構築する。ハッシュ`h(grp) = k = (salt, p, i)`でパーティション番号`p`とハッシュ配列インデックス`i`を求め、ハッシュエントリはページ化中間データ構造として保持することでメモリマネージャにスピリングを委ねる(本スライドはPhase 2の詳細説明の手前で終わる)。 ## 視覚的に重要な図表 **p.02 メモリ階層のレイテンシ表** ![[_attachments/DuckDB-DiDi-03-Memory-GroupedAgg/page-004.png]] CPU L2キャッシュからHDDまでの実レイテンシ・人間スケール換算・典型サイズを対比し、「速いメモリほど小さい」というトレードオフを可視化する。 **p.08 統一メモリ管理の比較表** ![[_attachments/DuckDB-DiDi-03-Memory-GroupedAgg/page-008.png]] 非ページ中間データ・ページ中間データ・バッファ済みベーステーブルデータの3種類を、サイズ・生存期間・スピリング可否の3軸で比較する。 **p.09 Data Pageの行指向レイアウト** ![[_attachments/DuckDB-DiDi-03-Memory-GroupedAgg/page-011.png]] 固定長行を持つData Page内でのオフセット計算(行#iはオフセット`i×s`、カラムオフセットは行内で既知)を図示する。 **p.10 German Strings(短文字列インライン化/長文字列ポインタ参照)** ![[_attachments/DuckDB-DiDi-03-Memory-GroupedAgg/page-012.png]] 12文字以下は`長さ+文字列`でインライン化し、長い文字列は`長さ+プレフィックス+ポインタ`でVariable Data Pageを参照する2種類のレイアウトを対比する。 **p.14 外部グループ集約Phase 1(スレッドローカル集約)** ![[_attachments/DuckDB-DiDi-03-Memory-GroupedAgg/page-016.png]] 入力を約10万行のモーセルに分割し、各スレッドのハッシュ配列がパーティション`p`・インデックス`i`を介してData Page上のハッシュエントリ(grp, agg)を指す構造を示す。 ## 概念・実体への接続 - [[DuckDB]] — 本スライドが内部実装を解説する対象システム。 - [[Torsten Grust]] / [[Universität Tübingen]] — 講義シリーズの講師・所属機関。 - [[アウトオブコア処理]] — メモリ階層・統一メモリ管理・スピリングの横断的知見に本ソースの内容を追加。 - [[ハッシュベースグループ集約]] — `HASH_GROUP_BY`と外部集約2フェーズ設計の詳細をこの概念ページに集約。 - [[列指向OLAPデータベース]] — German Strings(p.10)がUmbra由来でApache Arrow・Polarsにも波及している横断知見を追記。 ## 限界・不確実点 - ユーザー提供の想定発表日は2026-03-19だったが、これはコースの公式ページ(`https://duckdb.org/library/design-and-implementation-of-duckdb-internals/`)の`datePublished`(コース全体のページ公開日)であり、本スライド自体のタイトルページには「April 7, 2026」と明記されている(p.01)。本ページの`date`/`date_published`はスライド画像を権威としてp.01の記載(2026-04-07)を採用した。 - 全16ページ中2ページ(物理page-001、page-003)は本文が存在しない空白ページ(区切り用と推定)であり、内容には含めていない。 - スライドはPhase 2(パーティション単位集約)の説明タイトルを示した直後(p.13)で終わっており、Phase 2の具体的なアルゴリズムは本デッキには含まれない。後続デッキ(DiDi-04以降)で扱われる可能性があるが未確認。 - 音源・動画・transcriptは提供されておらず、口頭説明やQ&Aの情報は本ページに含まれない。 - p.10脚注3の「German Strings」がUmbraで普及したという記述はスライドの脚注に基づく一次情報であり、Umbra論文そのものは本ingestの対象外(未参照)。