bloom
bloom提供了一种基于布隆过滤器的索引访问方法。
布隆过滤器是一种空间高效的数据结构，它被用来测试一个元素是否为一个集合的成员。
在索引访问方法的情况下，它可以通过尺寸在索引创建时决定的签名来快速地排除不匹配的元组。
签名是被索引属性的一种有损表达，并且因此容易报告伪肯定，也就是说对于一个不在集合中的元素有可能报告该元素在集合中。因此索引搜索结果必须使用来自堆项的实际属性值进行再次检查。较大的签名可以降低伪肯定的几率并且减少无用的堆访问的次数，但是这显然会让索引更大且扫描起来更慢。
当表具有很多属性并且查询可能会测试其中任意组合时，这种类型的索引最有用。传统的btree 索引比布鲁姆索引更快，但是需要很多 btree 索引来支持所有可能的查询，而对于布鲁姆索引来说只需要一个即可。不过要注意 bloom 索引只支持等值查询，而 btree 索引还能执行不等和范围搜索。
1. 参数
bloom索引在其WITH子句中接受下列参数：
length每个签名（索引项）的长度位数，它会被圆整成为最近的16的倍数。默认是80位，最长是4096位。
col1 — col32从每一个索引列产生的位数。每个参数的名字表示它所控制的索引列的编号。默认是2位，最大是4095位。没有实际使用的索引列的参数 会被忽略。
2. 例子
这是一个创建bloom的例子：
test=## CREATE INDEX bloomidx ON tbloom USING bloom (i1,i2,i3)
test-## WITH (length=80, col1=2, col2=2, col3=4);
CREATE INDE
该索引是用长度为 80 位的签名所创建，其中属性 i1 和 i2 被映射为 2 位，属性 i3 被映射为 4 位。我们可以省略length、col1和col2说明，因为它们都有默认值。
这里是布隆索引定义和使用的更完整的例子，其中还与等效的 btree 做了对比。布隆索引比 btree 索引更小，并且效率更高。
test-## (random() * 1000000)::int as i1,
test-## (random() * 1000000)::int as i2,
test-## (random() * 1000000)::int as i3,
test-## (random() * 1000000)::int as i4,
test-## (random() * 1000000)::int as i5,
test-## (random() * 1000000)::int as i6
test-## FROM
test-## generate_series(1,10000000);
SELECT 10000000
在这个大表上的顺序扫描需要很长时间：
test=## EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451;
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------
Gather (cost=1000.00..127220.72 rows=250 width=24) (actual time=414.282..415.411 rows=0 loops=1)
Workers Planned: 2
Workers Launched: 2
-> Parallel Seq Scan on tbloom (cost=0.00..126195.72 rows=104 width=24) (actual time=410.361..410.361 rows=0 loop
s=3)
Filter: ((i2 = 898732) AND (i5 = 123451))
Rows Removed by Filter: 3333333
Planning Time: 0.176 ms
Execution Time: 415.484 ms
(8 rows)
即使定义了btree索引，结果将仍然是顺序扫描：
test=## CREATE INDEX btreeidx ON tbloom (i1, i2, i3, i4, i5, i6);
CREATE INDEX
test=## SELECT pg_size_pretty(pg_relation_size('btreeidx'));
pg_size_pretty
----------------
386 MB
(1 row)
test=## EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451;
QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------
Gather (cost=1000.00..127195.10 rows=1 width=24) (actual time=220.290..221.186 rows=0 loops=1)
Workers Planned: 2
Workers Launched: 2
-> Parallel Seq Scan on tbloom (cost=0.00..126195.00 rows=1 width=24) (actual time=216.318..216.319 rows=0 loops=
3)
Filter: ((i2 = 898732) AND (i5 = 123451))
Rows Removed by Filter: 3333333
Planning Time: 0.165 ms
Execution Time: 221.241 ms
(8 rows)
在处理这类搜索时，bloom 比 btree 更好：
test=## CREATE INDEX bloomidx ON tbloom USING bloom (i1, i2, i3, i4, i5, i6);
CREATE INDEX
test=## SELECT pg_size_pretty(pg_relation_size('bloomidx'));
pg_size_pretty
----------------
153 MB
(1 row)
现在，btree 搜索的主要问题是：当搜索条件不约束前几个索引列时，btree 的效率不好。
对于 btree 更好的策略是在每一列上创建一个独立的索引。那么规划器将选择这样的计划：
test=## CREATE INDEX btreeidx1 ON tbloom (i1);
CREATE INDEX
test=## CREATE INDEX btreeidx2 ON tbloom (i2);
CREATE INDEX
test=## CREATE INDEX btreeidx3 ON tbloom (i3);
CREATE INDEX
test=## CREATE INDEX btreeidx4 ON tbloom (i4);
CREATE INDEX
test=## CREATE INDEX btreeidx5 ON tbloom (i5);
CREATE INDEX
test=## CREATE INDEX btreeidx6 ON tbloom (i6);
CREATE INDEX
test=## EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451;
QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on tbloom (cost=9.28..13.29 rows=1 width=24) (actual time=0.659..0.664 rows=0 loops=1)
Recheck Cond: ((i5 = 123451) AND (i2 = 898732))
-> BitmapAnd (cost=9.28..9.28 rows=1 width=0) (actual time=0.657..0.660 rows=0 loops=1)
-> Bitmap Index Scan on btreeidx5 (cost=0.00..4.51 rows=10 width=0) (actual time=0.627..0.627 rows=5 loops=
1)
Index Cond: (i5 = 123451)
-> Bitmap Index Scan on btreeidx2 (cost=0.00..4.52 rows=11 width=0) (actual time=0.025..0.025 rows=10 loops
=1)
Index Cond: (i2 = 898732)
Planning Time: 0.416 ms
Execution Time: 3.074 ms
(9 rows)
尽管这个查询运行起来比在其中任一单个索引上都快，但是我们在索引尺寸上付出了代价。
每一个单列 btree 索引占用 2 MB，因此总的空间会超过 12 MB，这是bloom索引所使用的空间的 8 倍。
3 限制
• 在模块中只包括了用于int4以及text的操作符类。
• 搜索只支持=操作符。但是未来可以为合并和交集操作的数组增加支持。
• bloom访问方法不支持UNIQUE索引。
• bloom访问方法不支持对NULL值的搜索。