bloom 提供一种基于
布隆过滤器
的索引访问方法。
布隆过滤器是一种节省空间的数据结构，用于测试一个元素是否属于某个集合。对索引访问方法而言，它通过在创建索引时就确定大小的签名，快速排除不匹配的元组。
签名是被索引属性的有损表示，因此容易产生误报；也就是说，它可能报告某个元素在集合中，而实际上并不在。因此，索引搜索的结果必须始终使用堆条目中的实际属性值进行复查。更大的签名会降低误报的概率，从而减少无效的堆访问次数，但当然也会使索引变大、扫描变慢。
当一个表有很多属性，并且查询会测试这些属性的各种组合时，这种索引最为有用。传统 B 树索引比布隆索引更快，但要支持所有可能的查询组合，可能需要很多 B 树索引，而布隆索引只需一个。不过请注意，布隆索引只支持等值查询，而 B 树索引还可以执行不等值与范围搜索。
bloom 索引在其 WITH 子句中接受以下参数：
length
每个签名（索引条目）的长度（以位为单位）。它会被向上取整到 16 的倍数。默认值为 80 位，最大值为 4096。
col1 — col32
为每个索引列生成的位数。每个参数的名称对应它所控制的索引列的编号。默认值为 2 位，最大值为 4095。实际未使用的索引列的参数会被忽略。
下面是创建布隆索引的示例：
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 的说明，因为它们使用的就是默认值。
下面是一个更完整的布隆索引定义与使用示例，并与等效的 B 树索引进行对比。布隆索引比 B 树索引小得多，并且可能有更好的性能表现。
=# 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..213744.00 rows=250 width=24) (actual time=357.059..357.059 rows=0.00 loops=1)
Filter: ((i2 = 898732) AND (i5 = 123451))
Rows Removed by Filter: 10000000
Buffers: shared hit=63744
Planning Time: 0.346 ms
Execution Time: 357.076 ms
(6 rows)
即使定义了 B 树索引，结果仍然是顺序扫描：
=# CREATE INDEX btreeidx ON tbloom (i1, i2, i3, i4, i5, i6);
CREATE INDEX
=# SELECT pg_size_pretty(pg_relation_size('btreeidx'));
pg_size_pretty
----------------
386 MB
(1 row)
=# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451;
QUERY PLAN
------------------------------------------------------------------------------------------------------
Seq Scan on tbloom (cost=0.00..213744.00 rows=2 width=24) (actual time=351.016..351.017 rows=0.00 loops=1)
Filter: ((i2 = 898732) AND (i5 = 123451))
Rows Removed by Filter: 10000000
Buffers: shared hit=63744
Planning Time: 0.138 ms
Execution Time: 351.035 ms
(6 rows)
在表上定义布隆索引之后，处理这种类型的搜索就优于 B 树了：
=# 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
----------------
153 MB
(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=22.605..22.606 rows=0.00 loops=1)
Recheck Cond: ((i2 = 898732) AND (i5 = 123451))
Rows Removed by Index Recheck: 2300
Heap Blocks: exact=2256
Buffers: shared hit=21864
-> Bitmap Index Scan on bloomidx (cost=0.00..178436.00 rows=1 width=0) (actual time=20.005..20.005 rows=2300.00 loops=1)
Index Cond: ((i2 = 898732) AND (i5 = 123451))
Index Searches: 1
Buffers: shared hit=19608
Planning Time: 0.099 ms
Execution Time: 22.632 ms
(11 rows)
B 树搜索的主要问题在于：当搜索条件未约束前导索引列时，B 树的效率很低。对 B 树而言，更好的策略是为每一列分别创建一个索引。这样规划器会选择类似下面的计划：
=# 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=9.29..13.30 rows=1 width=24) (actual time=0.032..0.033 rows=0.00 loops=1)
Recheck Cond: ((i5 = 123451) AND (i2 = 898732))
Buffers: shared read=6
-> BitmapAnd (cost=9.29..9.29 rows=1 width=0) (actual time=0.047..0.047 rows=0.00 loops=1)
Buffers: shared hit=6
-> Bitmap Index Scan on btreeidx5 (cost=0.00..4.52 rows=11 width=0) (actual time=0.026..0.026 rows=7.00 loops=1)
Index Cond: (i5 = 123451)
Index Searches: 1
Buffers: shared hit=3
-> Bitmap Index Scan on btreeidx2 (cost=0.00..4.52 rows=11 width=0) (actual time=0.007..0.007 rows=8.00 loops=1)
Index Cond: (i2 = 898732)
Index Searches: 1
Buffers: shared hit=3
Planning Time: 0.264 ms
Execution Time: 0.047 ms
(15 rows)
虽然这条查询比使用任何单个索引都运行得快得多，但我们要付出索引空间的代价。每个单列 B 树索引占用 88.5 MB，因此所需总空间为 531 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 <teodor@postgrespro.ru>，Postgres Professional，俄罗斯莫斯科
Alexander Korotkov <a.korotkov@postgrespro.ru>，Postgres Professional，俄罗斯莫斯科
Oleg Bartunov <obartunov@postgrespro.ru>，Postgres Professional，俄罗斯莫斯科