bloom 提供了一种基于布隆过滤器的索引访问方法。
布隆过滤器是一种空间高效的数据结构，用于测试元素是否为集合的成员。索引访问方法中的布隆过滤器可以通过签名（其大小在创建索引时确定）快速排除不匹配的元组。
签名对索引属性的表示有损失，因此容易报告误报；也就是说，它可能会报告某个元素在集合中，而实际上它不在集合中。因此，索引搜索结果通常必须使用堆条目中的实际属性值重新检查。更大的签名可以减少误报的概率，从而减少无用堆访问的次数，但当然也使索引更大，因此扫描速度更慢。
当表有许多属性并且查询测试它们的各种组合时，这种类型的索引最有用。传统 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，是布隆索引使用空间的八倍。
布隆索引的操作符类仅需一个用于索引数据类型的哈希函数和一个用于搜索的相等操作符。此示例显示 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 <[email protected]>, Postgres Professional, Moscow, Russia
Alexander Korotkov <[email protected]>, Postgres Professional, Moscow, Russia
Oleg Bartunov <[email protected]>, Postgres Professional, Moscow, Russia