4.3 文件级统计与跳过策略
4.1 讲了 min/max 的区间判断,4.2 讲了布隆的成员判断。现实中一次查询不会只用一种:先用文件统计排除整文件,再用布隆排除块,最后才读数据页。每一级都能跳过一部分,但跳过的比例不能直接相加;顺序、成本与失效条件都要放进同一本账。
这一节把两级裁剪串成一条完整路径:100 个文件 → zone map 后剩 20 个 → 布隆再滤掉 8 个 → 余 12 个。最终跳过率是 88%,而不是 80% + 40%。
三级裁剪:分区、文件统计、块内统计
一次扫描能跳过的数据,通常分布在三个层级:
| 层级 | 依据 | 跳过单位 | 需要打开文件 |
|---|---|---|---|
| 分区裁剪 | 目录名/分区值 | 整个分区 | 否 |
| 文件统计 | 文件级 min/max、null 数、行数 | 整个文件 | 读元数据 |
| 块内统计 | row group/page 的 min/max、布隆 | 块或页 | 读 footer/索引 |
分区裁剪最便宜:它只看目录或清单,连文件都不用打开;文件统计次之:读一次元数据就能排除整文件;块内统计最贵:要读 footer、page index 或 Puffin,才能判断块内是否命中。
三层不是替代关系,而是漏斗关系。分区裁剪把候选集从「全表」缩到「若干分区」,文件统计把分区缩到「若干文件」,块内统计再把文件缩到「若干页」。每一层都在前一层的幸存者上工作,所以后一层的过滤率要乘以前一层的幸存比例,不能直接相加。
第一级:zone map 跳掉 80%
假设查询命中 100 个候选文件,文件级 min/max 能排除其中 80 个:
候选文件 = 100
zone map 跳过率 = 80%
zone map 后剩余 = 100 × (1 - 0.8) = 20 个
| 阶段 | 输入文件 | 跳过 | 剩余 | 跳过率 |
|---|---|---|---|---|
| 初始候选 | 100 | 0 | 100 | 0% |
| zone map 后 | 100 | 80 | 20 | 80% |
这 80% 的前提是文件统计与谓词区间不相交。文件按时间分区、按主键排序、或写入时聚簇,都会让文件级 min/max 互不重叠;随机写入的文件区间几乎一样,这一级就会退化。文件级统计的收益,首先取决于写入时有没有为裁剪做布局。
20 个幸存文件不代表都要读数据页。zone map 只能证明「文件里可能有值」,不能证明「值在哪一页」;要往下缩,需要块内统计或布隆。第一级裁剪结束的地方,正是第二级开始的地方。
第二级:布隆再滤掉 8 个
lab 的用例 35 接着这 20 个文件算:
zone map 后剩余 = 20 个文件
布隆再滤除 40%
滤掉 = 20 × 40% = 8 个
剩余 = 20 - 8 = 12 个
| 阶段 | 输入文件 | 滤除 | 剩余 | 本級滤除率 |
|---|---|---|---|---|
| zone map 后 | 20 | — | 20 | — |
| 布隆后 | 20 | 8 | 12 | 40% |
这里的 40% 是「有效滤除率」,不是布隆的误判率。4.2 的 1% 误判率描述的是「不存在的键被误判为存在」的概率;本用例描述的是「这批文件里有多少被布隆正确排除」。两者方向相反,不能混用:误判率越低,有效滤除率越高,但具体数值取决于这批文件里到底有多少真正的不存在键。
布隆只对「等值/成员」查询有效。如果谓词是 x > 95 这种范围条件,布隆帮不上忙,只能靠 min/max 或 page index。第二级用什么统计,由谓词形态决定;把布隆套在范围查询上,只会白读过滤器。
组合跳过率:为什么是 88%,不是 120%
lab 的用例 36 给出组合公式:
第一级跳过率 p1 = 80%
第二级跳过率 p2 = 40%
组合跳过率 = 1 - (1 - p1) × (1 - p2)
= 1 - 0.2 × 0.6
= 1 - 0.12
= 0.88,即 88%
| 阶段 | 跳过率 | 剩余比例 | 累计跳过率 |
|---|---|---|---|
| 仅 zone map | 80% | 20% | 80% |
| zone map + 布隆 | 40%(对幸存者) | 20% × 60% = 12% | 88% |
| 直接相加(错误) | — | — | 120%(不可能) |
两级跳过率相乘的是「剩余比例」,不是跳过率。第一级留下 20%,第二级在这 20% 里再留下 60%,最终留下 12%,跳过 88%。任何多级过滤都服从这个乘法结构:剩余比例连乘,跳过率是 1 减去连乘结果。
88% 不是终点,只是两级的结果。如果再加 page 级统计,第三级会在 12% 的幸存文件里继续过滤;每加一级,边际收益递减,但成本可能上升。裁剪的层数不是越多越好,要看下一级能多跳多少、要多花多少。
顺序为什么不能反:成本阶梯
两级裁剪的顺序通常固定为「便宜的在前」:
| 顺序 | 读取内容 | 单次成本 | 适用谓词 |
|---|---|---|---|
| 分区裁剪 | 目录/清单 | 极低 | 分区列 |
| 文件 min/max | 元数据/footer | 低 | 范围、等值 |
| 布隆 | 约 12KB/chunk | 中 | 等值、成员 |
| page index | 页统计 | 中 | 范围、等值 |
| 数据页 | 解压解码 | 高 | 任意 |
先做 min/max 再布隆,是因为 min/max 的统计通常已经随 footer 读入内存,判断几乎零成本;布隆要额外读过滤器、算 7 次哈希,成本更高。先做零成本的判断,能把后面的昂贵判断限制在更小的候选集上。
但「便宜在前」不是绝对规则。如果布隆的滤除率远高于 min/max,先布隆可能更省:假设 min/max 只跳 10%、布隆能跳 90%,先布隆能让 min/max 少判很多文件。正确的顺序由「成本 / 期望节省」决定:
先 A 后 B 的期望成本 = C_A × N + C_B × N × (1 - p_A)
先 B 后 A 的期望成本 = C_B × N + C_A × N × (1 - p_B)
两者比较,取更小者
| 场景 | 建议顺序 | 原因 |
|---|---|---|
| min/max 已在内存 | min/max → 布隆 | 第一步近乎免费 |
| 布隆选择性极高 | 布隆 → min/max | 先大幅缩小候选集 |
| 谓词是范围 | min/max → page index | 布隆不适用 |
| 谓词是等值 | 布隆 → page index | 布隆更直接 |
顺序错了不会错结果,只会多花钱。两级裁剪都是「只可能多读、不可能少读」的保守判断,顺序只影响成本,不影响正确性。这也是裁剪优化可以放心试错的原因。
总账:跳过率不等于扫描字节
跳过 88% 的文件,不等于扫描字节也减少 88%:
| 口径 | 计算 | 结果 |
|---|---|---|
| 文件数跳过率 | 12 / 100 剩余 | 88% |
| 扫描字节跳过率 | 取决于幸存文件大小 | 可能高于或低于 88% |
| 查询耗时下降 | 还受解压、CPU、网络影响 | 通常小于字节下降 |
文件大小不均匀时,按文件数算的跳过率会失真。如果被跳过的 88 个都是小文件,剩下的 12 个大文件仍占大部分字节,扫描量下降远小于 88%;反过来,跳过的是大文件,收益会被放大。评估裁剪效果,要用「跳过的字节 / 总字节」,而不是「跳过的文件数 / 总文件数」。
查询耗时还受其他阶段影响。少读 88% 的字节,不代表耗时也降 88%:解压、谓词计算、结果组装、网络传输都可能成为新瓶颈。裁剪解决的是 IO,不是全部;把它放进整条执行链看,才能判断收益是否真实。
失效条件与保守回退
两级裁剪都有失效的时候,识别失效比记住公式更重要:
| 失效条件 | 影响的层级 | 表现 |
|---|---|---|
| 数据未聚簇、统计区间重叠 | zone map | 跳过率趋近 0 |
| 统计缺失或截断 | zone map | 保守放行,多读 |
| 谓词套函数、无法反推 | 两级都失效 | 只能读完再过滤 |
| 高基数范围查询 | 布隆 | 布隆不适用,白读 |
| 统计与数据不同版本 | 文件级 | 可能错跳,必须靠快照保证 |
最后一行是唯一涉及正确性的风险。格式内的统计随文件一起写入,文件不可变,统计不会过期;但元数据仓库里的文件级统计可能滞后于外部写入。湖表用快照隔离保证「统计与数据同版本」,读取器只信当前快照的清单,不信可能过期的仓库统计。
统计缺失时必须保守。读取器遇到没有 min/max、没有布隆的块,只能当作「可能命中」;这不是实现偷懒,而是正确性的底线。跳过率可以降,结果不能错。
分区裁剪:漏斗的最上层
在文件统计之前,还有一层几乎零成本的裁剪:分区。分区值直接写在目录路径或清单字段里,查询规划阶段就能排除整个目录,连文件都不用打开。
| 维度 | 粗分区 | 细分区 |
|---|---|---|
| 裁剪精度 | 低,一个分区覆盖很多值 | 高,分区内值域窄 |
| 小文件风险 | 低,单分区文件少 | 高,分区多导致文件碎 |
| 元数据压力 | 小 | 大,清单与目录项膨胀 |
| 适用基数 | 低基数(天、地区) | 高基数(小时、用户) |
分区粒度是「裁剪精度」与「小文件」的折中。按天分区能跳掉大部分历史数据,但按用户 ID 分区会产生海量小目录;分得太细,文件数暴涨,列表与打开成本反过来吃掉裁剪收益。分区列应该是查询里稳定出现、基数可控的列,而不是越多越好。
隐藏分区把「分区」从物理布局变成元数据变换。Iceberg 这类表格式可以按 day(ts) 分区而不把列值写进目录名,查询仍然能裁剪,同时避免用户直接依赖目录结构。分区裁剪的本质是「用元数据排除数据」,目录只是最原始的实现形式。
条件滤除比例与误判概率
用例里的 40% 表示通过前一层后的 20 个候选中有 8 个被安全排除。Bloom 的假阳性率以真实不存在的候选为分母。若 20 个候选中 8 个不含目标、误判率 1%,平均排除约 7.92 个;真实存在的 12 个仍需读取。 Parquet Bloom
三个常见误解
误解一:两级裁剪的跳过率可以直接相加,80% + 40% = 120%。 真相:第二级只在第一级的幸存者上工作,组合跳过率是 1-(1-p1)(1-p2);用例 36 中 80% 与 40% 组合后是 88%,剩余 12%。
误解二:跳过 88% 的文件,扫描量也减少 88%。 真相:文件大小不均匀时,按文件数算的跳过率会失真;要看跳过的字节占总字节的比例,还要扣除解压与 CPU 成本。
误解三:裁剪级数越多越好,每级都应默认开启。 真相:每级都有读取与判断成本,边际收益递减;布隆对范围查询无效,page index 在命中页多时可能入不敷出。
一句话总结本节
文件级裁剪是一个漏斗:100 个候选文件先被 zone map 跳掉 80% 剩 20 个,再被布隆滤掉 8 个剩 12 个,组合跳过率是 1-(0.2×0.6)=88%,不是 80%+40%。顺序按「成本阶梯」排,min/max 通常在前、布隆在后;评估收益要看跳过的字节而不是文件数,统计缺失时必须保守放行。
本节 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。 - 断言:用例 35 验证「zone map 后剩 20 个文件,布隆再滤掉 8 个,余 12 个」;用例 36 验证「zone map 跳 80%、布隆再跳 40%,组合跳过率为 1-(0.2×0.6)=88%」。
- 整卷 runner 的预期汇总为
TOTAL: 116 passed, 0 failed。
对应本节判断链:先把候选集交给分区与文件统计 → 用 zone map 跳掉 80% 的文件 → 在 20 个幸存文件上用布隆再滤掉 8 个 → 用乘法结构算出 88% 的组合跳过率 → 按成本阶梯决定顺序 → 最后用「跳过的字节」而不是「跳过的文件数」评估真实收益。
继续阅读
探索更多技术文章
浏览归档,发现更多关于系统设计、工具链和工程实践的内容。