F.5. bloom

bloom提供了基于Bloom filters的索引访问方法。

布隆过滤器是一种节省空间的数据结构，用于测试元素是否为集合的成员。在使用索引访问方法的情况下，它允许通过签名(其大小是在创建索引时确定的)快速排除不匹配的 Tuples。

签名是索引属性的有损表示，因此很容易报告误报。也就是说，可能会报告某个元素在集合中(如果没有)。因此，必须始终使用堆条目中的实际属性值来重新检查索引搜索结果。较大的签名减少了误报的几率，从而减少了无用堆访问的次数，但是当然也使索引变大，因此扫描速度变慢。

当表具有许多属性并且查询测试它们的任意组合时，这种类型的索引最有用。传统的 btree 索引比 Bloom 索引快，但是它可能需要许多 btree 索引来支持所有可能的查询，而其中一个查询只需要一个 Bloom 索引。但是请注意，bloom 索引仅支持相等查询，而 btree 索引也可以执行不相等和范围搜索。

F.5.1. Parameters

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

length
- 每个签名(索引条目)的长度(以位为单位)。将其舍入到最接近的16的倍数。默认值为80位，最大值为4096。
col1 — col32
- 每个索引列生成的位数。每个参数的名称指的是它控制的索引列的编号。默认值为2位，最大值为4095。未实际使用的索引列的参数将被忽略。

F.5.2. Examples

这是创建 bloom 索引的示例：

CREATE INDEX bloomidx ON tbloom USING bloom (i1,i2,i3)
       WITH (length=80, col1=2, col2=2, col3=4);

创建的索引的签名长度为 80 位，属性 i1 和 i2Map 为 2 位，属性 i3Map 为 4 位。我们可以省略length，col1和col2规范，因为它们具有默认值。

这是 Bloom 索引定义和用法的更完整示例，以及与等效 btree 索引的比较。 Bloom 索引比 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
=# 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)
=# CREATE index btreeidx ON tbloom (i1, i2, i3, i4, i5, i6);
CREATE INDEX
=# SELECT pg_size_pretty(pg_relation_size('btreeidx'));
 pg_size_pretty
----------------
 387 MB
(1 row)

对该大型表进行 Sequences 扫描需要很长时间：

=# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451;
                                                 QUERY PLAN
------------------------------------------------------------------------------------------------------------
 Seq Scan on tbloom  (cost=0.00..213694.08 rows=1 width=24) (actual time=1445.438..1445.438 rows=0 loops=1)
   Filter: ((i2 = 898732) AND (i5 = 123451))
   Rows Removed by Filter: 10000000
 Planning time: 0.177 ms
 Execution time: 1445.473 ms
(5 rows)

因此，计划者通常会尽可能选择索引扫描。使用 btree 索引，我们得到如下结果：

=# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451;
                                                           QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------
 Index Only Scan using btreeidx on tbloom  (cost=0.56..298311.96 rows=1 width=24) (actual time=445.709..445.709 rows=0 loops=1)
   Index Cond: ((i2 = 898732) AND (i5 = 123451))
   Heap Fetches: 0
 Planning time: 0.193 ms
 Execution time: 445.770 ms
(5 rows)

在处理这种类型的搜索时，Bloom 比 btree 更好：

=# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451;
                                                        QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on tbloom  (cost=178435.39..178439.41 rows=1 width=24) (actual time=76.698..76.698 rows=0 loops=1)
   Recheck Cond: ((i2 = 898732) AND (i5 = 123451))
   Rows Removed by Index Recheck: 2439
   Heap Blocks: exact=2408
   ->  Bitmap Index Scan on bloomidx  (cost=0.00..178435.39 rows=1 width=0) (actual time=72.455..72.455 rows=2439 loops=1)
         Index Cond: ((i2 = 898732) AND (i5 = 123451))
 Planning time: 0.475 ms
 Execution time: 76.778 ms
(8 rows)

请注意，误报的数量相对较多：已选择 2439 行要在堆中进行访问，但实际上没有与查询匹配的行。我们可以通过指定更大的签名长度来减少这种情况。在此示例中，使用length=200创建索引将误报数减少为 55；但它使索引大小增加了一倍(至 306 MB)，并最终使该查询的速度变慢(总计 125 毫秒)。

现在，btree 搜索的主要问题在于，当搜索条件不限制前导索引列时，btree 效率低下。 btree 的更好策略是在每列上创建一个单独的索引。然后计划者将选择以下内容：

=# 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.148..0.148 rows=0 loops=1)
   Recheck Cond: ((i5 = 123451) AND (i2 = 898732))
   ->  BitmapAnd  (cost=9.29..9.29 rows=1 width=0) (actual time=0.145..0.145 rows=0 loops=1)
         ->  Bitmap Index Scan on tbloom_i5_idx  (cost=0.00..4.52 rows=11 width=0) (actual time=0.089..0.089 rows=10 loops=1)
               Index Cond: (i5 = 123451)
         ->  Bitmap Index Scan on tbloom_i2_idx  (cost=0.00..4.52 rows=11 width=0) (actual time=0.048..0.048 rows=8 loops=1)
               Index Cond: (i2 = 898732)
 Planning time: 2.049 ms
 Execution time: 0.280 ms
(9 rows)

尽管此查询的运行速度比使用单个索引的查询快得多，但我们在索引大小上付出了很大的代价。每个单列 btree 索引占用 214 MB，因此所需的总空间超过 1.2GB，是 Bloom 索引使用的空间的 8 倍以上。

F.5.3. 操作员类别接口

Bloom 索引的运算符类仅需要用于索引数据类型的哈希函数和用于搜索的相等运算符。此示例显示了text数据类型的运算符类定义：

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

F.5.4. Limitations

该模块仅包含int4和text的运算符类。
仅支持=运算符进行搜索。但是将来可能会增加对具有联合和相交运算的数组的支持。
bloom访问方法不支持UNIQUE索引。
bloom访问方法不支持搜索NULL值。

F.5.5. Authors

Teodor Sigaev <teodor@postgrespro.ru>，Postgres Professional，俄罗斯莫斯科

Alexander Korotkov <a.korotkov@postgrespro.ru>，Postgres Professional，俄罗斯莫斯科

Oleg Bartunov <obartunov@postgrespro.ru>，Postgres Professional，俄罗斯莫斯科

Docs

Docs4dev

Title here