在之前的文章中，我们讨论了PostgreSQL 索引引擎和访问方法的接口，以及哈希索引 ， B树 ， GiST ， SP-GiST ， GIN ， RUM和BRIN 。 但是我们仍然需要查看Bloom索引。

布卢姆

一般概念

经典的布隆过滤器是一种数据结构，使我们能够快速检查集合中元素的成员资格。 筛选器非常紧凑，但是会产生误报：它会错误地将元素视为集合的成员（误报），但不允许将集合的元素视为不属于成员（误否定） 。

过滤器是 $$$m$ 最初用零填充的位（也称为签名 ）。 $$$k$ 选择了不同的哈希函数，这些哈希函数将集合的任何元素映射到 $$$k$ 签名的位。 要将元素添加到集合中，我们需要将签名中的每个这些位设置为一个。 因此，如果将与元素相对应的所有位都设置为1，则该元素可以是该集合的成员，但是如果至少一位等于0，则该元素肯定不在集合中。

对于DBMS，我们实际上有 $$$N$ 为每个索引行构建单独的过滤器。 通常，索引中包含几个字段，这些字段的值构成每一行的元素集。

通过选择签名的长度 $$$m$ ，我们可以在索引大小和误报的概率之间找到权衡。 Bloom索引的应用程序区域很大，需要使用每个字段上的过滤器来查询很大的“宽”表。 可以将这种访问方法与BRIN一样，视为顺序扫描的加速器：必须使用表重新检查索引找到的所有匹配项，但是有机会完全避免考虑大多数行。

结构形式

我们已经在GiST访问方法的上下文中讨论了签名树。 与这些树不同，Bloom索引是平面结构。 它由一个元页面和随后的带有索引行的常规页面组成。 每个索引行都包含一个签名和对表行（TID）的引用，如图所示。

创建和选择参数值

创建Bloom索引时，将指定签名的总大小（“长度”），以及为索引中包含的每个单独字段设置的位数（“ col1”-“ col32”）：

create index on ... using bloom(...) with (length=..., col1=..., col2=..., ...); 

指定位数的方法看起来很奇怪：这些数字必须是运算符类的参数，而不是索引。 问题是，尽管有关此操作的工作正在进行中，但目前无法对操作员类别进行参数设置。

不幸的是，在这方面没有进一步的进展。

我们如何选择合适的值？ 该理论指出，给定概率 $$$p$ 如果滤波器返回假阳性，则可以估计签名位的最佳数量为 $$$m = −n \ log_2 p / \ ln 2$ ，在哪里 $$$n$ 是索引中的字段数，要设置的位数是 $$$k =-\ log_2 p$ 。

签名以两个字节的整数数组的形式存储在索引中，因此 $$$m$ 可以安全地取整 $$$16$ 。

选择概率时 $$$p$ ，我们需要考虑到索引的大小，这大约等于 $$$（m / 8 + 6）N$ ，在哪里 $$$N$ 是表中的行数，并且 $$$6$ 是TID指针的大小（以字节为单位）。

需要注意的几点：

• 机率 $$$p$ 的误报涉及一个过滤器，因此，我们希望得到 $$$Np$ 表扫描期间的误报（当然，对于返回几行的查询）。 例如，对于具有一百万行和概率0.01的表，平均而言，在查询计划中，我们可以预期“通过索引重新检查删除的行：10000”。
• 布隆过滤器是一种概率结构。 仅当平均许多值时才讲特定数字是有意义的，而在每种特定情况下，我们都能得到我们能想到的。
• 以上估计是基于理想化的数学模型和一些假设。 在实践中，结果可能会更糟。 因此，不要高估公式：它们只是为将来的实验选择初始值的一种方法。
• 对于每个字段，访问方法使我们能够选择要设置的位数。 有一个合理的假设，即最佳数量实际上取决于列中值的分布。 要深入了解，您可以阅读本文 （欢迎参考其他研究）。 但是请先重读上一项。

更新中

当在表中插入新行时，将创建签名：对于所有索引字段的值，其所有对应位都设置为1。 从理论上讲，我们必须具有k个不同的哈希函数，而在实践中，伪随机数生成器就足够了，每次使用唯一的哈希函数来选择其种子。

常规的Bloom过滤器不支持元素的删除，但是Bloom索引不是必需的：删除表行时，整个签名以及索引行都将被删除。

与往常一样，更新包括删除过时的行版本和插入新的行版本（签名是从头开始计算的）。

正在扫描

由于Bloom过滤器只能做的事情是检查集合中元素的成员资格，因此Bloom索引支持的唯一操作是相等检查（例如在哈希索引中）。

正如我们已经提到的，Bloom索引是平坦的，因此在索引访问过程中，始终会连续且完整地读取它。 在阅读过程中，将生成一个位图，然后将其用于访问表。

在常规索引访问中，假定几乎不必读取索引行，此外，很快又可能需要使用它们，因此将它们存储在缓冲区高速缓存中。 但是，读取Bloom索引实际上是顺序扫描。 为了防止将有用的信息从缓存中逐出，请通过一个小的缓冲环进行读取，这与顺序扫描表的方式完全相同。

我们应该考虑到Bloom指数的大小越大，对计划者的吸引力就越小。 这种依赖性是线性的，与树状索引不同。

例子

桌子

让我们以上一篇文章中的 “ flights_bi”大表为例看一下Bloom索引。 提醒您，此表的大小为4 GB，大约有3000万行。 该表的定义：

 demo=# \d flights_bi 

  Table "bookings.flights_bi" Column | Type | Collation | Nullable | Default --------------------+--------------------------+-----------+----------+--------- airport_code | character(3) | | | airport_coord | point | | | airport_utc_offset | interval | | | flight_no | character(6) | | | flight_type | text | | | scheduled_time | timestamp with time zone | | | actual_time | timestamp with time zone | | | aircraft_code | character(3) | | | seat_no | character varying(4) | | | fare_conditions | character varying(10) | | | passenger_id | character varying(20) | | | passenger_name | text | | | 

让我们首先创建扩展：尽管Bloom索引从9.6版开始包含在标准交付中，但默认情况下不可用。

 demo=# create extension bloom; 

上一次，我们可以使用BRIN为三个字段建立索引（“ scheduled_time”，“ actual_time”，“ airport_utc_offset”）。 由于Bloom索引不依赖于数据的物理顺序，因此让我们尝试在索引中包括表的几乎所有字段。 但是，让我们排除时间字段（“ scheduled_time”和“ actual_time”）：该方法仅支持比较是否相等，但是对于任何人来说，查询精确的时间几乎都没有意义（但是，我们可以在表达式上构建索引，四舍五入时间到一天，但我们不会这样做）。 我们还必须排除机场的地理坐标（“ airport_coord”）：展望未来，不支持“点”类型。

要选择参数值，让我们将误报的概率设置为0.01（请注意实际上我们会得到更多）。 上面的公式 $$$n = 9$ 和 $$$N = 30 \，000 \，$ 00$ 给出96位的签名大小，并建议每个元素设置7位。 索引的估计大小为515 MB（大约是表的八分之一）。

（在最小签名大小为16位的情况下，公式保证索引大小是原来的两倍小，但仅允许依赖于0.5的概率，这是非常差的。）

操作员类别

因此，让我们尝试创建索引。

 demo=# create index flights_bi_bloom on flights_bi using bloom(airport_code, airport_utc_offset, flight_no, flight_type, aircraft_code, seat_no, fare_conditions, passenger_id, passenger_name) with (length=96, col1=7, col2=7, col3=7, col4=7, col5=7, col6=7, col7=7, col8=7, col9=7); 

 ERROR: data type character has no default operator class for access method "bloom" HINT: You must specify an operator class for the index or define a default operator class for the data type. 

不幸的是，该扩展只为我们提供了两个运算符类：

 demo=# select opcname, opcintype::regtype from pg_opclass where opcmethod = (select oid from pg_am where amname = 'bloom') order by opcintype::regtype::text; 

  opcname | opcintype ----------+----------- int4_ops | integer text_ops | text (2 rows) 

但是幸运的是，为其他数据类型创建类似的类也很容易。 Bloom访问方法的运算符类必须仅包含一个运算符-等式-和仅包含一个辅助函数-哈希。 查找任意类型所需的运算符和函数的最简单方法是在系统目录中查找“哈希”方法的运算符类：

 demo=# select distinct opc.opcintype::regtype::text, amop.amopopr::regoperator, ampr.amproc from pg_am am, pg_opclass opc, pg_amop amop, pg_amproc ampr where am.amname = 'hash' and opc.opcmethod = am.oid and amop.amopfamily = opc.opcfamily and amop.amoplefttype = opc.opcintype and amop.amoprighttype = opc.opcintype and ampr.amprocfamily = opc.opcfamily and ampr.amproclefttype = opc.opcintype order by opc.opcintype::regtype::text; 

  opcintype | amopopr | amproc -----------+----------------------+-------------- abstime | =(abstime,abstime) | hashint4 aclitem | =(aclitem,aclitem) | hash_aclitem anyarray | =(anyarray,anyarray) | hash_array anyenum | =(anyenum,anyenum) | hashenum anyrange | =(anyrange,anyrange) | hash_range ... 

我们将使用此信息创建两个缺少的类：

 demo=# CREATE OPERATOR CLASS character_ops DEFAULT FOR TYPE character USING bloom AS OPERATOR 1 =(character,character), FUNCTION 1 hashbpchar; demo=# CREATE OPERATOR CLASS interval_ops DEFAULT FOR TYPE interval USING bloom AS OPERATOR 1 =(interval,interval), FUNCTION 1 interval_hash; 

没有为点（“点”类型）定义哈希函数，因此，我们无法在此类字段上构建Bloom索引（就像我们无法在此类字段上执行哈希联接一样）。

再试一次：

 demo=# create index flights_bi_bloom on flights_bi using bloom(airport_code, airport_utc_offset, flight_no, flight_type, aircraft_code, seat_no, fare_conditions, passenger_id, passenger_name) with (length=96, col1=7, col2=7, col3=7, col4=7, col5=7, col6=7, col7=7, col8=7, col9=7); 

 CREATE INDEX 

索引的大小为526 MB，比预期的要大一些。 这是因为该公式未考虑页面开销。

 demo=# select pg_size_pretty(pg_total_relation_size('flights_bi_bloom')); 

  pg_size_pretty ---------------- 526 MB (1 row) 

查询

现在，我们可以使用各种条件执行搜索，索引将支持它。

如前所述，布隆过滤器是一种概率结构，因此，效率在很大程度上取决于每种特定情况。 例如，让我们看一下与两名乘客Miroslav Sidorov相关的行：

 demo=# explain(costs off,analyze) select * from flights_bi where passenger_name='MIROSLAV SIDOROV'; 

  QUERY PLAN -------------------------------------------------------------------------------------------------- Bitmap Heap Scan on flights_bi (actual time=2639.010..3010.692 rows=2 loops=1) Recheck Cond: (passenger_name = 'MIROSLAV SIDOROV'::text) Rows Removed by Index Recheck: 38562 Heap Blocks: exact=21726 -> Bitmap Index Scan on flights_bi_bloom (actual time=1065.191..1065.191 rows=38564 loops=1) Index Cond: (passenger_name = 'MIROSLAV SIDOROV'::text) Planning time: 0.109 ms Execution time: 3010.736 ms 

和Marfa Soloveva：

 demo=# explain(costs off,analyze) select * from flights_bi where passenger_name='MARFA SOLOVEVA'; 

  QUERY PLAN --------------------------------------------------------------------------------------------------- Bitmap Heap Scan on flights_bi (actual time=9980.884..10142.684 rows=2 loops=1) Recheck Cond: (passenger_name = 'MARFA SOLOVEVA'::text) Rows Removed by Index Recheck: 3950168 Heap Blocks: exact=45757 lossy=67332 -> Bitmap Index Scan on flights_bi_bloom (actual time=1037.588..1037.588 rows=212972 loops=1) Index Cond: (passenger_name = 'MARFA SOLOVEVA'::text) Planning time: 0.157 ms Execution time: 10142.730 ms 

在一种情况下，过滤器仅允许4万个误报，而在另一个过滤器中最多允许400万个误报（“通过索引重新检查删除行”）。 查询的执行时间相应地有所不同。

以下是通过乘客ID而不是姓名搜索相同行的结果。 米罗斯拉夫：

 demo=# explain(costs off,analyze) demo-# select * from flights_bi where passenger_id='5864 006033'; 

  QUERY PLAN ------------------------------------------------------------------------------------------------- Bitmap Heap Scan on flights_bi (actual time=13747.305..16907.387 rows=2 loops=1) Recheck Cond: ((passenger_id)::text = '5864 006033'::text) Rows Removed by Index Recheck: 9620258 Heap Blocks: exact=50510 lossy=165722 -> Bitmap Index Scan on flights_bi_bloom (actual time=937.202..937.202 rows=426474 loops=1) Index Cond: ((passenger_id)::text = '5864 006033'::text) Planning time: 0.110 ms Execution time: 16907.423 ms 

和玛法：

 demo=# explain(costs off,analyze) select * from flights_bi where passenger_id='2461 559238'; 

  QUERY PLAN -------------------------------------------------------------------------------------------------- Bitmap Heap Scan on flights_bi (actual time=3881.615..3934.481 rows=2 loops=1) Recheck Cond: ((passenger_id)::text = '2461 559238'::text) Rows Removed by Index Recheck: 30669 Heap Blocks: exact=27513 -> Bitmap Index Scan on flights_bi_bloom (actual time=1084.391..1084.391 rows=30671 loops=1) Index Cond: ((passenger_id)::text = '2461 559238'::text) Planning time: 0.120 ms Execution time: 3934.517 ms 

效率再次大不相同，这次Marfa更加幸运。

请注意，由于误报的可能性，同时进行两个字段的搜索将更加高效 $$$p$ 变成 $$$p ^ 2$ ：

 demo=# explain(costs off,analyze) select * from flights_bi where passenger_name='MIROSLAV SIDOROV' and passenger_id='5864 006033'; 

  QUERY PLAN -------------------------------------------------------------------------------------------------------------------- Bitmap Heap Scan on flights_bi (actual time=872.593..877.915 rows=2 loops=1) Recheck Cond: (((passenger_id)::text = '5864 006033'::text) AND (passenger_name = 'MIROSLAV SIDOROV'::text)) Rows Removed by Index Recheck: 357 Heap Blocks: exact=356 -> Bitmap Index Scan on flights_bi_bloom (actual time=832.041..832.041 rows=359 loops=1) Index Cond: (((passenger_id)::text = '5864 006033'::text) AND (passenger_name = 'MIROSLAV SIDOROV'::text)) Planning time: 0.524 ms Execution time: 877.967 ms 

但是，根本不支持使用布尔“或”进行搜索。 这是计划者的限制，而不是访问方法的限制。 当然，仍然可以选择读取索引两次，构建两个位图并连接它们，但这对于选择该计划而言很可能太昂贵了。

与BRIN和哈希的比较

Bloom和BRIN索引的应用领域明显相交。 这些是大表，希望确保通过不同的字段进行搜索，但牺牲了搜索精度以降低紧凑性。

BRIN索引更紧凑（例如，在我们的示例中，最大可达几十兆字节），并且可以支持按范围进行搜索，但是与文件中数据的物理排序有很大的限制。 布隆索引更大（数百兆字节），但没有限制，只有合适的哈希函数可用。

像Bloom索引一样，哈希索引支持唯一性检查。 散列索引确保了Bloom不能达到的搜索精度，但是索引的大小要大得多（在我们的示例中，一个字段只有一个千兆字节，并且不能在多个字段上创建散列索引）。

物产

像往常一样，让我们​​看一下Bloom的属性（ 已经提供了查询）。

以下是访问方法的属性：

  amname | name | pg_indexam_has_property --------+---------------+------------------------- bloom | can_order | f bloom | can_unique | f bloom | can_multi_col | t bloom | can_exclude | f 

显然，访问方法使我们能够在多个列上建立索引。 在一个列上创建Bloom索引几乎没有任何意义。

以下索引层属性可用：

  name | pg_index_has_property ---------------+----------------------- clusterable | f index_scan | f bitmap_scan | t backward_scan | f 

唯一可用的扫描技术是位图扫描。 由于索引始终被完全扫描，因此实现常规索引访问以TID逐行返回TID毫无意义。

  name | pg_index_column_has_property --------------------+------------------------------ asc | f desc | f nulls_first | f nulls_last | f orderable | f distance_orderable | f returnable | f search_array | f search_nulls | f 

这里只有破折号； 该方法甚至不能操作NULL。

最后：

当出现新的感兴趣的索引类型时，这一系列文章在将来会继续是不可能的，但是现在该停下来了。

我要感谢Postgres Professional的同事（他们中的一些人是讨论的许多访问方法的作者）阅读草稿并提供意见的过程。 我当然感谢您的耐心和宝贵的意见。 您的关注促使我达到了这一点。 谢谢你