bloom 提供基於 Bloom filters 的索引存取方法。
Bloom filter 是一種空間效率高的資料結構，用於測試元素是否為集合的成員。 在索引存取方法的情況下，它允許透過在索引建立時確定大小的簽章快速排除不匹配的元組。
簽章是有索引屬性的有損表示，因此容易報告誤判； 也就是說，可能會報告某個元素在集合中，但實際上並非如此。 因此，必須使用堆積條目的實際屬性值重新檢查索引搜尋結果。 較大的簽章會降低誤判的機率，從而減少無用的堆積訪問次數，但當然也會使索引更大，從而降低掃描速度。
當表格具有許多屬性且查詢測試它們的任意組合時，此類型的索引最有用。 傳統的 btree 索引比 bloom 索引更快，但它可能需要許多 btree 索引才能支援所有可能的查詢，而只需要單個 bloom 索引。 但請注意，bloom 索引僅支援相等查詢，而 btree 索引還可以執行不等式和範圍搜尋。
bloom 索引在其 WITH 子句中接受以下參數
length每個簽章（索引條目）的長度，以位元為單位。 它四捨五入到最接近的 16 的倍數。 預設值為 80 位元，最大值為 4096。
col1 — col32為每個索引欄位產生的位元數。 每個參數的名稱都指向它控制的索引欄位編號。 預設值為 2 位元，最大值為 4095。 將忽略未實際使用的索引欄位的參數。
這是一個建立 bloom 索引的範例
CREATE INDEX bloomidx ON tbloom USING bloom (i1,i2,i3)
WITH (length=80, col1=2, col2=2, col3=4);
索引建立時的簽章長度為 80 位元，屬性 i1 和 i2 映射到 2 位元，屬性 i3 映射到 4 位元。 我們可以省略 length、col1 和 col2 規格，因為它們具有預設值。
這是一個更完整的 bloom 索引定義和使用範例，以及與等效 btree 索引的比較。 bloom 索引比 btree 索引小得多，並且可以表現更好。
=# CREATE TABLE tbloom AS
SELECT
(random() * 1000000)::int as i1,
(random() * 1000000)::int as i2,
(random() * 1000000)::int as i3,
(random() * 1000000)::int as i4,
(random() * 1000000)::int as i5,
(random() * 1000000)::int as i6
FROM
generate_series(1,10000000);
SELECT 10000000
對這個大型表格進行循序掃描需要很長時間
=# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451;
QUERY PLAN
------------------------------------------------------------------------------------------------------
Seq Scan on tbloom (cost=0.00..2137.14 rows=3 width=24) (actual time=16.971..16.971 rows=0 loops=1)
Filter: ((i2 = 898732) AND (i5 = 123451))
Rows Removed by Filter: 100000
Planning Time: 0.346 ms
Execution Time: 16.988 ms
(5 rows)
即使定義了 btree 索引，結果仍然是循序掃描
=# CREATE INDEX btreeidx ON tbloom (i1, i2, i3, i4, i5, i6);
CREATE INDEX
=# SELECT pg_size_pretty(pg_relation_size('btreeidx'));
pg_size_pretty
----------------
3976 kB
(1 row)
=# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451;
QUERY PLAN
------------------------------------------------------------------------------------------------------
Seq Scan on tbloom (cost=0.00..2137.00 rows=2 width=24) (actual time=12.805..12.805 rows=0 loops=1)
Filter: ((i2 = 898732) AND (i5 = 123451))
Rows Removed by Filter: 100000
Planning Time: 0.138 ms
Execution Time: 12.817 ms
(5 rows)
在表格上定義 bloom 索引比 btree 更能處理此類型的搜尋
=# CREATE INDEX bloomidx ON tbloom USING bloom (i1, i2, i3, i4, i5, i6);
CREATE INDEX
=# SELECT pg_size_pretty(pg_relation_size('bloomidx'));
pg_size_pretty
----------------
1584 kB
(1 row)
=# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451;
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on tbloom (cost=1792.00..1799.69 rows=2 width=24) (actual time=0.388..0.388 rows=0 loops=1)
Recheck Cond: ((i2 = 898732) AND (i5 = 123451))
Rows Removed by Index Recheck: 29
Heap Blocks: exact=28
-> Bitmap Index Scan on bloomidx (cost=0.00..1792.00 rows=2 width=0) (actual time=0.356..0.356 rows=29 loops=1)
Index Cond: ((i2 = 898732) AND (i5 = 123451))
Planning Time: 0.099 ms
Execution Time: 0.408 ms
(8 rows)
現在，btree 搜尋的主要問題是，當搜尋條件沒有約束前導索引欄位時，btree 的效率很低。 btree 更好的策略是在每個欄位上建立單獨的索引。 然後，規劃器將選擇類似這樣的東西
=# CREATE INDEX btreeidx1 ON tbloom (i1);
CREATE INDEX
=# CREATE INDEX btreeidx2 ON tbloom (i2);
CREATE INDEX
=# CREATE INDEX btreeidx3 ON tbloom (i3);
CREATE INDEX
=# CREATE INDEX btreeidx4 ON tbloom (i4);
CREATE INDEX
=# CREATE INDEX btreeidx5 ON tbloom (i5);
CREATE INDEX
=# CREATE INDEX btreeidx6 ON tbloom (i6);
CREATE INDEX
=# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451;
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on tbloom (cost=24.34..32.03 rows=2 width=24) (actual time=0.028..0.029 rows=0 loops=1)
Recheck Cond: ((i5 = 123451) AND (i2 = 898732))
-> BitmapAnd (cost=24.34..24.34 rows=2 width=0) (actual time=0.027..0.027 rows=0 loops=1)
-> Bitmap Index Scan on btreeidx5 (cost=0.00..12.04 rows=500 width=0) (actual time=0.026..0.026 rows=0 loops=1)
Index Cond: (i5 = 123451)
-> Bitmap Index Scan on btreeidx2 (cost=0.00..12.04 rows=500 width=0) (never executed)
Index Cond: (i2 = 898732)
Planning Time: 0.491 ms
Execution Time: 0.055 ms
(9 rows)
儘管此查詢的執行速度比任何一個單一索引都快得多，但我們在索引大小方面付出了代價。 每個單欄 btree 索引佔用 2 MB，因此所需的總空間為 12 MB，是 bloom 索引使用的空間的八倍。
bloom 索引的運算子類別只需要索引資料類型的雜湊函數和用於搜尋的等式運算子。 此範例顯示了 text 資料類型的運算子類別定義
CREATE OPERATOR CLASS text_ops
DEFAULT FOR TYPE text USING bloom AS
OPERATOR 1 =(text, text),
FUNCTION 1 hashtext(text);
模組中僅包含 int4 和 text 的運算子類別。
搜尋僅支援 = 運算子。 但將來可以增加對具有聯集和交集運算的陣列的支援。
bloom 存取方法不支援 UNIQUE 索引。
bloom 存取方法不支援搜尋 NULL 值。
Teodor Sigaev <teodor@postgrespro.ru>, Postgres Professional, Moscow, Russia
Alexander Korotkov <a.korotkov@postgrespro.ru>, Postgres Professional, Moscow, Russia
Oleg Bartunov <obartunov@postgrespro.ru>, Postgres Professional, Moscow, Russia
如果您在文件中發現任何不正確、與特定功能的經驗不符或需要進一步澄清的地方，請使用此表單報告文件問題。