# ハッシュベースグループ集約 ## 定義 ハッシュベースグループ集約(hash-based grouped aggregation)とは、SQLの`GROUP BY`を、グループ化キーをハッシュ関数に通してハッシュテーブルへ集約状態を保持・更新する方式で実装する手法である。[[DuckDB]]は物理演算子`HASH_GROUP_BY`でこれを実装する。行の`grp`値がキー`k`にハッシュされ、`hash_table[k]`のエントリ`(grp, agg)`を更新する。異なる`grp`値が同じキー`k`に衝突した場合は線形プロービングで別エントリを探す。グループ数が静的に少ないと分かる場合(例:`l_returnflag`のような値域の狭いカラム)は、衝突が起きない`PERFECT_HASH_GROUP_BY`という効率的な代替演算子を使う(p.12)。TPC-H(sf=100)の`lineitem`(6億行)を`l_orderkey`でGROUP BYすると1.5億グループが生成される例が、通常のGROUP BYがハッシュテーブルサイズの点で厳しい典型例として示される(Source: [[@2026__DiDi__Managing Memory + Grouped Aggregation]])。 グループ数が多くハッシュテーブルがメモリを超える場合、DuckDBは**外部グループ集約(external grouped aggregation)**として2フェーズ設計を採る。Phase 1はスレッドローカルな事前集約で、入力を約10万行の「モーセル(morsel)」に分割し、各スレッドが1つのモーセルを読んでスレッドローカルなハッシュテーブルを構築する。ハッシュ`h(grp) = k = (salt, p, i)`によりパーティション番号`p`とハッシュ配列インデックス`i`を求め、ハッシュエントリ`(grp, agg)`はページ化中間データ構造として保持する。これによりメモリマネージャに[[アウトオブコア処理|スピリング]]を委ねられる。Phase 2はパーティション単位の集約で、全コア活用とスピリング可能性を両立する狙いがある(p.13-p.14)。本スライドはPhase 2の詳細説明タイトルを示した直後で終わっており、具体的なアルゴリズムは後続の講義回で扱われる可能性がある。 ## 横断的知見 - 今後の取り込みで、複数ソース間の関係を追記する。 ## 未解決の問い - Phase 2(パーティション単位集約)の具体的なアルゴリズムはどうなるか。同シリーズの後続回(DiDi-04以降)が取り込まれ次第、追記する。 - モーセルサイズ(約10万行)やパーティション数`p`はどのような基準(コア数、メモリ量、推定グループ数)で決定されるか。 - `PERFECT_HASH_GROUP_BY`への切り替え判定(「グループ数が静的に少ないと分かる」の具体的な条件・しきい値)はオプティマイザのどの段階で行われるか。 - 本概念はソートベースのグループ集約(interesting orderを利用する方式、p.12脚注4で言及)とどうコスト比較されるか。 ## 関連 - ソース: [[@2026__DiDi__Managing Memory + Grouped Aggregation]] - 概念: [[アウトオブコア処理]] / [[クエリ実行プラン]] - エンティティ: [[DuckDB]] / [[Torsten Grust]] / [[Universität Tübingen]] ## 出典 - [[@2026__DiDi__Managing Memory + Grouped Aggregation]](`HASH_GROUP_BY`と外部グループ集約2フェーズ設計を解説する一次ソース)