IndexType： BRIN

前言

昨天介紹了 B+Tree，今天就來介紹B+Tree的變形BRIN。
先回憶一下B+Tree的長相，
每個internel node確確實實代表著下個節點的區間;
每個leaf node都會確確實實的對應上資料節點;
假設今天更改一下，一樣是B+Tree的結構，
但是每個node不代表一筆紀錄，而是代表一個區間，
這樣一來就可以大大的降低tree的高度，
當如果要找一個範圍的資料，只需要先抓出數個小區間，
再經過過濾，就可以比較快速的找到目標。

##　BRIN資料結構
BRIN基本上仍然是符合B+Tree的長相，
不過每個node都是以一個範圍來表示。

使用場景

1. 有序的大量資料
2. 物聯網(IOT)數據
3. 時間序列資料處理

BRIN in db

加上Index

CREATE INDEX "{{INDEX_NAME}}" ON "{{TABLE_NAME}}" USING BRIN({{COL_NAME}});

實際使用

前處理我們建立了兩張相同結構的table，
TABLE_A與TABLE_B，
兩表都有欄位 ts 資料型態為timestamp not null，
分別使用B+Tree與BRIN 對欄位ts來做index，
並且插入1000萬筆紀錄來做分析。

1. B+tree

explain analyze
select * from TABLE_A
where ts between timestamp '2000-02-01 00:00:00' and timestamp '2000-03-01 00:00:00';
------------------------------------------------------------
  Index Scan using table_a_btree on TABLE_A (cost=0.43..91922.05 rows=2526931 width=16)
                                            (actual time=40.380..1400.256 rows=2505601 loops=1) 
   Index Cond: ((ts >= '2000-02-01 00:00:00'::timestamp without time zone) AND (ts <= '2000-03-01 00:00:00'::timestamp without time zone))
 Planning time: 1.009 ms  
 Execution time: 1653.522 ms

2. BRIN

explain analyze
select * from TABLE_B
where ts between timestamp '2000-02-01 00:00:00' and timestamp '2000-03-01 00:00:00';
------------------------------------------------------------
Bitmap Heap Scan on TABLE_B (cost=663.60..93370.54 rows=2576457 width=16) 
                            (actual time=5.988..441.199 rows=2505601 loops=1)
  Recheck Cond: ((ts >= '2000-02-01 00:00:00'::timestamp without time zone) AND (ts <= '2000-03-01 00:00:00'::timestamp without time zone)) 
  Rows Removed by Index Recheck: 4479
  Heap Blocks: lossy=13568
  ->  Bitmap Index Scan on TABLE_B  (cost=0.00..19.49 rows=2576796 width=0)
                                    (actual time=0.837..0.837 rows=135680 loops=1) 
        Index Cond: ((ts >= '2000-02-01 00:00:00'::timestamp without time zone) AND (ts <= '2000-03-01 00:00:00'::timestamp without time zone))
Planning time: 0.428  ms
Execution time: 615.363 ms

比較結果

可以看到大小與執行時間具有明顯的差距，
大小因為BRIN的特性，避免每個資料都需要放在一個node中。
執行時間也隨著node的減少，而減少了大部分的高度，大幅縮短了執行時間。

結語

時間序列的搜尋，選擇BRIN會是一個優良的選則，
尤其時間序列查詢時都會查詢一段時間。
就僅僅是個b+tree的變化，就可以有許多的優化。
下次可別B+Tree index從頭用到底!

特別說明，目前postgres的pk只可以使用B+Tree作為default index，
無法使用其他index type。

參考資料

1. PostgreSQL/Index BRIN
2. 以Postgresql為主，再聊聊資料庫 PostgreSQL BRIN index 介紹一
3. Possible to use a BRIN Index on a Primary Key in PostgreSQL
4. PostgreSQL execution plan visualizer