概觀#

其他索引都是為了快速找到所需的列而最佳化，BRIN 卻是為了濾掉不需要的列而設計。

這個存取方法主要是為數 TB 以上的大表而生，因此較小的索引體積優先於搜尋精確度。

為加速搜尋，整張表被切成若干範圍（range），名稱由此而來：Block Range Index。每個範圍含數個頁面。

• 索引不存放 TID，只保留每個範圍的摘要資訊（summary）
• 對序數型別而言，最簡單的情況下就是該範圍的最小值與最大值；不同運算子類別可能蒐集不同的範圍值資訊
• 範圍中的頁面數，在索引建立時依 pages_per_range 儲存參數（預設 128）決定

若查詢條件參照到被索引的欄位，所有保證沒有匹配的範圍都可被跳過。其餘範圍的頁面由索引以有損 bitmap（lossy bitmap）回傳，這些頁面的所有列都必須重新檢查。

因此 BRIN 適用於「值有局部性」的欄位——亦即彼此存放得近的值，其摘要資訊性質也相近。

對序數型別而言，這意味著值必須以遞增或遞減順序存放，也就是實體位置與邏輯順序之間有高度相關性（correlation）。對其他類型的摘要資訊，「性質相近」的意涵則可能有所不同。

把 BRIN 想成循序 heap 掃描的加速器，而非傳統意義下的索引，並不算錯。它也可視為分割（partitioning）的替代方案——每個範圍就是一個虛擬分割。

範例#

demo 資料庫沒有大到適合 BRIN 的表，但我們可以想像分析報表需要一張反正規化的表，含某機場所有起降航班的摘要資訊，細到座位層級。每個機場的資料在對應時區的午夜一到就每日更新，加入的資料既不更新也不刪除。

CREATE TABLE flights_bi(
   airport_code char(3),
   airport_coord point,         -- 機場座標
   airport_utc_offset interval, -- 時區
   flight_no char(6),
   flight_type text,            -- 出發或抵達
   scheduled_time timestamptz,
   actual_time timestamptz,
   aircraft_code char(3),
   seat_no varchar(4),
   fare_conditions varchar(10), -- 艙等
   passenger_id varchar(20),
   passenger_name text
);

資料載入以巢狀迴圈模擬：外層迴圈對應天數（demo 資料庫存放一年的資料），內層迴圈依時區。因此即使迴圈內未明確排序，載入的資料至少會依時間與機場大致有序。

書中載入的副本約 1 GB、約 3000 萬列（總大小 4129 MB）。以預設設定建出的 BRIN 索引只佔 184 kB。

相同欄位的 B-tree 索引是它的一千倍大（210 MB），即使啟用了資料去重（PostgreSQL 13）也一樣。

B-tree 的效率確實高得多，但對真正的大表而言，這額外的體積可能是負擔不起的奢侈品。

頁面佈局#

BRIN 索引的第零頁稱為 metapage，保存索引結構的資訊。距離 metadata 一定偏移量之後，是存放摘要資訊的頁面——這類頁面中的每個索引項目，含有某個 block range 的摘要。

metapage 與摘要資訊之間的空間，由範圍對照表（range map，有時也稱 reverse map，故常縮寫為 revmap）佔據。

revmap 實質上是一個指向對應索引列的指標陣列，陣列中的索引編號即範圍編號。

隨著表擴張，revmap 的體積也隨之成長。若對照表塞不進配給的頁面，它會佔用下一個頁面，原先位於該頁的所有索引項目則轉移到其他頁面。由於一個頁面可容納許多指標，這類轉移相當罕見。

=> SELECT pagesperrange, lastrevmappage
FROM brin_metapage_info(get_raw_page(
  'flights_bi_scheduled_time_idx', 0
));
 pagesperrange | lastrevmappage
−−−−−−−−−−−−−−−+−−−−−−−−−−−−−−−−
           128 |              4
(1 row)

=> SELECT *
FROM brin_revmap_data(get_raw_page(
  'flights_bi_scheduled_time_idx', 1
));
  pages
−−−−−−−−−−
 (6,197)
 (6,198)
 (6,199)
 ...
(1360 rows)

=> SELECT itemoffset, blknum, value
FROM brin_page_items(
  get_raw_page('flights_bi_scheduled_time_idx', 6),
  'flights_bi_scheduled_time_idx'
)
ORDER BY blknum
LIMIT 3 \gx
−[ RECORD 1 ]−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
itemoffset | 197
blknum     | 0
value      | {2016−08−15 02:45:00+03 .. 2016−08−15 16:20:00+03}
−[ RECORD 2 ]−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
itemoffset | 198
blknum     | 128
value      | {2016−08−15 05:50:00+03 .. 2016−08−15 18:55:00+03}

搜尋#

若查詢條件受 BRIN 索引支援，執行器會掃描 revmap 與每個範圍的摘要資訊：

1. 若某範圍的資料可能匹配搜尋鍵，該範圍所屬的所有頁面都加入 bitmap
2. 資料與搜尋鍵的比對由一致性函式執行，它負責詮釋範圍的摘要資訊
3. 尚未摘要的範圍一律加入 bitmap

由於 BRIN 不保存個別元組的 ID，bitmap 永遠是有損的。

取得的 bitmap 以一般方式掃描資料表。值得一提的是，heap 頁面的讀取是循序發生的，一個 block range 接著一個，而且會運用預取（prefetching）。

摘要資訊的更新#

插入值#

新元組被加進 heap 頁面時，對應索引範圍的摘要資訊隨之更新：

1. 範圍編號由頁面編號經簡單算術運算算出（頁面編號整除範圍大小）
2. 再由 revmap 定位到摘要資訊
3. addition 函式判定當前摘要是否需要擴張
4. 若需要擴張且該頁有足夠可用空間，就原地完成（不新增索引項目）

若無法原地更新，就新增一個項目並修改 revmap。

範圍摘要化#

以上談的都是「新元組落在已摘要範圍」的情境。索引建立時，所有既有範圍都會被摘要，但隨著表成長，新頁面可能落在這些範圍之外。

• 若索引建立時啟用了 autosummarize 儲存參數（預設關閉），新範圍會立刻被摘要
• 但在資料倉儲中，列通常是大批量加入而非逐一加入，這個模式可能嚴重拖慢插入

摘要化以非同步方式進行：在資料表 vacuum 期間，或呼叫 brin_summarize_new_values 函式手動觸發（brin_summarize_range 則處理單一範圍）。

範圍摘要化不會鎖住資料表阻擋更新：

1. 程序開始時，先為該範圍在索引中插入一個 placeholder 項目
2. 若掃描該範圍期間資料有變動，placeholder 會被這些變動的摘要資訊更新
3. 接著 union 函式把這份資料與對應範圍的摘要資訊合併

理論上，刪除部分列之後摘要資訊有時可以縮小。但 GiST 索引能在頁面分裂後重新分配資料，BRIN 的摘要資訊卻永不縮小、只會變寬。

這裡通常不需要縮小，因為資料儲存區一般只用於追加新資料。你可以對某範圍呼叫 brin_desummarize_range 手動刪除摘要資訊以便重新摘要，但無從得知哪些範圍會因此受益。

因此，BRIN 主要針對體積極大的表：這些表要嘛更新極少、且新列大多加在檔案末端，要嘛完全不更新。它主要用於資料倉儲中建構分析報表。

minmax 類別#

對允許比較的資料型別，摘要資訊至少含最大值與最小值。對應的運算子類別名稱中含 minmax（共 26 個，如 bit_minmax_ops、uuid_minmax_ops 等）。

支援函式：

 amprocnum |         amproc
−−−−−−−−−−−+−−−−−−−−−−−−−−−−−−−−−−−−
         1 | brin_minmax_opcinfo
         2 | brin_minmax_add_value
         3 | brin_minmax_consistent
         4 | brin_minmax_union
(4 rows)

第一個函式回傳運算子類別的 metadata；其餘三個前面已述：插入新值、檢查一致性、執行 union。

minmax 類別包含的比較運算子，與 B-tree 中所見完全相同（<、<=、=、>=、>，策略 1 ～ 5）。

該索引哪些欄位#

如前所述，這類索引在列的實體位置與值的邏輯順序相關時運作良好。以範例的表驗證：

=> SELECT attname, correlation, n_distinct
FROM pg_stats
WHERE tablename = 'flights_bi'
ORDER BY correlation DESC NULLS LAST;
      attname       |  correlation   |  n_distinct
−−−−−−−−−−−−−−−−−−−−+−−−−−−−−−−−−−−−−+−−−−−−−−−−−−−−
 scheduled_time     |      0.9999949 |        25926
 actual_time        |      0.9999948 |        34469
 fare_conditions    |      0.7976897 |            3
 flight_type        |      0.4981733 |            2
 airport_utc_offset |      0.4440067 |           11
 aircraft_code      |     0.19249801 |            8
 airport_code       |    0.061483838 |          104
 seat_no            |   0.0024594965 |          461
 flight_no          |   0.0020146023 |          710
 passenger_id       | −0.00046121294 | 2.610987e+06
 passenger_name     |   −0.012388787 |         8618
 airport_coord      |                |            0
(12 rows)

• 資料依時間有序（scheduled 與 actual 差別極小）：新項目按時序加入，且資料既不更新也不刪除，因此所有列都循序落入表的主 fork
• fare_conditions、flight_type、airport_utc_offset 相關性相對高，但相異值太少
• 其他欄位的相關性太低，用 minmax 運算子類別索引沒什麼意思

範圍大小與搜尋效率#

合適的範圍大小，可依「存放特定值所用的頁面數」來決定。

=> CREATE FUNCTION tid2page(t tid) RETURNS integer
LANGUAGE sql
RETURN (t::text::point)[0]::integer;

=> SELECT min(numblk), round(avg(numblk)) avg, max(numblk)
FROM (
  SELECT count(distinct tid2page(ctid)) numblk
  FROM flights_bi
  GROUP BY scheduled_time::date
) t;
 min  | avg  | max
−−−−−−+−−−−−−+−−−−−−
 1192 | 1447 | 1512
(1 row)

擷取某一天的資料時，索引掃描會同時回傳真正需要的列，以及落在同一批範圍中、屬於其他日期的列。

範圍越大，讀進來的多餘邊界值越多——可藉由縮小或放大範圍來調節其數量。

=> EXPLAIN (analyze, buffers, costs off, timing off, summary off)
SELECT * FROM flights_bi
WHERE scheduled_time >= :'d'::timestamptz
  AND scheduled_time < :'d'::timestamptz + interval '1 day';
                              QUERY PLAN
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
 Bitmap Heap Scan on flights_bi (actual rows=81964 loops=1)
   Recheck Cond: ((scheduled_time >= '2016−08−15 02:45:00+03'::ti...
   Rows Removed by Index Recheck: 11606
   Heap Blocks: lossy=1536
   Buffers: shared hit=1561
   −> Bitmap Index Scan on flights_bi_scheduled_time_idx
       (actual rows=15360 loops=1)
       Index Cond: ((scheduled_time >= '2016−08−15 02:45:00+03'::...
       Buffers: shared hit=25
(11 rows)

我們可把某查詢的 BRIN 效率因子（efficiency factor）定義為：索引掃描所跳過的頁面數，與表中總頁面數之比。

• 效率因子為 0 時，索引存取退化成循序掃描（不計額外開銷）
• 效率因子越高，需讀取的頁面越少
• 但由於有些頁面含有待回傳的資料、無法跳過，效率因子永遠小於 1

此例中效率因子為 (528417 − 1561) / 528417 ≈ 0.997（528,417 為表中頁面數）。

單一數值得不出有意義的結論。即使資料均勻、相關性理想，效率仍會浮動——至少範圍邊界不會對齊頁面邊界。唯有把效率因子當成隨機變數並分析其分佈，才能看到全貌。

書中對全年每一天執行查詢、解析 EXPLAIN 的 JSON 輸出，並以盒鬚圖（box plot）呈現三種範圍大小的效率分佈：

範圍大小	索引體積
32 pages/range	529 kB
128 pages/range（預設）	184 kB
512 pages/range	72 kB

結論一如預期：即使範圍相當大，搜尋精確度與效率仍然很高（皆在 0.99 以上）。

屬性#

BRIN 的屬性是寫死的，不隨運算子類別而變。

存取方法層級：

 amname |     name      | pg_indexam_has_property
−−−−−−−−+−−−−−−−−−−−−−−−+−−−−−−−−−−−−−−−−−−−−−−−−−
 brin   | can_order     | f
 brin   | can_unique    | f
 brin   | can_multi_col | t
 brin   | can_exclude   | f
 brin   | can_include   | f
(5 rows)

• 不支援排序與唯一性
• 由於 BRIN 永遠回傳 bitmap，不支援排除約束
• INCLUDE 欄位也毫無意義——BRIN 連索引鍵本身都不存放
• 可建立多欄 BRIN 索引：每個欄位的摘要資訊各自蒐集、存於獨立的索引項目，但共用同一份 revmap。這在「同一個範圍大小適用於所有被索引欄位」時有用

另一種做法：為數個欄位分別建立 BRIN 索引，並利用 bitmap 可以合併的特性（執行計畫中會出現 BitmapAnd）。

=> CREATE INDEX ON flights_bi USING brin(airport_utc_offset);
=> EXPLAIN (analyze, costs off, timing off, summary off)
SELECT *
FROM flights_bi
WHERE scheduled_time >= :'d'::timestamptz
  AND scheduled_time < :'d'::timestamptz + interval '1 day'
  AND airport_utc_offset = '08:00:00';
                             QUERY PLAN
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
 Bitmap Heap Scan on flights_bi (actual rows=1658 loops=1)
   Recheck Cond: ((scheduled_time >= '2016−08−15 02:45:00+03'::ti...
   Rows Removed by Index Recheck: 14077
   Heap Blocks: lossy=256
   −> BitmapAnd (actual rows=0 loops=1)
       −> Bitmap Index Scan on flights_bi_scheduled_time_idx (act...
       −> Bitmap Index Scan on flights_bi_airport_utc_offset_idx ...
(9 rows)

索引層級：clusterable、index_scan、backward_scan 皆為 f，只有 bitmap_scan 為 t——bitmap 掃描是唯一支援的存取型態。

缺少叢集化（clusterization）看似令人費解：BRIN 對列的實體順序敏感，理當支援重排以最大化效率。

但考量重建表所需的處理成本與額外磁碟空間，對大表做叢集化本來就是奢侈品。何況如 flights_bi 所示，資料倉儲中的某種程度有序，往往是自然發生的。

欄位層級：唯一可用的屬性是 NULL 支援（search_nulls 為 t）。為追蹤範圍中的 NULL 值，摘要資訊提供了獨立屬性：

 hasnulls | allnulls |         value
−−−−−−−−−−+−−−−−−−−−−+−−−−−−−−−−−−−−−−−−−−−−−−
 f        | f        | {03:00:00 .. 03:00:00}
(1 row)

minmax-multi 類別（PostgreSQL 14）#

降低 fillfactor 儲存參數可在頁面留下更多空間給日後更新，稍微緩解此效應。但為了這個去擴大一張本已巨大的表，真的值得嗎？何況刪除本來就會在既有頁面釋出空間，等於為那些原本會落到檔案末端的新元組布下陷阱。

延伸：模擬相關性被破壞的過程

刪掉隨機 0.1% 的列並 vacuum 以清出空間：

=> WITH t AS (
  SELECT ctid
  FROM flights_bi TABLESAMPLE BERNOULLI(0.1) REPEATABLE(0)
)
DELETE FROM flights_bi
WHERE ctid IN (SELECT ctid FROM t);
DELETE 30180
=> VACUUM flights_bi;

接著為某時區加入新一天的資料（直接複製前一天）：

=> INSERT INTO flights_bi
SELECT airport_code, airport_coord, airport_utc_offset,
  flight_no, flight_type, scheduled_time + interval '1 day',
  actual_time + interval '1 day', aircraft_code, seat_no,
  fare_conditions, passenger_id, passenger_name
FROM flights_bi
WHERE date_trunc('day', scheduled_time) = '2017-08-15'
  AND airport_utc_offset = '03:00:00';
INSERT 0 40532

這次刪除足以在所有或幾乎所有範圍中釋出空間。新元組落進檔案中段的頁面，自動撐大了範圍。例如第一個範圍的摘要原本涵蓋不到一天，現在涵蓋了整整一年：

                       value
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
 {2016−08−15 02:45:00+03 .. 2017−08−16 09:35:00+03}
(1 row)

查詢指定的日期越早，必須掃描的範圍就越多——效率因子從 0.99 以上崩落到 0 至 1 之間全域散佈的災難程度。

解法是讓摘要資訊更精緻一些：不存單一的連續範圍，而是存數個較小的範圍，合起來涵蓋所有值。

如此一來，其中一個範圍可涵蓋主要資料集，其餘的則處理偶發的離群值。

這項功能由 minmax-multi 運算子類別提供（共 19 個，如 timestamptz_minmax_multi_ops）。

相較 minmax，minmax-multi 多了一個計算值之間距離的支援函式，用來決定範圍長度——運算子類別會設法縮小它：

 amprocnum |                amproc
−−−−−−−−−−−+−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
         1 | brin_minmax_multi_opcinfo
         2 | brin_minmax_multi_add_value
         3 | brin_minmax_multi_consistent
         4 | brin_minmax_multi_union
         5 | brin_minmax_multi_options
        11 | brin_minmax_multi_distance_numeric
(6 rows)

運算子則與 minmax 類別完全相同。

minmax-multi 類別可接受 values_per_range 參數（預設 32），定義每個範圍允許的最大摘要值數量。

一個被摘要的值區間以兩個數字表示，而單獨的點只需要一個。若值的額度不夠，部分區間會被縮減。

=> DROP INDEX flights_bi_scheduled_time_idx;
=> CREATE INDEX ON flights_bi USING brin(
   scheduled_time timestamptz_minmax_multi_ops(
     values_per_range = 16
   )
);

inclusion 類別#

inclusion 運算子類別為特定範圍提供的摘要資訊，是該範圍中所有值的邊界框（bounding box）。這類類別數量不多：box_inclusion_ops、inet_inclusion_ops、range_inclusion_ops。

支援函式清單多了一個合併兩個值的必要函式，以及一批選用函式（如 bound_box、box_contain）。

處理可比較的值時，我們仰賴的是它們的相關性；但對其他資料型別，這項統計根本不會被蒐集，因此難以預測 inclusion 型 BRIN 索引的效率。

更糟的是，相關性大幅影響索引掃描的成本估算。統計不可得時，它被視為零。於是規劃器無從分辨精確與模糊的 inclusion 索引，通常乾脆完全避免使用它們。

PostGIS（3.3.0 起）會蒐集空間資料的相關性統計。

以本例而言，可以推測在機場座標上建索引是有意義的，因為經度應與時區相關。

與 GiST 的述詞不同，BRIN 的摘要資訊與被索引資料型別相同，因此不容易直接為「點」建索引。變通做法是建立運算式索引，把點轉成退化的矩形：

=> CREATE INDEX ON flights_bi USING brin(box(airport_coord))
WITH (pages_per_range = 8);

此索引佔 3816 kB；以相同範圍大小在時區上建的索引，體積也差不多（3820 kB）。

此類別的運算子與 GiST 運算子類似，例如 BRIN 索引可加速搜尋某區域內的點。但如前所述，除非關閉循序掃描，規劃器不會採用索引掃描：

=> EXPLAIN (costs off)
SELECT *
FROM flights_bi
WHERE box(airport_coord) <@ box '135,45,140,50';
                         QUERY PLAN
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
 Seq Scan on flights_bi
   Filter: (box(airport_coord) <@ '(140,50),(135,45)'::box)
(2 rows)

bloom 類別（PostgreSQL 14）#

基於 Bloom filter 的運算子類別，讓 BRIN 得以用於任何支援等值操作且定義了雜湊函式的資料型別。

它們也可用於一般序數型別——當值局部集中在各個範圍中，但實體位置與邏輯順序毫無相關性時。

這類運算子類別名稱含 bloom（共 24 個）。

Bloom filter 原理#

經典的 Bloom filter 是一種能快速檢查「元素是否屬於某集合」的資料結構。它非常精簡，但允許偽陽性：集合可能被認為含有比實際更多的元素。

運作方式：

1. filter 是一個含 m 個位元的陣列（亦稱簽章），初始全為零
2. 選定 k 個不同的雜湊函式，把集合中任一元素對映到簽章的 k 個位元
3. 元素被加入集合時，簽章中對應的每個位元都被設為 1
4. 因此：對應某元素的位元若全為 1，該元素「可能」在集合中；只要有一個位元為 0，該元素「保證」不在

在 BRIN 索引中，filter 處理的是屬於某個範圍的被索引欄位值集合，該範圍的摘要資訊就是建出的 Bloom filter。

參數#

Bloom filter 的精確度取決於簽章長度。理論上，最佳簽章位元數可估為 m = −n·log p / ln²2，其中 n 是集合中的元素數、p 是偽陽性機率。這兩項可用對應的運算子類別參數調整：

但這不保證精確搜尋：被掃描的範圍仍會含有不匹配查詢的多餘列。這種行為肇因於範圍寬度與資料的實體位置，而非 filter 本身的性質。

支援函式清單多了一個雜湊函式（如 hash_numeric）。

由於 Bloom filter 以雜湊為基礎，只支援等值運算子（策略 1）。

範例#

以 flight_no 欄位為例，它的相關性趨近於零，因此對一般的範圍運算子類別毫無用處。維持預設的偽陽性設定，相異值數量則可輕易算出——以八頁的範圍而言，最大值是 22。

範圍更小時這個數字會更低，但運算子類別無論如何都不允許小於 16 的值。

=> CREATE INDEX ON flights_bi USING brin(
  flight_no bpchar_bloom_ops(n_distinct_per_range = 22)
)
WITH (pages_per_range = 8);

=> EXPLAIN (analyze, costs off, timing off, summary off)
SELECT *
FROM flights_bi
WHERE flight_no = 'PG0001';
                             QUERY PLAN
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
 Bitmap Heap Scan on flights_bi (actual rows=5192 loops=1)
   Recheck Cond: (flight_no = 'PG0001'::bpchar)
   Rows Removed by Index Recheck: 122894
   Heap Blocks: lossy=2168
   −> Bitmap Index Scan on flights_bi_flight_no_idx (actual rows=...
       Index Cond: (flight_no = 'PG0001'::bpchar)
(6 rows)

範圍大小	索引體積
2 pages/range	14.8 MB
4 pages/range	7.4 MB
8 pages/range	3.7 MB