4.2 布隆过滤器与 Puffin 统计
4.1 的 zone map 对范围查询很有效,但遇到高基数等值查询就失灵:一列有 100 万个不同 ID,每个 page 的 min/max 都覆盖全表值域,id = 12345 这种查询一个 page 都跳不过。min/max 描述的是「值域」,不是「成员」,而等值查询关心的恰恰是成员。
布隆过滤器补的正是这一层:它用位数组回答「这个值一定不在」,用少量误判换取大幅跳过。本节先推 m/k 公式,再算误判账,最后把 Puffin 这类 sidecar 统计放进同一张图。
布隆过滤器:只回答「一定不在」
布隆过滤器是一个 m 位的位数组,加 k 个哈希函数。插入一个值,用 k 个哈希算出 k 个位置,全部置 1;查询一个值,同样算 k 个位置:
若 k 个位置中有任意一个为 0 → 该值一定不在集合中
若 k 个位置全为 1 → 该值可能在集合中(也可能不在)
这个不对称是布隆的全部价值:它不会漏掉真正存在的值(无假阴性),但会把一些不存在的值误判为存在(有假阳性)。用在数据裁剪上,假阳性只意味着「多读一块」,不会漏数据;正确性安全,代价是误判率。
| 查询结果 | 含义 | 裁剪动作 |
|---|---|---|
| 任一位为 0 | 一定不存在 | 可跳过该块 |
| 全为 1 | 可能存在 | 必须读该块 |
| 真正存在的值 | 全为 1 | 一定会读,不会漏 |
布隆不能删除元素。把某位置 0 会影响其他元素的判断,所以它只适合「写入后不再删除」的块级统计。数据更新只能重写块或重建过滤器,这与列式文件「块不可变」的假设一致。
m 与 k:公式与用例 33 的 95851 位
给定预期元素个数 n 和目标误判率 p,最优位数组长度 m 与哈希函数个数 k 由两个公式给出:
m = -n × ln(p) / (ln 2)^2
k = (m / n) × ln 2
lab 的用例 33 代入 n = 10,000、p = 0.01:
ln(0.01) = -4.60517
(ln 2)^2 = 0.480453
m = -10000 × (-4.60517) / 0.480453 ≈ 95850.5 位,向上取整 95851 位
k = (95851 / 10000) × 0.693147 ≈ 6.64,四舍五入 7 个
字节数 = 95851 / 8 ≈ 11981 字节 ≈ 12KB
| 参数 | 值 | 说明 |
|---|---|---|
| n | 10,000 | 预期插入的元素数 |
| p | 1% | 目标误判率 |
| m | 95,851 位 | 位数组长度,约 12KB |
| k | 7 | 哈希函数个数 |
| 每元素位数 | 9.59 位 | m / n |
m/n 约为 9.59 位/元素,这是 1% 误判率的代价。误判率每降一个数量级,位数大约要增加 4.8 位/元素;想把 1% 降到 0.1%,位数组要从 12KB 涨到约 18KB。误判率不是免费的,它直接用空间换。
k 也不是越大越好。k 增大,每次查询的哈希次数增加,CPU 成本上升;同时位数组被填得更满,误判率反而可能回升。最优 k 由 m/n 决定,公式给出的 7 就是平衡点。盲目加哈希函数,既慢又不一定更准。
误判率:1000 次查询约 10 次误判
误判率的定义是「不存在的元素被误判为存在」的概率。lab 的用例 34 把它折算成次数:
不存在键查询次数 = 1000
误判率 = 1%
期望误判次数 = 1000 × 1% = 10 次
| 查询次数 | 误判率 | 期望误判 | 实际影响 |
|---|---|---|---|
| 1000 | 1% | 10 | 10 次多读块 |
| 1000 | 0.1% | 1 | 1 次多读块 |
| 1000 | 10% | 100 | 100 次多读块 |
误判的代价是「多读」,不是「读错」。被误判的块会被读进来,再由上层谓词过滤掉,结果仍然正确。所以布隆的账要按「多读的块数 × 单块成本」算,而不是按「错误率」算。10 次误判在 1000 次查询里,可能只多读 10 个块;若每个块 1MiB,就是多读 10MiB。
误判率会随插入量漂移。公式里的 p 是按预期 n 算的;如果实际插入量超过 n,位数组被填得更满,真实误判率会高于设计值。写入时低估基数,是布隆失效的常见原因;要么按上限预留,要么在基数超阈值时重建。
布隆过滤器的格式与粒度
Parquet 规范的 split-block Bloom filter 由 256 bit 的块组成,每块含八个 32 bit word。用列值散列选块,再在块内按规范的位操作测试成员关系。它与通用位数组公式的 7 次独立哈希是两个模型。Parquet 在列块元数据记录相应 Bloom 的位置;ORC 等格式有自己的索引粒度。读端是否利用 Bloom 也取决于 reader 和谓词。缺失索引、NULL 谓词或类型不兼容时,应按适用规则保留候选。 Parquet Bloom 规范
布隆的成本:12KB 与 7 次哈希
一份 1% 误判率、1 万元素的布隆约 12KB。把它放进整张表:
单个 column chunk 的布隆 ≈ 12KB
10GiB 表、80 个 row group、10 列 → 800 个 column chunk
若每列都建布隆:800 × 12KB = 9600KB ≈ 9.6MB
| 成本项 | 量级 | 说明 |
|---|---|---|
| 存储 | 约 12KB / chunk | 只对高基数列建,实际远小于 9.6MB |
| 读取 | 每次查询读过滤器 | 点查只读命中的 chunk 过滤器 |
| CPU | 每键 k=7 次哈希 | 相对解压可忽略 |
| 构建 | 写入时逐值哈希 | 写入吞吐的小幅下降 |
9.6MB 是「全列都建」的上界,不是典型值。实际只给少数过滤列建布隆,统计开销通常远小于数据本身。布隆的性价比取决于「过滤器字节 / 被跳过块的字节」:跳过一块 1MiB 的数据,只花 12KB 统计,比例约 1:87,非常划算;若过滤器比数据还大,就不值得。
布隆的读取也有代价。点查时要先读过滤器、再算哈希、再判断;如果查询命中的块很多,过滤器的读取与哈希会成为额外开销。布隆适合「高选择性点查」,不适合「低选择性扫描」。
Puffin Theta sketch 与目录统计
Iceberg Puffin 单独保存带类型的 blob。规范定义的 Theta sketch 带字段 ID、快照 ID 和序号,可用于估计 NDV,典型消费者是查询优化器。Parquet 列块 Bloom 的成员判断走 Parquet 规范。Puffin 在 Iceberg 表元数据中定位,按需读取,无固定顺序要求先扫描 Parquet footer 再读取它。合并不同 sketch 前还要满足相同的值编码、字段和兼容性约束。 Puffin 规范
NDV 与 theta sketch:给优化器用的统计
布隆回答「某个值在不在」,但优化器还需要另一个问题:「这一列有多少个不同值」。这就是 NDV(Number of Distinct Values)。精确 NDV 要存全部值,代价太高;Puffin 里常用 theta sketch 这类可合并的近似结构。
| 统计 | 回答的问题 | 典型结构 | 服务对象 |
|---|---|---|---|
| min/max | 值域范围 | 两个值 | 裁剪、范围选择率 |
| 布隆 | 某值是否存在 | 位数组 | 等值裁剪 |
| NDV | 有多少不同值 | theta sketch / HLL | 优化器基数估计 |
NDV 的主要用途不是裁剪,而是代价估算。join 的顺序、聚合的哈希表大小、等值谓词的选择率,都依赖「这一列有多少不同值」。NDV 估错,优化器可能选错 join 顺序,代价比多读几个块大得多。
theta sketch 的优势是可合并。每个文件维护一个 sketch,扫描计划可以把多个文件的 sketch 合并,估计全局 NDV,而不必读全部数据。可合并性让「文件级统计」能升级成「表级统计」,这是 Puffin 相比普通 footer 统计的另一个价值。
近似统计要接受误差。theta sketch 的误差随精度参数变化,NDV 是一个估计值而不是精确值;优化器用它做决策,不拿它做正确性判断。统计可以错,结果不能错,这是所有近似统计的共同边界。
组合使用:三种统计的分工
把 min/max、布隆、NDV 放在一起,各自的位置很清楚:
| 查询形态 | 首选统计 | 原因 |
|---|---|---|
范围查询 x > 95 | min/max | 区间比较最便宜 |
等值点查 id = 12345 | 布隆 | min/max 对高基数无效 |
| join 顺序选择 | NDV | 需要基数而不是成员 |
| 分区裁剪 | 分区值 | 目录级,零文件打开 |
| 低基数枚举 | 字典 + min/max | 布隆空间不划算 |
没有一种统计能覆盖所有查询。范围查询靠 min/max,等值点查靠布隆,优化器决策靠 NDV;三者组合,才构成完整的统计层。统计的选型应该跟着查询形态走,而不是跟着格式默认走。
组合的顺序也有讲究。先做便宜的 min/max,再做布隆,最后才读数据;如果布隆的过滤率很高,也可以先布隆再 min/max,但前提是布隆的读取成本低于 min/max 的收益。顺序由成本与过滤率共同决定,4.3 会把这两级组合成一个跳过率总账。
三个常见误解
误解一:布隆过滤器有误判,所以查询结果可能出错。 真相:布隆只有假阳性、没有假阴性;误判只会让不该读的块被读进来,再由上层谓词过滤,结果仍然正确。
误解二:哈希函数越多,布隆越准。 真相:k 由 m/n 决定,用例 33 的最优值是 7;盲目增加哈希次数只会提高 CPU 成本,还可能因位数组过满而推高误判率。
误解三:NDV 统计是用来跳过数据块的。 真相:NDV 主要服务优化器的基数估计与 join 顺序,不是成员判断;跳过数据靠的是 min/max 与布隆。
一句话总结本节
通用 Bloom 公式用来理解空间与误判的取舍。Parquet 用自己的 split-block 布局排除一定不存在的列块。Puffin 的 Theta sketch 提供近似基数,消费路径和用途各自独立。
统计结构及消费者
表级基数估计、列块成员测试和页级范围分别影响计划选择或扫描。缺失统计时保留正确性。
flowchart LR
A[快照元数据] --> B[定位 Puffin Theta sketch]
B --> C[NDV 估计]
C --> D[优化器基数与计划]
E[Parquet 列块元数据] --> F[定位 split-block Bloom]
E --> G[定位 Page Index]
F --> H[用等值条件排除确定不存在的列块]
G --> I[用范围和偏移定位候选页]
H --> J[Reader 扫描候选]
I --> J
本节 lab
在 bd-engine-lab 中验证布隆参数与误判账:
- 源码:
src/format/Format.java与src/format/FormatSuite.java。 - 运行:
cd bd-engine-lab && mkdir -p out && javac -d out $(find src -name '*.java') && java -cp out lab.RunAll。 - 断言:用例 33 验证「1 万行、1% 误判率需要 95851 位、7 个哈希函数」;用例 34 验证「1000 次不存在键查询、1% 误判率,约 10 次误判」。
- 整卷 runner 的预期汇总为
TOTAL: 116 passed, 0 failed。
对应本节判断链:先确认 min/max 对高基数等值查询失效 → 用布隆的「一定不在」补位 → 由 n 与 p 推出 m=95851 位、k=7 → 把 1% 误判率折算成 1000 次查询约 10 次多读 → 对照 Parquet split-block Bloom → 以 Puffin Theta sketch 的 NDV 服务优化器。
继续阅读
探索更多技术文章
浏览归档,发现更多关于系统设计、工具链和工程实践的内容。