《大规模分布式计算深入解析》4.1 min/max 与 zone map

zone map 用 min/max 回答「这块数据一定不命中」:page 统计 [10,90] 时查询 x>95 可直接跳过,100 个分区间文件查询 x>9000 能跳 90 个。但统计区间重叠时一个都跳不过,本节算清粒度、重叠与成本三笔账。

4.1 min/max 与 zone map

3.1 到 3.3 讲的是数据怎么摆、怎么编码。从这一节开始,问题变成「读之前能不能先排除一部分数据」。列式格式之所以快,不只因为列投影,更因为它在每个块上留了统计信息,让读取器有机会在触碰数据页之前就说「这块不用读」。

zone map 是最便宜的一种裁剪:它只记录每块数据的 min/max,用一次区间比较就能判断是否可能命中。便宜的另一面是容易失效:统计区间一旦重叠,跳过率会从 90% 掉到 0。这一节把这两种极端都算清楚。

zone map 是什么:用区间回答「不可能」

zone map 为每块数据维护一个值域区间 [min, max]。给定谓词,判断规则只有一条:

若块的整个区间都落在谓词区间之外
(如 x > L 时 max ≤ L,x < U 时 min ≥ U)→ 该块一定不命中,可跳过
否则 → 可能命中,必须读

这条规则只做「否定判断」:它能证明「不存在」,但不能证明「存在」。所以 zone map 不会漏数据,只会多读数据;跳过是安全的,不跳过是保守的。正确性不依赖统计精度,性能才依赖。

谓词判断方式能否跳过
x = 5050 是否落在 [min, max] 外能,区间外即跳过
x > 95max 是否不大于 95能,max ≤ 95 即跳过
x < 5min 是否不小于 5能,min ≥ 5 即跳过
x BETWEEN 10 AND 20区间是否完全不相交能,不相交即跳过
x IS NULL看 null_count,不看 min/max能,null_count=0 即跳过
f(x) > 95无法反推 x 的区间不能,只能读完再算

最后一行是常见坑:谓词一旦套了函数,zone map 就失效。date_trunc(day, ts) = '...'、CAST(x AS STRING) LIKE '...' 都无法用原始列的 min/max 判断,除非优化器能改写谓词。裁剪的前提是谓词能直接比较列值。

三种粒度:文件、row group/stripe、page

zone map 可以挂在不同层级,粒度越细,跳过越准,元数据越多:

粒度统计位置跳过单位典型来源
文件元数据仓库/清单整个文件Hive metastore、Iceberg manifest
row group / stripeParquet footer、ORC file footer一个 row group / stripe列式格式一级块
page / row indexParquet page index、ORC row index一个 page / 一段行列式格式二级块

文件级统计最便宜,也最粗。它只需要读元数据,不用打开文件;但一个文件可能包含几千万行,区间很宽,很容易重叠。page 级统计最准,也最贵:Parquet 的 page index 要额外读,ORC 的 row index 存在 stripe 内部,读取器必须先定位才能用。

三层不是互斥的,而是逐层收窄:先用文件统计排除整文件,再用 row group 统计排除整块,最后用 page 统计排除整页。每往下一层,能排除的块更少,但读的字节也更少。裁剪的收益来自「最早排除」,成本来自「读统计」,两层要一起算。

最小例子:page 统计 [10, 90],查询 x > 95

lab 的用例 30 是最小可验证场景:

page 统计:min = 10,max = 90
谓词:x > 95
判断:max 90 < 95 → 该 page 一定不命中 → 跳过
量值含义
page min10页内最小值
page max90页内最大值
谓词下界95只关心大于 95 的值
判断90 < 95区间不相交
结果跳过不读该页

这个例子说明 zone map 的收益可以精确到页。若没有 page index,读取器只能读完整个 column chunk 再过滤;有了页统计,它可以只解压命中的页。3.1 说的「page 从压缩单位变成裁剪单位」,靠的就是这类统计。

文件级账本:100 个文件跳 90 个

把粒度放大到文件,账本更直观。lab 的用例 31 构造了 100 个文件,第 i 个文件的统计区间是 [i × 100, i × 100 + 99],查询 x > 9000:

文件 0:  [0, 99]        max 99    < 9000 → 跳过
文件 1:  [100, 199]     max 199   < 9000 → 跳过
……
文件 89: [8900, 8999]   max 8999  < 9000 → 跳过
文件 90: [9000, 9099]   max 9099  > 9000 → 必须读
……
文件 99: [9900, 9999]   max 9999  > 9000 → 必须读
区间文件数判断结果
max ≤ 900090区间完全在谓词下界之下跳过
max ≥ 900010可能有值命中读取
合计100—跳过 90 个

跳过率 90% 的前提是「文件按值域有序分布」:第 i 个文件只覆盖 [i×100, i×100+99],区间互不重叠。这对应现实中的分区表、按主键排序写入的表、按时间聚簇的表。没有这个前提,zone map 的收益会立刻塌掉。

统计重叠:100 个文件一个都跳不过

lab 的用例 32 把同样的 100 个文件改成「每个文件的统计区间都是 [0, 5000]」,查询 x > 4000:

每个文件:min = 0,max = 5000
谓词:x > 4000
判断:min 0 不 > 4000,max 5000 不 < 4000 → 区间相交 → 必须读
结果:100 个文件全部读取,跳过 0 个
量用例 31用例 32
文件数100100
每文件区间[i×100, i×100+99][0, 5000]
查询x > 9000x > 4000
跳过文件数900
跳过率90%0%

注意用例 32 的「重叠比例」其实很小:查询只要 x > 4000,而文件区间是 [0, 5000],看起来只有最后 1000 的区间相关。但 zone map 的判断是「只要区间有交集就必须读」,哪怕只有一个值落在谓词范围内,整块也不能跳过。这就是统计重叠的杀伤力:重叠比例不等于跳过率,交集存在就是全读。

这也解释了为什么「数据没排序」会让裁剪失效。随机写入的文件,每个文件的 min/max 都会被拉宽到接近全表值域;100 个文件的区间几乎一样,zone map 只能全部放行。排序、聚簇、分区不是存储优化,而是裁剪的前提。

统计从哪里来,什么时候不可信

zone map 的统计通常来自三个地方:

来源记录内容可信度风险
写入时生成块内 min/max、null 数写入器实现差异,可能截断
元数据仓库文件级统计、分区值统计过期、外部写入未更新
查询时读取page index、row index老文件可能没有索引

统计缺失时只能保守处理。老版本文件、复杂类型、未开启统计的写入路径,都可能让 min/max 为空;读取器遇到空统计必须当作「可能命中」,否则会漏数据。正确性永远优先于跳过率。

统计截断也会让判断变保守。字符串的 min/max 通常只保留前若干字节,超长前缀相同、后缀不同的值会被归到同一区间;这不会导致漏读,但会让本可跳过的块被放行。截断是空间换保守,不是错误。

null 是另一条独立通道。min/max 通常忽略 null,所以 x > 5 的裁剪不受 null 影响;但 x IS NULL 必须看 null_count,不能靠 min/max。写谓词下推时,要把 null 语义单独处理,否则会把「全为 null 的块」错判成可跳过或不可跳过。

让 zone map 有效的三个条件

把前面的账合起来,zone map 要真正省 IO,至少满足三个条件:

条件说明失效后果
数据聚簇过滤列在块间有序或分区区间重叠,跳过率趋近 0
粒度足够细page/row index 覆盖到查询关心的范围只能跳大块,误判成本高
谓词可比较直接对列做范围/等值比较函数包裹后无法反推区间

三个条件缺一不可。只做排序但统计粒度粗,能跳文件却跳不了页;只做细粒度索引但数据乱序,每页区间都重叠,索引白建;谓词被函数包住,前两个条件都满足也用不上。

这也是查询优化器要做谓词改写的原因:把 year(ts) = 2026 改写成 ts >= '2026-01-01' AND ts < '2027-01-01',才能让 zone map 用上 ts 的 min/max。改写不是语法糖,而是把谓词翻译成统计能理解的形式。

成本与收益:便宜不等于免费

zone map 的成本主要是读统计与比较,收益是少读数据页:

操作成本收益
读文件级统计一次元数据读可能排除整文件
读 footer 统计打开文件时一次排除 row group
读 page index额外一次读排除 page
区间比较每条统计几次比较跳过整块

统计的读放大要算进账本。page index 本身也占字节,若查询命中的页很多,读索引的开销可能超过省下的解压;反过来,点查只命中一两页时,索引的收益远大于成本。是否启用页级裁剪,应该由「命中页比例」决定,而不是默认全开。

zone map 不会带来正确性风险,只会带来性能波动。统计准确时它安全地跳过;统计缺失或截断时它保守放行。这类「只可能多读、不可能少读」的优化,适合默认开启;真正需要谨慎的是布隆过滤器这类有误判率的结构,下一节展开。

多列谓词:逐列独立判断

真实查询很少只有一个条件。zone map 对多列谓词的处理是「逐列独立判断,再按逻辑组合」:

谓词形态跳过条件说明
a > 10 AND b < 5任一列区间不相交即可跳过AND 更严,裁剪更容易生效
a > 10 OR b < 5两列区间都不相交才可跳过OR 更松,裁剪更难生效
a > 10 AND a < 20合并成区间 [10, 20] 再比较同列条件可先做区间合并

AND 是裁剪的朋友,OR 是裁剪的敌人。每个 AND 条件都多一次排除机会,只要有一列能证明不命中,整块就可以跳过;OR 要求所有分支都失败才放行,任意一列有交集就得读。这也是优化器愿意把谓词拆分、把 OR 改写成 UNION 的原因:拆分后每个分支都能独立裁剪。

多列统计不能替代列间相关性。a 和 b 各自的 min/max 都覆盖查询范围,不代表它们的组合覆盖;反过来,组合上不存在的值,单列统计也发现不了。zone map 只理解单列值域,不理解列与列的关系;要利用相关性,需要多维聚簇或更复杂的统计。

三个常见误解

误解一:有 min/max 统计就一定能跳过不相关的数据。 真相:只有统计区间与谓词区间完全不相交才能跳过;用例 32 中 100 个文件区间都是 [0,5000],查询 x>4000 一个都跳不过。

误解二:区间重叠比例小,跳过率就高。 真相:zone map 是布尔判断,只要交集存在就必须读;重叠 20% 和重叠 100% 在「能否跳过」上没有区别。

误解三:zone map 统计越细越好, page 级索引应无条件开启。 真相:page index 要额外读,命中页多时索引开销可能超过收益;粒度选择要看查询的命中页比例。

一句话总结本节

zone map 用 min/max 做「一定不命中」的否定判断:page 统计 [10,90] 时查询 x>95 可跳过该页,100 个互不重叠的文件查询 x>9000 可跳 90 个(90%),但 100 个文件统计都是 [0,5000] 时查询 x>4000 一个都跳不过(0%)。有效的前提是数据聚簇、粒度足够细、谓词可直接比较;它只可能多读,不会漏数据。

上游实现参照

Parquet 页索引与范围统计

本节 lab

下载卷五 Java 8 实验 · 实验运行与版本说明

在 bd-engine-lab 中验证 zone map 的跳过规则:

  • 源码: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。
  • 断言:用例 30 验证「page 统计 min=10、max=90 时,查询 x>95 可跳过该 page」;用例 31 验证「100 个文件、第 i 个区间 [i×100, i×100+99],查询 x>9000 跳过 90 个、命中 10 个」;用例 32 验证「100 个文件统计区间都是 [0,5000],查询 x>4000 跳过 0 个」。
  • 整卷 runner 的预期汇总为 TOTAL: 116 passed, 0 failed。

对应本节判断链:先看块内 min/max 能否与谓词区间不相交 → 把统计挂到文件、row group、page 三层 → 用 90/100 的账本确认聚簇的收益 → 用 0/100 的账本确认重叠的代价 → 最后用「聚簇、粒度、可比较谓词」三个条件判断 zone map 是否值得依赖。

继续阅读

探索更多技术文章

浏览归档,发现更多关于系统设计、工具链和工程实践的内容。

全部文章 返回首页

「books」更多文章

  1. 《大规模分布式计算深入解析》15.3 落地:从 Neo4j 到自研图引擎
  2. 《大规模分布式计算深入解析·图计算与图数据库内核》 · 目录与学习路径(45 篇)
  3. 《大规模分布式计算深入解析》15.2 十一卷主线:从切分到图