MIT Notes by Ron

中文

English

中文

English

Appearance

PostgreSQL 索引 — 10（Bloom 索引） ​

原文：https://habr.com/en/companies/postgrespro/articles/452968/ （作者 Egor Rogov，PostgresPro）

写在前面 ​

这是本系列的收官一篇，介绍另一种需要单独安装的扩展索引类型——Bloom 索引，它基于经典的布隆过滤器（Bloom filter）这一概率数据结构。它的定位很明确：为那些"字段特别多、每个字段选择性都不算太高、但查询经常同时对好几个字段做等值过滤"的宽表场景，提供一种比多列 B-tree 更紧凑的解决方案。

布隆过滤器基础 ​

布隆过滤器是一种用来快速判断"某个元素是否可能属于某个集合"的数据结构，核心特性是：它可能出现假阳性（错误地认为一个不在集合里的元素在集合里），但绝不会出现假阴性（如果过滤器说某元素不在集合里，那就一定不在）。

具体机制是：准备一个长度为 m 位的比特数组（这个数组就是所谓的"签名"），初始全部为 0；再准备 k 个相互独立的哈希函数，每个函数把输入元素映射到数组里的某一个比特位置。把一个元素"加入"集合时，用这 k 个哈希函数分别算出 k 个位置，把这些位置全部置为 1。之后要判断某个元素是否"可能"在集合里，同样用这 k 个哈希函数算出 k 个位置，检查这些位置是否全部为 1——只要有一个位置是 0，就可以百分百确定该元素不在集合里；如果 k 个位置全部是 1，则该元素可能在集合里（也可能是别的元素的置位恰好导致了这次"撞车"）。

在数据库里的应用方式 ​

Bloom 索引把这套机制用在了"一行数据"上：每一个索引行都对应一个独立的布隆过滤器，这一行里被索引的每个字段值都会被加入到这个专属过滤器里。查询时，对给定的过滤条件（比如若干个字段的等值条件）分别计算哈希位置，逐行核对该行的签名是否可能包含所有查询涉及的字段值。

和 BRIN 类似，Bloom 索引也被原文定性为"顺序扫描的加速器"：它并不精确给出匹配结果，命中的候选行仍需要回表核实，但大部分明显不匹配的行可以被快速跳过。

数学参数：如何选择签名长度和每字段位数 ​

Bloom 索引允许针对每个被索引字段单独配置"要置多少位"（也就是该字段专属的 k 值）。原文给出了几个用于估算合理参数的经验公式：

  • 推荐的签名总长度：m = -n * log₂(p) / ln 2（其中 n 是索引涉及的字段总数，p 是期望的假阳性概率）；
  • 每个字段建议置位的比特数：k = -log₂(p)；
  • 索引体积粗略估算：(m/8 + 6) * N 字节（m 单位是比特，6 字节是存储一个 TID 指针的开销，N 是行数）。

需要强调的是，原文特别提醒：这些公式只是用来估个大概初始值，实际效果高度依赖数据分布，真正调优还是要靠实测和调整。

参数配置示例 ​

以一张有 9 个待索引字段、3000 万行的宽表 flights_bi 为例，目标假阳性概率 p=0.01：

sql
create extension bloom;

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);

按公式推算出的建议配置是 96 位签名、每字段 7 个置位比特，理论估算索引体积约 515MB，实测结果为 526MB，两者相当吻合。

索引结构：完全"扁平" ​

Bloom 索引的物理结构非常简单——一个元页面后面跟着一系列普通的索引数据页，每个索引行只包含"一个签名 + 一个指向表行的 TID"，没有任何树形层级结构，是所有内置/扩展索引类型里结构最"平"的一种。

扫描方式 ​

正因为结构是扁平的、没有任何可供跳转的导航结构，Bloom 索引在被访问时总是被完整、顺序地从头读到尾——本质上就是对索引文件本身做一次顺序扫描,一边读一边根据签名核对哪些行可能匹配,一边构建位图,最后再用这个位图去表里批量取数据。原文提到，为了避免这种大范围顺序读把数据库共享缓冲区里的其他有用数据挤出去，Bloom 索引的读取会使用一个专门的小型环形缓冲区（buffer ring）——这和普通表的顺序扫描采用的缓存保护策略是同一套机制。

查询效果示例 ​

单字段过滤（只用乘客姓名）：

Bitmap Heap Scan on flights_bi
  Recheck Cond: (passenger_name = 'MIROSLAV SIDOROV'::text)
  Rows Removed by Index Recheck: 38562
  Bitmap Index Scan on flights_bi_bloom (actual time=1065.191..1065.191 rows=38564)

可以看到，单独用一个字段过滤时假阳性非常多——38564 个候选里,有 38562 个都是被 Recheck 剔除掉的误报,过滤效果很差。

而多字段联合过滤：

sql
select * from flights_bi
where passenger_name='MIROSLAV SIDOROV'
  and passenger_id='5864 006033';

同时用两个字段做等值条件后，假阳性数量骤降到只有 357 个——这正体现出 Bloom 索引的核心特性：它对单一字段的过滤效果并不出色，但同时施加的过滤条件越多，联合过滤效果越好，因为每多一个条件，就相当于多核对了一组比特位,进一步降低了误判概率。这也是它区别于普通多列 B-tree（对领头字段依赖强、非领头字段效果差）的地方——Bloom 索引对参与查询的所有字段"一视同仁"，不存在字段顺序的问题。

自定义操作符类 ​

要让某个数据类型接入 Bloom 索引，只需要提供一个等值操作符和一个哈希函数，比如：

sql
CREATE OPERATOR CLASS character_ops
DEFAULT FOR TYPE character USING bloom AS
  OPERATOR  1  =(character,character),
  FUNCTION  1  hashbpchar;

CREATE OPERATOR CLASS interval_ops
DEFAULT FOR TYPE interval USING bloom AS
  OPERATOR  1  =(interval,interval),
  FUNCTION  1  interval_hash;

这个接口要求非常简洁，几乎所有内置类型只要有对应的哈希函数就能直接支持。

和 BRIN、Hash 的对比 ​

原文专门比较了 Bloom 与另外两种同样"以牺牲精确度换取效率"或"专注等值查询"的索引：

对比 BRIN：BRIN 通常比 Bloom 更紧凑（体积能小上几十兆量级的差距），而且 BRIN 还能支持范围查询；但 BRIN 强依赖数据的物理排列顺序（相关性），一旦数据物理上比较散乱，BRIN 的效果会大打折扣。Bloom 则不依赖任何物理排列顺序，唯一的前提是该数据类型要有可用的哈希函数,适用范围更广、不挑数据分布。

对比 Hash 索引：Hash 索引能给出精确匹配结果（没有假阳性），但只能索引单个字段，而且体积可观——原文提到光是给一个字段建 Hash 索引就要占用大约 1GB 空间；相比之下 Bloom 用 526MB 就覆盖了全部 9 个字段的联合查询能力，虽然牺牲了精确性（需要回表核实），但空间效率和多字段覆盖能力上优势明显。

属性核对 ​

访问方法级：can_order: 不支持；can_unique: 不支持；can_multi_col: 支持（这本身就是 Bloom 存在的意义——服务多列联合等值查询）；can_exclude: 不支持。

索引级：只支持位图扫描（bitmap_scan），不支持普通索引扫描（index_scan，因为索引结构本身没有导航能力，无法逐条定向返回）。

其他限制：完全不能处理 NULL 值（原文原话是"甚至没法操作 NULL"）；不支持反向扫描；不支持距离排序。

使用限制与注意事项 ​

  • 只支持等值查询，不支持范围、模式匹配等其他操作符；
  • 优化器目前不会把多个 Bloom 条件之间的 OR 逻辑下推到索引层面利用（只能很好地支持 AND 组合的多条件查询）；
  • 前提是该字段类型必须有可用的哈希函数——比如 point 几何类型就因缺乏合适的哈希函数而无法直接使用；
  • 建索引时给出的每字段位数等参数在建成之后不能再动态调整，只能重建索引；
  • 不支持 NULL，涉及 NULL 的字段无法纳入索引考量。

适用场景总结 ​

原文的建议非常明确：Bloom 索引适合那种"字段数量很多、表本身很宽、并且典型查询会对其中若干个字段做等值过滤"的场景——这类场景下，为每种可能的字段组合分别建多列 B-tree 索引会导致索引数量爆炸、维护成本失控，而一个 Bloom 索引就能同时较好地服务多种字段组合的查询,是一种务实的空间换查全能力的折中方案。同时原文再次强调:公式给出的参数只是实验的起点,布隆过滤器终究是一种概率型结构,实际效果需要结合真实查询模式和数据分布反复验证调优。

小结 ​

Bloom 索引把经典的布隆过滤器概率结构直接映射到数据库索引场景：每行一个独立的比特签名，靠多个哈希函数的置位模式判断"可能匹配"，用完全扁平、无导航结构的物理组织换取极简的存储和更新逻辑。它最大的价值在于解决了"宽表多字段任意组合等值查询"这个 B-tree 和 Hash 都不擅长应对的痛点——不需要为每种字段组合分别建索引,一个 Bloom 索引就能覆盖多种查询模式的过滤加速,代价是需要回表核实假阳性、且完全不支持范围查询和 NULL。

至此，本系列十篇文章完整覆盖了 PostgreSQL 生态里从核心到扩展的主要索引类型：Hash（纯等值）、B-tree（全能型、唯一支持排序和唯一约束）、GiST（通用包含关系树,支持空间/区间/全文）、SP-GiST（通用空间分割树,适合前缀共享数据）、GIN（倒排索引,适合数组/JSON/全文）、RUM（GIN 的全文检索增强版）、BRIN（面向超大规模有序表的轻量摘要索引）、以及 Bloom（面向宽表多字段等值查询的概率索引）。选择索引类型的核心思路,始终是回到数据本身的分布特征和查询模式的匹配需求上做权衡。