列式存储的宣称是"只读需要的列",但只读列不等于少读数据——一次 WHERE event_time BETWEEN ... 仍可能把整列几十亿行的字节从磁盘读进内存、解压、再逐行比对。真正的性能杠杆藏在数据跳过(Data Skipping):为每个数据块维护一份极小的摘要元数据,查询时先用它判断"这个块里绝不可能有我要的行",从而在解压和逐行扫描之前就整块排除。Zone Map 用 min/max/null count 裁剪范围查询,稀疏索引用少量主键锚点二分定位,Bloom Filter 用几位数组回答"这个值肯定不在本块"。三者是 Parquet、ORC、ClickHouse、DuckDB 冷查询快到离谱的共同底座。本文从一张扫描账单讲起,逐层剖析这三种结构的原理、适用边界与协同漏斗,最后给出一份本地实跑验证过(12 万行数据、零漏报)的 Python 教学实现。

一、扫描的代价:为什么"只读列"还不够

先把一次列式查询的成本拆开。从 SSD 到结果集,一次全列扫描大致经过:读页 → 解压 → 解码 → 逐行谓词求值。列存靠压缩和向量化把后三步做得很高效,但第一步的 I/O 和第二步的解压仍与扫描字节总量成正比。若一个 10 亿行的 event_time 列压缩后仍有 4 GB,即使解压吞吐做到 2 GB/s,光读这一列就要 2 秒——而查询可能只要其中 100 行。

数据跳过的核心洞察是:大部分谓词具有"局部性"。时间、自增 ID、价格这类列往往按某种顺序写入,相邻的行在值域上也相邻。于是可以给每个块配一份几字节到几百字节的摘要,查询时先查摘要:

  • 若谓词与摘要必然无交集,整块跳过——省掉全部 I/O 与解压。
  • 若摘要可能有交集,才解压该块做精确扫描——多付的只是"假阳性"块的无效扫描。

这是一笔典型的用元数据空间换扫描时间的交易:摘要通常不到数据量的 1%,却能把扫描量砍掉一到三个数量级。关键在于摘要必须满足一条铁律——零漏报(no false negative):摘要说"不在",就绝不能真的在。否则会漏掉结果,破坏正确性。所有数据跳过结构都在这条铁律下,尽力压低"假阳性"。

二、Zone Map:用 min/max 守住范围查询

Zone Map(也叫段/块统计、min-max index、Zone Map 元数据)是最简单也最广泛的结构。它为每个数据块(Parquet 的 Row Group/Page、ORC 的 Stripe、ClickHouse 的 Granule、DuckDB 的 Row Group)记录三个值:

  • min / max:块内该列的最小值与最大值;
  • null_count:NULL 值个数(用于 IS NULL 判断,也帮助优化器估算选择率)。

对谓词 lo <= x <= hi,若 max < lo 或 min > hi,说明整个块的值域与查询区间不重叠,可安全跳过。这个判断是充分不必要的:区间重叠不代表块内一定有命中的行(块内可能只有 min 和 max 两个端点值),所以 Zone Map 会有假阳性,但绝不会漏报——完全符合铁律。

下面是一次真实验证:12 万行按值聚簇写入,每 4096 行一块。查询 [900, 999] 时,30 个块被跳过了 26 个,只解压 4 块就返回了与暴力扫描逐行一致的 9998 行结果。

class ZoneMap:
    """一个数据块/段(row group / granule / page)的统计摘要。"""
    def __init__(self, values):
        self.row_count = len(values)
        non_null = [v for v in values if v is not None]
        self.null_count = len(values) - len(non_null)
        self.min = min(non_null) if non_null else None
        self.max = max(non_null) if non_null else None

    def can_skip_range(self, lo, hi):
        """谓词 lo <= x <= hi:区间与 [min,max] 无交集则可跳过。"""
        if self.min is None:
            return True                       # 全 NULL 块,对非空区间必然可跳
        return self.max < lo or self.min > hi

    def can_skip_equal(self, v):
        if self.min is None:
            return True
        return v < self.min or v > self.max

# [TEST 2 PASS] 范围查询 [900,999]:Zone 裁剪 26/30 块,
# 命中 9998 行,与暴力扫描逐行一致

注意 min is None(全 NULL 块)的处理:对"值落在某个非空区间"的查询,全 NULL 块必然可跳过;但 can_skip_equal(None) 要单独定义语义。边界条件与空值是 Zone Map 实现里最容易出错的地方,教学实现中专门用 TEST 3 覆盖了全 NULL 段与恰好命中 min 的情形。

三、灵魂前提:数据局部性决定裁剪率

Zone Map 的裁剪率几乎完全取决于数据在值域上的局部性。同样是 12 万行,按值单调写入时每块的 max - min 约 40,范围查询能精准命中少数块;一旦把行打乱,每块的值域跨度会暴涨到约 1199——因为一个块里同时混进了很小和很大的值,任意区间的 min/max 都不得不覆盖整个值域,Zone Map 宣告失效。

教学实现用 TEST 6 量化了这个效应:乱序让段跨度膨胀了约 30 倍(40 → 1199)。这正是为什么列式系统如此看重聚簇/排序键:ClickHouse 的 ORDER BY、Parquet 写入前按时间排序、排序后的批量导入,本质上都是在"为 Zone Map 制造局部性"。数据跳过不是免费的魔法,它是写入时排序成本在查询时的回报。

import random
random.seed(7)
shuffled = col[:]; random.shuffle(shuffled)
szms = build_zone_maps(shuffled, BLOCK)
avg_span = sum((z.max - z.min) for z in szms if z.min is not None) / len(szms)
ordered_span = sum((z.max - z.min) for z in zms if z.min is not None) / len(zms)
assert avg_span > ordered_span * 20
# [TEST 6 PASS] 乱序使段跨度膨胀 30x(40 -> 1199),印证聚簇是裁剪前提

工程推论:如果一张表的查询几乎总是按时间范围过滤,那就该按时间排序落盘;如果查询模式无法预测,Zone Map 的收益会显著下降,此时要更多依赖后文的 Bloom Filter 与倒排/二级索引。

四、稀疏索引:用少量锚点二分定位

Zone Map 解决"值在不在这个块",稀疏索引解决"要找的主键落在哪个块"。它借鉴了 B+ 树的思想但更省:不为每一行建索引项,而是每个数据块只记一个锚点(通常是块内首行的主键)。30 个块就只有 30 个键,可以常驻内存。查询时二分找到"最后一个 <= key 的锚点",就锁定了候选块,再进块内精确比对。

代价是只能定位到块、不能定位到行:因为锚点是稀疏的,候选块内仍要做一次小规模扫描(这就是 ClickHouse 里 "mark" 与 granule 的关系)。它牺牲了一点精度,换来索引体积缩小几个数量级,非常适合"读多写少、按主键范围查"的分析场景。

import bisect
class SparseIndex:
    """每 block_size 行只记一个 (首键, 块号),二分定位候选块。"""
    def __init__(self, sorted_keys, block_size):
        self.block_size = block_size
        self.keys = []                        # 每块的首键
        for start in range(0, len(sorted_keys), block_size):
            self.keys.append(sorted_keys[start])

    def locate(self, key):
        idx = bisect.bisect_right(self.keys, key) - 1
        return 0 if idx < 0 else idx           # 小于首键仍查第一块

# [TEST 4 PASS] 稀疏索引 30 个锚点,6 个探测点二分定位均落候选块

前提同样是主键有序。教学实现用 bisect_right(key)-1 处理了"key 恰好等于锚点"和"key 小于首键"的边界,6 个探测点(首键、块边界、末键)全部落在正确候选块。真实系统(如 ClickHouse 的 primary key index)会额外做多级跳跃,把"候选块"再收窄。

五、Bloom Filter:回答"肯定不在"

Zone Map 对等值查询无能为力:WHERE user_id = 9527 时,只要块的 min ≤ 9527 ≤ max 就得扫描,而一个跨度大的块几乎总是满足这个条件。Bloom Filter(布隆过滤器)填补了这个空缺。它是一个 m 位的位数组,插入元素时用 k 个哈希函数把对应位置置 1;查询时若任意一个哈希位是 0,则元素一定不在集合里,可以整块跳过;若全是 1,则"可能在"(有误报)。

它同样满足零漏报铁律:只要插入过,所有 k 个位都是 1,查询不可能返回"不在"。代价是假阳性——没插入的元素也可能恰好把所有位都撞成 1。误报率近似 (1 - e^(-kn/m))^k,在 k = (m/n)·ln2 时最优。教学实现按这个公式自动取 k,1.6 万字节(2^17 bit)装 1 万个元素、k=9 时,误报率仅 0.76%,漏报为 0。

class BloomFilter:
    """位数组 + 双哈希(FNV-1a 派生),无漏报,有可控误报。"""
    def __init__(self, m_bits, n_items):
        self.m = m_bits
        self.k = max(1, min(16, int(round(m_bits / max(n_items, 1) * 0.693))))
        self.bits = [0] * m_bits

    def _hashes(self, item):
        s = str(item).encode('utf-8')
        h1, h2 = 14695981039346656037, 1099511628211
        for b in s:                            # 两个不同种子的 FNV-1a
            h1 = (h1 ^ b) * 1099511628211 & 0xFFFFFFFFFFFFFFFF
            h2 = (h2 ^ b) * 14695981039346656037 & 0xFFFFFFFFFFFFFFFF
        for i in range(self.k):
            yield (h1 + i * h2) % self.m

    def add(self, item):
        for idx in self._hashes(item):
            self.bits[idx] = 1

    def might_contain(self, item):
        return all(self.bits[idx] for idx in self._hashes(item))

# [TEST 5 PASS] Bloom k=9, m=131072:漏报 0,误报 1528/200000 = 0.7640% (<2%)

实现里用两个 FNV-1a 种子派生出 k 个哈希(h1 + i·h2 的增强双重哈希技巧),避免了 k 次独立哈希的开销,且分布质量足够。位与操作 & 0xFFFF... 在文章 HTML 中必须转义为 &amp;(否则会被当作实体解析),这也是所有技术文把代码放进 <pre> 时必须逐一检查的转义陷阱。

六、三者协同:一条分层剪枝漏斗

三种结构不是互斥的,而是可以叠成一条由粗到细的漏斗。以 ClickHouse 处理一段范围查询为例,一次扫描依次经过:

  • 分区裁剪(Partition Pruning):按分区键(常是日期)直接排除整个分区目录,最粗粒度、收益最大;
  • Zone Map / 主键索引:在候选分区内,用 min/max 排除不相交的 Granule;
  • Bloom Filter 索引(若建了):对等值/IN 谓词,用位数组再排掉一批 Granule;
  • 精确扫描 + 向量化求值:只剩少数候选块真正解压、逐行比对。

每往下一层,候选数据量骤减,但单层开销也更高——所以顺序是"便宜粗筛在前、昂贵精查在后"。下面的漏斗函数演示了这个骨架:

def funnel_query(zone_maps, blocks, lo, hi, block_size):
    """分段扫描:Zone Map 裁掉不相交块 -> 命中块内精确扫描。
    返回 (命中行, 实际扫描块数, Zone裁剪数)。"""
    scanned = z_skipped = 0
    hits = []
    for i, zm in enumerate(zone_maps):
        if zm.can_skip_range(lo, hi):        # 第一层:段级裁剪
            z_skipped += 1
            continue
        scanned += 1                          # 第二层:块内精确扫描
        for row_idx, v in enumerate(blocks[i]):
            if v is not None and lo <= v <= hi:
                hits.append((i * block_size + row_idx, v))
    return hits, scanned, z_skipped

# 实测:30 块中 Zone 裁剪 26 块,仅解压 4 块即得完整结果

要点在于正确性由最细粒度保证:无论上层怎么跳,最终命中块内一定做了逐行精确比对;而上层只可能"多留"候选(假阳性),不会"错丢"(漏报)。这种分层设计让每层都可以独立优化、独立开关,而不影响结果正确性。

七、三种结构横向对比

把三种结构的特性放在一起看,边界就很清楚了:Zone Map 擅长有序数据的范围查询,稀疏索引擅长按主键定位,Bloom Filter 擅长高基数列的等值存在性判断。它们对存储、内存、数据局部性的要求各不相同,真实系统往往按需组合。

结构擅长谓词元数据开销假阳性来源前提
Zone Map范围 / 等值 / IS NULL每块 min/max/null,极低值域重叠但块内无命中数据按查询键聚簇
稀疏索引主键等值 / 前缀范围每块一个锚点,可全内存稀疏性,需块内精查主键有序
Bloom Filter高基数列等值 / IN每块位数组,m/n 位/元素哈希碰撞,可控无,但不支持范围

三者都遵循零漏报铁律,区别只在"会不会多扫"。因此组合使用时,可以放心地把它们当成纯优化:开关掉任意一个,查询结果不变,只是变慢。

八、工程权衡:元数据放哪、何时失效

把数据跳过落到生产系统,有几个绕不开的工程问题:

  • 元数据存放位置:Parquet 把 Zone Map 直接写进文件尾部的 Footer(Row Group / Column Chunk 的 statistics),读取时先读 Footer;ORC 存在 Stripe Footer;ClickHouse 的PrimaryKey 索引常驻内存(primary.idx)。放文件内随数据一起移动、一致性好;放内存则查询快但要常驻成本。
  • 写入放大与批量:Zone Map/Bloom 必须在写入时构建。小块(granule)裁剪更精细但元数据更多,大块反之。ClickHouse 默认 granule 8192 行,就是在精度与开销间取的折中。
  • 更新导致失效:UPDATE/DELETE 会让原有 min/max 变宽松甚至失效。LSM 类系统靠"新版本文件 + 旧文件标记删除"规避就地更新,从而保住 Zone Map 的紧凑性——这也是列存/LSM 天生更适合数据跳过的原因。
  • 选择率估算:Zone Map 的 min/max/null_count 还能喂给优化器估算过滤后的行数,辅助 join order 与索引选择。一份元数据,裁剪与优化两用。

一个常被忽略的点是假阳性的累积:单块 Bloom 误报 1% 看似无害,但若查询跨越上千块,冗余扫描会叠加。因此高基数列上通常会调大 m/n(每元素更多位)来压低误报,用少量内存换稳定的查询延迟。

九、完整教学实现与验证

下面把三块核心结构与漏斗查询串起来。完整脚本 verify_data_skipping.py 已在本地 Python 3 实跑通过:12 万行数据、30 个数据块,6 组断言全部 PASS。这里给出骨架与实测输出:

def build_zone_maps(columns, block_size):
    maps = []
    for start in range(0, len(columns), block_size):
        maps.append(ZoneMap(columns[start:start + block_size]))
    return maps

# ===== 实跑输出 =====
# [数据] rows=120000, block_size=4096, blocks=30
# [TEST 1 PASS] Zone Map min/max/null_count 与暴力统计一致
# [TEST 2 PASS] 范围查询 [900,999]:Zone 裁剪 26/30 块,命中 9998 行,逐行一致
# [TEST 3 PASS] 边界值与全 NULL 段裁剪安全,无漏报
# [TEST 4 PASS] 稀疏索引 30 个锚点,6 个探测点二分定位均落候选块
# [TEST 5 PASS] Bloom k=9, m=131072:漏报 0,误报 1528/200000 = 0.7640%
# [TEST 6 PASS] 乱序使段跨度膨胀 30x(40 -> 1199),印证聚簇是裁剪前提
# ALL TESTS PASSED

这组验证刻意覆盖了三类容易出错的边界:全 NULL 块(min is None)、恰好命中 min/max 端点、稀疏索引的首键与末键。数据跳过结构的 bug 往往不出在主逻辑,而出在这些边界上——一旦边界判断错,就可能静默漏掉结果,且很难在测试集里暴露。

十、主流系统里的对应实现

最后把理论落回现实,看看各大系统分别用了哪些结构。你会发现本文剖析的三种结构几乎无处不在,只是换了名字:

系统Zone Map 对应稀疏索引对应Bloom 对应
ParquetRow Group / Page statistics (min/max/null)Page Index(偏移索引)Bloom Filter 列块
ORCStripe/Row Group statisticsRow Level IndexBloom Filter (列级)
ClickHouseGranule min/max(PK 索引派生)primary.idx 稀疏主键索引bloom_filter 跳数索引
DuckDBRow Group min/max + 分区裁剪ArtIndex / 区间映射列段过滤
Apache DruidSegment 时间/列范围倒排索引位图Query Cache + 过滤

名字各异,本质同一套思想:用廉价摘要换昂贵扫描,用局部性换裁剪率,用假阳性换零漏报。理解了 Zone Map、稀疏索引与 Bloom Filter 这三块积木,再去看任何一个列式引擎的查询路径,都能迅速定位它的"跳过层"在哪里、为什么这么设计。

结语

数据跳过是列式存储里"最不起眼却最有效"的一环。它不改变查询结果,只在扫描前做减法;它依赖的不是复杂算法,而是写入时的有序与聚簇。Zone Map 守住范围查询,稀疏索引定位主键,Bloom Filter 攻克高基数等值,三者叠成一条从粗到细的漏斗,把"读整列"变成"读几块"。教学实现用 12 万行数据验证了这条链路:26/30 块被裁剪、零漏报、误报可控。下次当你惊叹于 ClickHouse 秒级扫过十亿行时,请记得——它快,往往不是因为算得快,而是因为压根没去算那些不可能的数据。

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论
立即
投稿

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部