F.5. bloom

F.5.1. 参数
F.5.2. 例子
F.5.3. 操作符类接口
F.5.4. 限制
F.5.5. 作者

bloom提供了一种基于布鲁姆过滤器的索引访问方法。

布鲁姆过滤器是一种空间高效的数据结构,它被用来测试一个元素是否为一个集合的成员。在索引访问方法的情况下,它可以通过尺寸在索引创建时决定的签名来快速地排除不匹配的元组。

签名是被索引属性的一种有损表达,并且因此容易报告伪肯定,也就是说对于一个不在集合中的元素有可能报告该元素在集合中。因此索引搜索结果必须使用来自堆项的实际属性值进行再次检查。较大的签名可以降低伪肯定的几率并且减少无用的堆访问的次数,但是这显然会让索引更大且扫描起来更慢。

当表具有很多属性并且查询可能会测试其中任意组合时,这种类型的索引最有用。传统的 btree 索引比布鲁姆索引更快,但是需要很多 btree 索引来支持所有可能的查询,而对于布鲁姆索引来说只需要一个即可。不过要注意 bloom 索引只支持等值查询,而 btree 索引还能执行不等和范围搜索。

F.5.1. 参数

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

length

每个签名(索引项)的长度位数,它会被圆整成为最近的16的倍数。默认是80位,最长是4096位。

col1 — col32

从每一个索引列产生的位数。每个参数的名字表示它所控制的索引列的编号。默认是2位,最大是4095位。没有实际使用的索引列的参数会被忽略。

F.5.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 位。我们可以省略lengthcol1col2说明,因为它们都有默认值。

这里是布鲁姆索引定义和使用的更完整的例子,其中还与等效的 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)

在处理这类搜索时,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,这是bloom索引所使用的空间的 8 倍。

F.5.3. 操作符类接口

用于布鲁姆索引的操作符类只要一个用于被索引数据类型的哈希函数以及一个用于搜索的等值操作符。这个例子展示了用于text数据类型的操作符类定义:

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

F.5.4. 限制

  • 在模块中只包括了用于int4以及text的操作符类。

  • 搜索只支持=操作符。但是未来可以为带合并和交集操作的数组增加支持。

  • bloom访问方法不支持UNIQUE索引。

  • bloom访问方法不支持对NULL值的搜索。

F.5.5. 作者

Teodor Sigaev , Postgres Professional, Moscow, Russia

Alexander Korotkov , Postgres Professional, Moscow, Russia

Oleg Bartunov , Postgres Professional, Moscow, Russia