bloom
提供基于 布隆过滤器 的索引访问方法。
布隆过滤器是一种空间高效的数据结构,用于测试元素是否属于一个集合。对于索引访问方法,它可以通过签名快速排除不匹配的元组,其大小在创建索引时确定。
签名是索引属性的损失表示,因此容易报告误报;也就是说,它可能会报告元素在集合中,而实际上并不在。因此,必须始终使用堆条目中的实际属性值重新检查索引搜索结果。较大的签名会降低误报的几率,从而减少无用的堆访问,但当然也会使索引更大,从而减慢扫描速度。
当表具有许多属性且查询测试它们的任意组合时,此类索引最为有用。传统 btree 索引比布隆索引快,但它可能需要许多 btree 索引来支持所有可能的查询,而布隆索引只需要一个。但请注意,布隆索引仅支持相等查询,而 btree 索引还可以执行不等式和范围搜索。
bloom
索引在其 WITH
子句中接受以下参数
长度
以位为单位的每个签名(索引项)的长度。它向上舍入到最接近的 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
规范,因为它们具有默认值。
这是一个布隆索引定义和用法的更完整的示例,以及与等效 btree 索引的比较。布隆索引比 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)
在表上定义布隆索引在处理此类搜索时比 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,俄罗斯莫斯科
Alexander Korotkov <[email protected]>
,Postgres Professional,俄罗斯莫斯科
Oleg Bartunov <[email protected]>
,Postgres Professional,俄罗斯莫斯科