F.7. bloom — 布隆过滤器索引访问方法#

F.7.1. 参数
F.7.2. 示例
F.7.3. 运算符类接口
F.7.4. 限制
F.7.5. 作者

bloom提供基于布隆过滤器的索引访问方法。

布隆过滤器是一种空间高效的数据结构，用于测试元素是否属于一个集合。对于索引访问方法，它可以通过签名快速排除不匹配的元组，其大小在创建索引时确定。

签名是索引属性的损失表示，因此容易报告误报；也就是说，它可能会报告元素在集合中，而实际上并不在。因此，必须始终使用堆条目中的实际属性值重新检查索引搜索结果。较大的签名会降低误报的几率，从而减少无用的堆访问，但当然也会使索引更大，从而减慢扫描速度。

当表具有许多属性且查询测试它们的任意组合时，此类索引最为有用。传统 btree 索引比布隆索引快，但它可能需要许多 btree 索引来支持所有可能的查询，而布隆索引只需要一个。但请注意，布隆索引仅支持相等查询，而 btree 索引还可以执行不等式和范围搜索。

F.7.1. 参数#

bloom索引在其WITH子句中接受以下参数

长度: 以位为单位的每个签名（索引项）的长度。它向上舍入到最接近的 16 倍数。默认值为 80 位，最大值为 4096。

col1 — col32: 为每个索引列生成的位数。每个参数的名称都指它控制的索引列的编号。默认值为 2 位，最大值为 4095。对于实际上未使用的索引列，将忽略其参数。

F.7.2. 示例#

这是一个创建布隆索引的示例

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，是布隆索引所用空间的八倍。

F.7.3. 操作符类接口#

布隆索引的操作符类仅需要一个哈希函数（用于索引的数据类型）和一个相等操作符（用于搜索）。此示例显示了text数据类型的操作符类定义

CREATE OPERATOR CLASS text_ops
DEFAULT FOR TYPE text USING bloom AS
    OPERATOR    1   =(text, text),
    FUNCTION    1   hashtext(text);

F.7.4. 限制#

此模块仅包含 int4 和 text 的操作符类。
搜索仅支持 = 操作符。但将来有可能通过并集和交集操作为数组添加支持。
bloom 访问方法不支持 UNIQUE 索引。
bloom 访问方法不支持搜索 NULL 值。

F.7.5. 作者#

Teodor Sigaev<[[email protected]](/cdn-cgi/l/email-protection#8efaebe1eae1fccefee1fdfae9fcebfdfefce1a0fcfb)>，Postgres Professional，俄罗斯莫斯科

Alexander Korotkov<[[email protected]](/cdn-cgi/l/email-protection#43226d282c312c37282c3503332c30372431263033312c6d3136)>，Postgres Professional，俄罗斯莫斯科

Oleg Bartunov<[[email protected]](/cdn-cgi/l/email-protection#1e717c7f6c6a6b7071685e6e716d6a796c7b6d6e6c71306c6b)>，Postgres Professional，俄罗斯莫斯科

F.7. bloom — 布隆过滤器索引访问方法# ​

F.7.1. 参数# ​

F.7.2. 示例# ​

F.7.3. 操作符类接口# ​

F.7.4. 限制# ​