# Zonemap ## 定義 Zonemap(min-max インデックス)は、列指向テーブルストレージに組み込まれ、全列に自動生成される軽量な索引である。DuckDB では各列 `c` を 120K(122880)行単位の行グループ(row group)に分割し、各行グループごとに含まれる値の範囲を大まかに特徴づける `(min, Max)` エントリを保持する。Sequential Scan 演算子は述語プッシュダウンにより、`lo ≤ c ≤ hi` が行グループの `(min, Max)` レンジと重ならないことが保証できる行グループを安全にスキップできる。Zonemap は手動作成や制約起因ではなく常に全列に存在し、ART のような作業メモリ消費や更新時の明示的メンテナンスを要しない点で ART と対照的である。(Source: [[@2026__DiDi__The ART of Indexing]]) Zonemap の有効性は列の値の並び順(column ordering)に強く依存する。ソート済みの列ではエントリごとの `(min, Max)` の幅(span)が狭くなり、多くの行グループが述語を確実に満たさないと判定できるためスキップ効果が高い。逆に無秩序な列では各行グループの span が列の値域全体をほぼ覆ってしまい、ほとんどの行グループがヒットの可能性を排除できずスキップできない。したがって、ベーステーブルを特定列でソートしておくことが述語評価の効率化に寄与しうる。(Source: [[@2026__DiDi__The ART of Indexing]]) ## 横断的知見 - **Zonemap と ART は「粗い足切り」と「精密な到達」という補完関係にある**: Zonemap は行グループ単位(120K行)の粗い skip/no-skip 判定しか行えないが、常時稼働かつ追加コストがほぼゼロという特性を持つ。一方 [[Adaptive Radix Tree]] は個々の行へ `O(k)` で到達できるが、作業メモリと更新メンテナンスのコストを伴う。DuckDB がこの2階層を両方実装している設計は、「全行スキャンを避ける」という共通目的に対し、コストの異なる2つの解像度の索引を組み合わせる典型例として理解できる。(Source: [[@2026__DiDi__The ART of Indexing]]) - **列順序という物理設計判断が、索引を作らずに索引的効果を得る手段になる**: Zonemap のスキップ効率は列の物理的な並び順(ソート済みか否か)だけで大きく変動する。これは ART や B-Tree のように明示的な索引構造を追加せずとも、テーブルの物理レイアウト(列順序・行順序)そのものが述語評価の効率を左右するという、[[B-Tree]] や [[Adaptive Radix Tree]] とは異なる最適化軸を示す。(Source: [[@2026__DiDi__The ART of Indexing]]) ## 未解決の問い - Zonemap の行グループサイズ(120K = 122880行)がどのような基準で選定されたか、また他の DBMS の類似機構(min-max index、ブロックレンジ索引等)と比べたトレードオフはスライドからは読み取れない。 - INSERT/UPDATE/DELETE による行グループ内の値変動時に、Zonemap の `(min, Max)` エントリがどのタイミング・コストで再計算されるかは説明されていない。 - 複数列にまたがる複合述語(例: `c1 = x AND c2 = y`)に対して、Zonemap が列ごとの skip 判定をどう組み合わせるかは未説明である。 ## 関連 - ソース: [[@2026__DiDi__The ART of Indexing]] - 概念: [[Adaptive Radix Tree]] - エンティティ: [[DuckDB]] / [[Torsten Grust]] / [[Universität Tübingen]] ## 出典 - [[@2026__DiDi__The ART of Indexing]](Zonemap の定義、行グループ単位の `(min, Max)` エントリ、Sequential Scan による skip 判定、列順序が有効性に与える影響)