# 概要 - [[PostgreSQL]] 14で導入された、[[BRIN]]（Block Range Index）の演算子クラス（Operator Class）のファミリー（例: `int4_minmax_multi_ops`, `timestamptz_minmax_multi_ops` など） - [[Skipping Index]] - 従来の `minmax` 演算子クラスが1つのブロックレンジ（ページ範囲）につき**単一の最小値・最大値のペア `[min, max]`** のみを保持するのに対し、`minmax-multi` は**複数の小さな区間（interval）や単一値（point）の集合**として要約データを保持する - これにより、外れ値（Outlier）の混入やUPDATEによるタプル移動、物理的なソート順の局所的な崩れがあっても、ギャップ（空白区間）を保持して検索時のブロックスキップ効率を高く維持できる # minmaxの課題 - [[BRIN]] はテーブルの物理的な連続ブロック群（`pages_per_range`、デフォルト128ページ＝1MB）ごとに、格納されている値の要約情報（Summary）だけを記録する軽量なインデックス（Zone Map / Data Skipping Indexの一種） - 従来の `minmax` は各ブロックレンジに対して `[min, max]` の1区間しか持てないため、**外れ値（Outlier）に極めて弱い**という問題がある - 例：あるブロックレンジに `1000`〜`2000` の値が格納されている状態で、`1000000` という値が1件だけ挿入（またはHOT更新失敗等で別ページから移動）されたとする - `minmax` の場合：要約区間が `[1000, 1000000]` に拡大し、幅が約1000倍になる。結果として `WHERE col = 50000` のようなクエリでもこのブロックレンジをスキップできず、不要なSequential Scan（Bitmap Heap Scan）が発生する - `minmax-multi` の場合：要約を `[1000, 2000]` と `1000000`（単一値）の2つに分けて保持できるため、`2001`〜`999999` の間にある検索キーに対して引き続きこのブロックレンジを除外（スキップ）できる # アルゴリズム ## 要約データの構造 - 各ブロックレンジの要約は、**区間（range）** `[min, max]` と **単一値（point）** の集合（`brin_minmax_multi.c` の `Ranges` 構造体） - 区間は境界値を2つ、点は1つ消費する - 制約: $2 \times (\text{区間数}) + (\text{点の数}) \le$ `values_per_range`（デフォルト32、指定可能範囲は8〜256） - 区間同士は重ならず、区間・点はそれぞれソートされた状態で保持される - 区間の「間隔（gap）」を測るため、演算子クラスは **distance関数**（サポートプロシージャ11、例: `brin_minmax_multi_distance_int4`）を提供する - 整数なら $b - a$、timestampなら時間差、`inet` ならアドレス差、といった型ごとの「距離」 ## 値の追加（add_value）とcompaction 1. 新しい値はまずソートされていないバッファに追記される（毎回ソートするのを避けるため、メモリ上では `values_per_range` の数倍の領域を確保している） 2. バッファが一杯になるか、ディスクに書き出す（serialize）タイミングで **compaction** を行う 1. 点をソートして重複を除去する 2. 区間と点を「区間のリスト」（点は `min = max` の縮退区間）に展開してソートし、重なっている区間をマージする 3. 隣接する区間の間のgap `distance(r[i].max, r[i+1].min)` を全て計算し、**大きい順に並べる** 4. 上位 `values_per_range / 2 - 1` 個のgapだけを残し、それ以外のgapを埋める（＝隣り合う区間を結合する） - 残す境界値は「全体の最小値・最大値」と「残すgapの両端」なので、結果の区間数は最大 `values_per_range / 2` 個になる - 結合後に `min = max` になったものは点として保存される（1スロットで済む） - 要するに、**値が密集している部分を区間にまとめ、大きな空白区間（gap）を優先的に残す**貪欲法 - 情報は損失するが、結合後の区間は必ず元の値を全て包含するため、偽陰性（本来ヒットすべきブロックの除外）は起きない ## 検索（consistent） - `col = k`: `k` が含まれる区間があるか、または `k` と一致する点があるかを二分探索で調べる。どちらも無ければこのブロックレンジはスキップ - `col < k`, `col >= k` などの不等号: 全体の最小値・最大値だけを見れば判定できる（この場合は `minmax` と同等の効果） - 偽陽性（区間内だが実際にはその値が無い）は起こり得るので、ヒットしたブロックはBitmap Heap Scanで再チェック（recheck）される ## 要約の統合（union） - 並列ビルドや `brin_summarize_range` などで2つの要約を統合する場合も、両方の区間・点を連結してから上記と同じcompactionを行う ## Running example 簡単のためバッファの存在は無視し、`values_per_range = 8`（最小値）でシリアライズ時のcompactionだけを追う。整数カラムで、distanceは差 $b - a$ とする。 ### Step 1: 初回の要約 あるブロックレンジに次の9個の値が格納されているとする。 `10, 12, 15, 20, 25, 30, 500, 1000, 1020` 点として持つと9スロット必要で、上限8を超えるのでcompactionする。各値を縮退区間とみなし、隣接gapを計算する。 | gap | 距離 | | --- | ---: | | 10 → 12 | 2 | | 12 → 15 | 3 | | 15 → 20 | 5 | | 20 → 25 | 5 | | 25 → 30 | 5 | | 30 → 500 | **470** | | 500 → 1000 | **500** | | 1000 → 1020 | **20** | 残せるgapは $8/2 - 1 = 3$ 個なので、大きい順に `500→1000`(500), `30→500`(470), `1000→1020`(20) を残す。 境界値は「全体のmin/max」＋「残すgapの両端」: - 全体: `10`, `1020` - gap: `30, 500` / `500, 1000` / `1000, 1020` ソートすると `10, 30, | 500, 500, | 1000, 1000, | 1020, 1020` となり、2つずつペアにすると: - 区間 `[10, 30]`（2スロット） - 点 `500`, `1000`, `1020`（各1スロット） 合計5スロットで上限8に収まる。`10〜30` の密集部分は1つの区間にまとめられ、大きな空白は残っている。 ### Step 2: 値の追加 その後、このブロックレンジに `505, 510, 990, 995` が挿入された。展開すると `[10,30], 500, 505, 510, 990, 995, 1000, 1020` で、スロット数は $2 + 7 = 9$ となり上限8を超えるのでcompactionする（上限内に収まっている間はcompactionはスキップされる）。 | gap | 距離 | | --- | ---: | | 30 → 500 | **470** | | 500 → 505 | 5 | | 505 → 510 | 5 | | 510 → 990 | **480** | | 990 → 995 | 5 | | 995 → 1000 | 5 | | 1000 → 1020 | **20** | 上位3つ `510→990`(480), `30→500`(470), `1000→1020`(20) を残す。境界値は `10, 1020` と `510, 990` / `30, 500` / `1000, 1020` で、ソートすると `10, 30, | 500, 510, | 990, 1000, | 1020, 1020` となり: - 区間 `[10, 30]` - 区間 `[500, 510]`（点 `500, 505, 510` が結合された） - 区間 `[990, 1000]`（点 `990, 995, 1000` が結合された） - 点 `1020` 合計 $2+2+2+1 = 7$ スロット。 ### Step 3: 検索 この要約に対するクエリの判定: | クエリ | 判定 | 理由 | | --- | --- | --- | | `col = 700` | **スキップ** | どの区間にも含まれず、点 `1020` とも一致しない | | `col = 503` | スキャン（偽陽性） | `[500, 510]` に含まれるが、実際には `503` は存在しない | | `col = 20` | スキャン | `[10, 30]` に含まれる（実際に存在する） | | `col = 1010` | **スキップ** | `[990, 1000]` と点 `1020` の間のgapに落ちる | | `col < 5` | **スキップ** | 全体の最小値が `10` | | `col > 1000` | スキャン | 全体の最大値が `1020` | 同じデータに対して従来の `minmax` は `[10, 1020]` の1区間しか持たないため、`col = 700` や `col = 1010` でもこのブロックレンジをスキップできない。 # 参考 - [PostgreSQL Documentation: Built-in Operator Classes for BRIN](https://www.postgresql.org/docs/current/brin-builtin-opclasses.html) - [postgres/src/backend/access/brin/brin_minmax_multi.c](https://github.com/postgres/postgres/blob/master/src/backend/access/brin/brin_minmax_multi.c) - [PostgreSQL 14 Internals (Part III) - BRIN indexes](https://postgrespro.com/blog/pgsql/5967951)