F.5. bloom
Bloom 提供了一種基於 Bloom fliters 索引方法。
Bloom filter 是一種節省空間的資料結構,用於測試元素是否為集合的成員。在使用索引方法時,它透過 signatures(其大小是在建立索引時確定的)快速排除不相符的內容。
Signature 是索引屬性的失真表示,因此很容易誤報。也就是說,可能會回報某個元素在集合中(實際上沒有)。因此,必須使用資料中的實際屬性值來重新檢查索引並搜尋結果。較大的 signature 會減少了誤報的機率,也減少了無效的存取次數,但當然也會使索引變大,造成掃描速度變慢。
當資料表具有許多屬性並且查詢測試它們的任意組合時,這種類型的索引最有用。傳統的 btree 索引會比 Bloom 索引快,但是它可能需要許多 btree 索引來支援所有可能的查詢,而其中一個查詢只需要一個 Bloom 索引。但是請注意,bloom 索引僅支援相等查詢,而 btree 索引也可以用於不相等和範圍查詢。

F.5.1. 參數

Bloom 索引的 WITH 子句接受以下參數:
length
每個 signature(索引項目)的長度(以位元為單位)。四捨五入到最接近的 16 的倍數。預設值為 80 位元,最大值為 4096。
col1 — col32
每個索引欄位產成的位元數。每個參數的名稱指的是它控制的索引欄位的編號。預設值為 2 位元,最大值為 4095。實際未使用的索引欄位的參數將被忽略。

F.5.2. Examples

This is an example of creating a bloom index:
1
CREATE INDEX bloomidx ON tbloom USING bloom (i1,i2,i3)
2
WITH (length=80, col1=2, col2=2, col3=4);
Copied!
The index is created with a signature length of 80 bits, with attributes i1 and i2 mapped to 2 bits, and attribute i3 mapped to 4 bits. We could have omitted the length, col1, and col2 specifications since those have the default values.
Here is a more complete example of bloom index definition and usage, as well as a comparison with equivalent btree indexes. The bloom index is considerably smaller than the btree index, and can perform better.
1
=# CREATE TABLE tbloom AS
2
SELECT
3
(random() * 1000000)::int as i1,
4
(random() * 1000000)::int as i2,
5
(random() * 1000000)::int as i3,
6
(random() * 1000000)::int as i4,
7
(random() * 1000000)::int as i5,
8
(random() * 1000000)::int as i6
9
FROM
10
generate_series(1,10000000);
11
SELECT 10000000
12
=# CREATE INDEX bloomidx ON tbloom USING bloom (i1, i2, i3, i4, i5, i6);
13
CREATE INDEX
14
=# SELECT pg_size_pretty(pg_relation_size('bloomidx'));
15
pg_size_pretty
16
----------------
17
153 MB
18
(1 row)
19
=# CREATE index btreeidx ON tbloom (i1, i2, i3, i4, i5, i6);
20
CREATE INDEX
21
=# SELECT pg_size_pretty(pg_relation_size('btreeidx'));
22
pg_size_pretty
23
----------------
24
387 MB
25
(1 row)
Copied!
A sequential scan over this large table takes a long time:
1
=# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451;
2
QUERY PLAN
3
-------------------------------------------------------------------​-----------------------------------------
4
Seq Scan on tbloom (cost=0.00..213694.08 rows=1 width=24) (actual time=1445.438..1445.438 rows=0 loops=1)
5
Filter: ((i2 = 898732) AND (i5 = 123451))
6
Rows Removed by Filter: 10000000
7
Planning time: 0.177 ms
8
Execution time: 1445.473 ms
9
(5 rows)
Copied!
So the planner will usually select an index scan if possible. With a btree index, we get results like this:
1
=# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451;
2
QUERY PLAN
3
-------------------------------------------------------------------​-------------------------------------------------------------
4
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)
5
Index Cond: ((i2 = 898732) AND (i5 = 123451))
6
Heap Fetches: 0
7
Planning time: 0.193 ms
8
Execution time: 445.770 ms
9
(5 rows)
Copied!
Bloom is better than btree in handling this type of search:
1
=# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451;
2
QUERY PLAN
3
-------------------------------------------------------------------​--------------------------------------------------------
4
Bitmap Heap Scan on tbloom (cost=178435.39..178439.41 rows=1 width=24) (actual time=76.698..76.698 rows=0 loops=1)
5
Recheck Cond: ((i2 = 898732) AND (i5 = 123451))
6
Rows Removed by Index Recheck: 2439
7
Heap Blocks: exact=2408
8
-> Bitmap Index Scan on bloomidx (cost=0.00..178435.39 rows=1 width=0) (actual time=72.455..72.455 rows=2439 loops=1)
9
Index Cond: ((i2 = 898732) AND (i5 = 123451))
10
Planning time: 0.475 ms
11
Execution time: 76.778 ms
12
(8 rows)
Copied!
請注意,這裡的誤報的數量相對較多:被選擇 2439 筆資料要進行確認,但實際上沒有與查詢相符的資料。我們可以透過指定更大的 signature 長度來減少這種情況。在此範例中,建立長度為 200 的索引可將誤報數量減少到 55;但它也使索引大小增加了一倍(至 306 MB),並最終使該查詢的速度變慢(總計 125 毫秒)。
現在,btree 搜搜的主要問題在於,當搜搜條件不限制前導索引欄時,btree 的效率低下。btree 的更好策略是在每欄位上建立一個單獨的索引。然後計劃程序將會選擇規劃以下內容:
1
=# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451;
2
QUERY PLAN
3
-------------------------------------------------------------------​-----------------------------------------------------------
4
Bitmap Heap Scan on tbloom (cost=9.29..13.30 rows=1 width=24) (actual time=0.148..0.148 rows=0 loops=1)
5
Recheck Cond: ((i5 = 123451) AND (i2 = 898732))
6
-> BitmapAnd (cost=9.29..9.29 rows=1 width=0) (actual time=0.145..0.145 rows=0 loops=1)
7
-> Bitmap Index Scan on tbloom_i5_idx (cost=0.00..4.52 rows=11 width=0) (actual time=0.089..0.089 rows=10 loops=1)
8
Index Cond: (i5 = 123451)
9
-> Bitmap Index Scan on tbloom_i2_idx (cost=0.00..4.52 rows=11 width=0) (actual time=0.048..0.048 rows=8 loops=1)
10
Index Cond: (i2 = 898732)
11
Planning time: 2.049 ms
12
Execution time: 0.280 ms
13
(9 rows)
Copied!
儘管此查詢的執行速度比使用單個索引的查詢快得多,但我們在索引大小上付出了很大的代價。每個單欄位 btree 索引佔用 214 MB,因此所需的總空間超過 1.2GB,是 Bloom 索引使用的空間 8 倍以上。

F.5.3. Operator Class Interface

An operator class for bloom indexes requires only a hash function for the indexed data type and an equality operator for searching. This example shows the operator class definition for the text data type:
1
CREATE OPERATOR CLASS text_ops
2
DEFAULT FOR TYPE text USING bloom AS
3
OPERATOR 1 =(text, text),
4
FUNCTION 1 hashtext(text);
Copied!

F.5.4. Limitations

  • Only operator classes for int4 and text are included with the module.
  • Only the = operator is supported for search. But it is possible to add support for arrays with union and intersection operations in the future.
  • bloom access method doesn't support UNIQUE indexes.
  • bloom access method doesn't support searching for NULL values.

F.5.5. Authors

Teodor Sigaev <[email protected]>, Postgres Professional, Moscow, Russia
Alexander Korotkov <[email protected]>, Postgres Professional, Moscow, Russia
Oleg Bartunov <[email protected]>, Postgres Professional, Moscow, Russia