IndexType：Bloom

前言

終於到了我們的目標了，今天要講解db是如何使用bloom這個index type的。
也許你會困惑，bloom filter不是只能確定資料可能否存在，回傳true/false，
那麼他是如何將值取出的呢？
其實，確實是先經過bloom filter做出第一批的篩選，將可能存在的搜尋值列出，
然再將剩餘的值經過一般的Bitmap Heap Scan做搜尋與驗證。

我們將介紹在db中使用bloom index type，
概念在大部分db大同小異，這裡使用postgres作為範例。

Bloom in db

加上Index

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

實際使用

前處理我們建立了一張table叫tbloom，
裡面有i1， i2， i3， i4， i5， i6這幾個欄位;
插入1000萬筆紀錄來做分析。

分別對這些欄位
做b+tree index 名為btreeidx
與bloom index 名為bloomidx

沒使用任何index的query

=# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451;
                                                 QUERY PLAN
-------------------------------------------------------------------​-----------------------------------------
 Seq Scan on tbloom  (cost=0.00..213694.08 rows=1 width=24) 
                     (actual time=1445.438..1445.438 rows=0 loops=1)
   Filter: ((i2 = 898732) AND (i5 = 123451))
   Rows Removed by Filter: 10000000
 Planning time: 0.177 ms
 Execution time: 1445.473 ms
(5 rows)

可以看到直接掃整張table，因為n非常大，所以耗費方非常多時間。

使用b+tree的query

=# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451;
                                                           QUERY PLAN
-------------------------------------------------------------------​-------------------------------------------------------------
 Index Only Scan using btreeidx on tbloom  (cost=0.56..298311.96 rows=1 width=24) 
                                           (actual time=445.709..445.709 rows=0 loops=1)
   Index Cond: ((i2 = 898732) AND (i5 = 123451))
   Heap Fetches: 0
 Planning time: 0.193 ms
 Execution time: 445.770 ms
(5 rows)

使用了b+tree因只需要index only scan所以降低了Execution time

使用bloom的query

=# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451;
                                                        QUERY PLAN
-------------------------------------------------------------------​--------------------------------------------------------
 Bitmap Heap Scan on tbloom  (cost=178435.39..178439.41 rows=1 width=24) 
                             (actual time=76.698..76.698 rows=0 loops=1)
   Recheck Cond: ((i2 = 898732) AND (i5 = 123451))
   Rows Removed by Index Recheck: 2439
   Heap Blocks: exact=2408
   ->  Bitmap Index Scan on bloomidx  (cost=0.00..178435.39 rows=1 width=0)                           (actual time=72.455..72.455 rows=2439 loops=1)
         Index Cond: ((i2 = 898732) AND (i5 = 123451))
 Planning time: 0.475 ms
 Execution time: 76.778 ms
(8 rows)

這裡使用到了bloom filter，可以看到bloom取出了2439筆資料，
因bloom filter 會有Type I error，所以還需要做再次的過濾。
所以這裡Heap Blocks: exact=2408利用i2 = 898732 OR i5 = 123451移除了2408筆資料，
最後在Index Cond: ((i2 = 898732) AND (i5 = 123451))
移除到最後僅僅剩下我們的真正要的8筆資料。

比較結果

我們可以使用
SELECT pg_size_pretty(pg_relation_size('{{index name}}'));
來得知index的大小

可以看到大小與執行時間具有明顯的差距，
大小因為Bloom的特性，大小大致為bit array的大小，
執行時間因做了第一層過濾，
再用少量的資料做b+tree的搜索，大幅縮短了執行時間。

結語

終於介紹完了bloom filter與bloom index type，
想必大家一定對於index type有更深入裡的解。
可以依照資料應用的情境制定正確的index type，優化查找速度。

參考資料

1. 以Postgresql為主，再聊聊資料庫 PostgreSQL Bloom index 介紹
2. F.5. bloom
3. trying-out-postgres-bloom-indexes
4. PostgreSQL execution plan visualizer