# 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 は「行グループ内のスキャンスキップ」だけでなく「分散ストレージにおけるファイル/セグメント選択」というより粗い粒度でも機能する汎用パターンである**: DuckDB は 120K(122880)行の行グループ単位で `(min, Max)` を保持し、単一プロセス内のシーケンシャルスキャン中に行グループを読み飛ばす判定に使う。これに対し Honeycomb Retriever([[@2026__OReilly__Observability Engineering 2E - Chapter 13 Efficient Data Storage with Retriever]])は、1時間経過・250,000レコード超・1GB超のいずれかで区切られる「セグメント」(数十万行規模の追記単位)ごとに最古・最新イベントタイムスタンプだけを保持し、クエリ時にはこのメタデータでクエリ時間範囲と無関係なセグメント全体を丸ごとスキップする。DuckDB の用途がプロセス内スキャンの高速化であるのに対し、Retriever の用途は分散ストレージ上のどのファイル群を読み込み対象にするかというファイル選択の判定であり、Snowflake の min-max ファイルプルーニング(→ [[データパーティショニング]] の横断的知見)とも同型である。粒度が粗くなるほどメタデータの保持・更新コストは下がるが、1セグメントに広い時間範囲が混入する場合(バックフィルデータ等)はプルーニング精度が落ちるというトレードオフを Retriever は明示的に許容している。(Source: [[@2026__DiDi__The ART of Indexing]], [[@2026__OReilly__Observability Engineering 2E - Chapter 13 Efficient Data Storage with Retriever]]) - **ClickHouseは同一システム内に「常時有効な粗い並び順インデックス」と「任意設定するZonemap相当の`MinMax`スキップインデックス」を並存させ、Zonemapを「唯一の索引」ではなく「複数の粒度・複数の役割を持つ絞り込み手段の一つ」として位置づける**: [[ClickHouse]]([[@2026__OReilly__Observability Engineering 2E - Chapter 14 Efficient Data Storage with ClickHouse]])は約8,192行単位のgranuleに対し、(1) 常に構築される疎な主キーインデックス(granule先頭のキー値のみを記録し、パーティション→パート→granuleという上位の絞り込み段階を通過した後に二分探索で使う)と、(2) `INDEX ... TYPE minmax`で明示的に宣言するオプトインのMinMaxスキップインデックス(主キー以外の任意カラム、例えばスパンの`Duration`列に対しgranuleごとの最小・最大値を保持し外れ値検索を高速化する)という、目的の異なる2種類の索引を区別する。DuckDBのZonemapが全カラムに自動生成される単一メカニズムであるのに対し、ClickHouseは「並び順キーに基づく必須の粗い足切り」と「任意カラムへの追加的なZonemap」を分離しており、Zonemapという設計パターンが常に単一の実装形態を取るわけではないことを示す。また、granule粒度(約8,192行)はDuckDBの行グループ(120K行)やRetrieverのセグメント(数十万行)よりも一桁以上細かく、DuckDB/Retrieverが「粗いが安価な足切り」を志向するのに対し、ClickHouseはより精密なgranule単位のプルーニングを可能にする代わりにインデックス自体の読み取りコストが増える(「読むべきでないgranuleが少ない場合はMinMaxインデックス自体がストレージを肥大化させ性能を劣化させうる」と明記される)というトレードオフを負う。(Source: [[@2026__DiDi__The ART of Indexing]], [[@2026__OReilly__Observability Engineering 2E - Chapter 14 Efficient Data Storage with ClickHouse]]) ## 未解決の問い - Zonemap の行グループサイズ(120K = 122880行)がどのような基準で選定されたか、また他の DBMS の類似機構(min-max index、ブロックレンジ索引等)と比べたトレードオフはスライドからは読み取れない。 - INSERT/UPDATE/DELETE による行グループ内の値変動時に、Zonemap の `(min, Max)` エントリがどのタイミング・コストで再計算されるかは説明されていない。 - 複数列にまたがる複合述語(例: `c1 = x AND c2 = y`)に対して、Zonemap が列ごとの skip 判定をどう組み合わせるかは未説明である。 - DuckDB(行グループ粒度)と Retriever(セグメント粒度)のように Zonemap 的メタデータの粒度が異なる実装間で、最適な粒度をワークロード特性(挿入レート・クエリの時間範囲選択性)から導出する一般式は存在するか。 - ClickHouseのMinMaxスキップインデックスがgranule(約8,192行)単位、DuckDBのZonemapが行グループ(120K行)単位、Retrieverのセグメントメタデータが数十万行単位という3段階の粒度差は、それぞれのシステムが想定する典型クエリ選択性(何%の行が述語にマッチするか)の違いに由来すると考えられるが、この対応関係を定量的に裏付けた比較研究はあるか。 - ClickHouseの「常時有効な主キーインデックス」と「任意設定のMinMaxスキップインデックス」の二層構造は、DuckDBのZonemap(全カラム自動)+ART(任意カラム精密索引)という二層構造(横断的知見1点目参照)とどこまで同型か。両者とも「粗い足切り+精密索引」の組み合わせという共通パターンを持つが、ClickHouseの主キーインデックスはART的な精密到達を提供しない点で対応関係は完全ではない。 ## 関連 - ソース: [[@2026__DiDi__The ART of Indexing]] / [[@2026__OReilly__Observability Engineering 2E - Chapter 13 Efficient Data Storage with Retriever]] / [[@2026__OReilly__Observability Engineering 2E - Chapter 14 Efficient Data Storage with ClickHouse]] - 概念: [[Adaptive Radix Tree]] / [[データパーティショニング]] / [[列指向OLAPデータベース]] - エンティティ: [[DuckDB]] / [[Torsten Grust]] / [[Universität Tübingen]] / [[Retriever]] / [[Honeycomb.io]] / [[ClickHouse]] ## 出典 - [[@2026__DiDi__The ART of Indexing]](Zonemap の定義、行グループ単位の `(min, Max)` エントリ、Sequential Scan による skip 判定、列順序が有効性に与える影響) - [[@2026__OReilly__Observability Engineering 2E - Chapter 13 Efficient Data Storage with Retriever]](セグメント単位の最古・最新タイムスタンプメタデータによる、より粗い粒度でのファイル選択プルーニング) - [[@2026__OReilly__Observability Engineering 2E - Chapter 14 Efficient Data Storage with ClickHouse]](granule単位の疎な主キーインデックスと、任意設定のMinMaxスキップインデックスの使い分け)