Lance Zone Map 索引(Zone Map Index)详解:基于分区统计的谓词下推与扫描剪枝机制

原创2026-09-16 14:55:201,756 阅读
文章标签:数据湖湖仓一体大数据列式数据库向量数据库全文检索OLAP人工智能

Lance Zone Map 索引(Zone Map Index)详解:基于分区统计的谓词下推与扫描剪枝机制

导读

Zone Map(分区映射)是 Lance 标量索引体系中的基础结构,也是数据湖表格式中经典的列式存储加速手段。本指南以 docs/src/format/index/scalar/zonemap.md 为骨架,结合 rust/lance-index/src/scalar/zonemap.rs 的实现与 python/python/lance/dataset.py 的 Python API,系统讲解 Zone Map 的存储布局、文件 Schema、元数据设计、加速的查询类型以及底层裁剪判定逻辑。读完本文,你将掌握 Zone Map 索引在 Lance 中的工作原理、文件格式细节,以及如何在扫描过滤与向量预过滤场景中使用并调优它。

Zone Map 的核心原理

Zone Map 是一种列式数据库技术,服务于两个目标:谓词下推(predicate pushdown)与扫描剪枝(scan pruning)。其基本思想是:把一列数据切分成固定大小的块(称为 zone),并为每个 zone 维护一组摘要统计信息——最小值 min、最大值 max、空值数量 null_count(浮点列还额外记录 nan_count)。查询执行时,通过比较查询谓词与 zone 的 [min, max] 区间,直接排除那些不可能包含匹配值的 zone,从而跳过对应的数据页,减少 IO 与解码开销。

Zone Map 属于不精确(inexact)过滤器:

  • 它可以**确定性地排除(definitively exclude)**某个 zone;
  • 但也可能**误包含(false positive)**一些实际不匹配的 zone,这些残留 zone 需要在读取阶段重新检查(recheck)。

换句话说,Zone Map 与布隆过滤器类似,绝不会产生假阴性(false negative)——所有真正匹配的行都必然被保留下来,只是结果集可能偏大。这一特性使它可以安全地用于查询裁剪,而不必担心漏数据。

一个特殊之处是:由于“查找 NULL”是极其常见的查询模式,Lance 的 Zone Map 索引除 zone 统计外,还额外维护一张空值行位图(null bitmap),因此 IS NULL 查询可以通过该位图返回精确结果(exact results),而不是近似结果。

在 Lance 的整体索引体系中,Zone Map 属于**标量索引(scalar index)**中的“主跳读结构(primary skipping structure)”,与 B-Tree、Bitmap、全文检索等“次级结构(secondary structure)”并列,参见 docs/src/format/index/index.md 中的索引分类说明。

Index Details:ZoneMapIndexDetails 消息

IndexMetadata.index_details 是一个 protobuf Any 消息,用于存放索引类型特有的配置与参数。Zone Map 索引对应的消息定义位于 protos/index_old.proto(原文中的 %%% proto.message.ZoneMapIndexDetails %%% 即指向此处):

message ZoneMapIndexDetails {
  /* Number of rows per zone. Optional for backwards compatibility: absent on
   * datasets written before this field was added. When absent, no seed writer
   * is created for the index.
   */
  optional uint64 rows_per_zone = 1;
  /* Whether seed-based incremental updates are enabled for this index.
   * On-disk semantics: absent means seeds are disabled (old datasets written
   * before this field was added). Present false means explicitly disabled.
   * Present true means seeds are enabled: the index will embed per-fragment
   * seed buffers in data files and harvest them during incremental updates
   * to skip full column scans.
   * Creation-time default: index creation code sets this to true for
   * variable-length types (strings, binary) and fixed-width types wider than
   * 8 bytes, and to false for narrow fixed-width types (e.g. Int64, Float64).
   */
  optional bool use_seeds = 2;
  /* Whether this index tracks exact null row addresses in a separate bitmap.
   * Absent or false means legacy format: null positions are not tracked and
   * IS NULL searches fall back to approximate zone-level statistics. Present
   * true means IS NULL is exact and IS NOT NULL can be answered without a
   * full scan.
   */
  optional bool has_null_bitmap = 3;
}

三个字段的语义如下:

字段 类型 含义
rows_per_zone optional uint64 每个 zone 包含的行数;缺省表示兼容旧数据集(该字段引入前写入),此时不会为该索引创建 seed writer
use_seeds optional bool 是否启用基于 seed 的增量更新:索引会按 fragment 将 seed 缓冲区嵌入数据文件,增量更新时通过收获 seed 跳过整列扫描;缺省视为禁用(旧数据集),创建时对可变长度类型与宽度 > 8 字节的定宽类型自动置 true
has_null_bitmap optional bool 索引是否在独立位图中记录精确的空值行地址;缺省或 false 表示旧格式,IS NULL 退化为 zone 级近似统计;为 true 时 IS NULL 精确、IS NOT NULL 也可免全扫描回答

存储布局与文件格式

与 B-Tree 等索引一样,Zone Map 索引的内容存放在数据集根目录下的 _indices/{UUID}/ 目录中,其中 {UUID} 是索引段的唯一标识(详见 docs/src/format/table/layout.md 的目录结构说明)。Zone Map 索引的存储极为精简,所有 zone 统计信息只落在一个文件里:

  1. zonemap.lance — 用于查询剪枝的 zone 统计文件

对应源码中的常量定义见 rust/lance-index/src/scalar/zonemap.rs:const ZONEMAP_FILENAME: &str = "zonemap.lance"。由于该文件本身就是一个 Lance 文件,读写完全复用现有的 Lance 文件格式代码,这也是 docs/src/format/index/index.md 中“索引内容多为 Lance 文件”设计原则的具体体现。

Zone 统计文件 Schema

zonemap.lance 中每个 zone 占一行记录,列定义如下(与源码中 ZoneMapIndexBuilder::zonemap_stats_as_batch 构造的 RecordBatch Schema 完全一致,见 rust/lance-index/src/scalar/zonemap.rs):

列 类型 可空 说明
min {DataType} true zone 内最小值;若整个 zone 全为 NULL,则为 NULL
max {DataType} true zone 内最大值;若整个 zone 全为 NULL,则为 NULL
null_count UInt32 false zone 内 NULL 值的数量
nan_count UInt32 false zone 内 NaN 值的数量(仅浮点类型有意义)
fragment_id UInt64 false 该 zone 所属的 fragment
zone_start UInt64 false zone 在 fragment 内的起始行偏移
zone_length UInt32 false 该 zone 的行数

注意:文档表格中 zone_length 标注为 UInt32,而源码中该列实际以 UInt64 数组构造(UInt64Array::from_iter_values(...))。以源码为准,其余各列的 UInt32/UInt64 类型与文档一致。源码加载时对 null_count、nan_count 强校验为 UInt32,对 fragment_id、zone_start 强校验为 UInt64(见 rust/lance-index/src/scalar/zonemap.rs)。

这 7 列与内存中的 ZoneMapStatistics 结构一一对应(rust/lance-index/src/scalar/zonemap.rs):min、max、null_count、nan_count,以及由 fragment_id、zone_start、zone_length 三元组共同构成的 zone 边界(ZoneBound)。

Schema 元数据

文件 Schema 的 metadata 中还写入两条关键信息(常量定义见 rust/lance-index/src/scalar/zonemap.rs):

Key 类型 说明
rows_per_zone String 每个 zone 的行数(默认 "8192")
null_bitmap UInt32 null 位图全局缓冲区在索引文件中的序号

全局缓冲区

Metadata Key 说明
null_bitmap 一个序列化的 RowAddrTreeMap,精确记录哪些行是 NULL

写入时,若索引持有完整的 null 位图,则将序列化后的 RowAddrTreeMap 作为全局缓冲区附加到 zonemap.lance,并在文件 metadata 中登记缓冲区序号(rust/lance-index/src/scalar/zonemap.rs);若为旧格式(无位图),则不写全局缓冲区,查询时退化为保守的 zone 级统计。

如何切分 Zone:一个直观示例

源码注释中给出了一个非常直观的分区示例(rust/lance-index/src/scalar/zonemap.rs)。假设输入如下:

  • Fragment 1:10 行,行号 0 → 9
  • Fragment 2:7 行,行号 10 → 16
  • Fragment 3:4 行,行号 20 → 23
  • 用户指定的 zone 大小(rows_per_zone)为 5

则生成的 zone 统计为:

fragment id min max zone_length
1 0 4 5
1 5 9 5
2 10 14 5
2 15 16 2
3 20 23 4

可以看到:zone 的切分不会跨越 fragment 边界,每个 zone 恰好落在单个 fragment 内;最后一个不足 rows_per_zone 的尾巴行数由 zone_length 记录。加载索引时,所有 zone 按 (fragment_id, zone_start) 排序,便于顺序读取与合并。

加速的查询类型

Zone Map 索引对下列查询提供不精确(inexact)的候选集(其中空值类查询返回精确结果):

查询类型 说明 判定操作 结果类型
Equals column = value 保留满足 min ≤ value ≤ max 的 zone AtMost
Range column BETWEEN a AND b 保留与查询区间有重叠的 zone AtMost
IsIn column IN (v1, v2, ...) 保留可能包含集合中任一值的 zone AtMost
IsNull column IS NULL 保留 null_count > 0 的 zone Exact

这里的“结果类型”对应搜索结果的语义:

  • AtMost:返回的行地址是候选超集(可能包含不匹配的行,需要 recheck);
  • Exact:返回的行地址精确匹配查询条件。

在实现层面,ScalarIndex::search 会根据查询类型路由到不同的判定逻辑(rust/lance-index/src/scalar/zonemap.rs):

  • 当查询是 IsNull 且索引持有 null 位图时,直接返回 SearchResult::exact(null_rows.clone())——这正是文档所说“IS NULL 返回精确结果”的源码依据;
  • 其余情况调用 search_zones,对每个 zone 执行 evaluate_zone_against_query 判定,结果封装为 SearchResult::at_most(...)。

底层判定逻辑与边界情况(源码级解读)

evaluate_zone_against_query(rust/lance-index/src/scalar/zonemap.rs)实现了上表中各查询类型的精确判定,其中包含大量容易被忽略的边界细节:

1. Equals(等值查询)

  • 目标值为 NULL:zone 的 null_count > 0 则保留;
  • 目标值为 NaN(浮点类型):zone 的 nan_count > 0 则保留;
  • 普通值:保留 min ≤ value ≤ max 的 zone;
  • 若 zone 缺失极值(全 NULL zone,min/max 为 NULL):根据 zone_has_comparable_values 判断——只要 zone 中存在可比较值(zone_length > null_count + nan_count),就保守保留该 zone,避免漏数据。

2. Range(区间查询)

  • 区间与 zone 的 [min, max] 有交集即保留;
  • 对 NaN 做了细致处理:例如下界为 NaN(Included)时只检查 nan_count > 0;上界为 Excluded NaN 时则视为“无值大于 NaN”,直接排除;
  • zone 的 max 为 NaN 时保守保留(因为真实最大有限值未知)。

3. IsIn(集合查询)

只要集合中任一值可能命中 zone 就保留:NULL 看 null_count,NaN 看 nan_count,普通值看 [min, max] 区间。

4. LikePrefix(前缀查询)

虽然不在文档的加速表中,源码还为字符串前缀匹配(LIKE 'foo%' 类查询)实现了专用的 zone 判定:zone 的 max ≥ prefix 且 min < next_prefix(next_prefix 通过对前缀最后一个字节自增计算得出,处理了 0xFF 溢出),即可保留该 zone。

5. 嵌套类型(Nested Types)的特殊处理

对于 List、FixedSizeList、Struct、Map 等嵌套类型,zone 中只记录 null_count,min/max 以类型化 NULL 占位(rust/lance-index/src/scalar/zonemap.rs 与 rust/lance-index/src/scalar/zonemap.rs)。判定时只能依据 null 统计:全 NULL 的 zone 在等值/集合查询中可直接排除,IS NULL 则看 null_count > 0。相应地,嵌套类型的全局 <a href="https://link.gitcode.com/i/13e96cc56eaefe2c314eb3a23df1d183" target="_blank">min, max] 折叠(value_range_over)会直接返回 None([rust/lance-index/src/scalar/zonemap.rs)。

6. NaN 的全局极值语义

在跨段折叠全局 <a href="https://link.gitcode.com/i/823c0679ab2b38dff632cd2d1d88260e" target="_blank">min, max](value_range_over,用于统计类下推)时,只要任一 zone 的 max 为 NaN,就放弃折叠——因为 ScalarValue 的全序中 NaN 排在所有有限值之上,直接折叠会得到错误的“伪上界”,从而剪掉本应保留的行([rust/lance-index/src/scalar/zonemap.rs)。这一保守策略保证了 Zone Map 永不假阴性的性质。

在 Python 中使用 Zone Map 索引

创建索引

在 Lance Python 库中,通过 LanceDataset.create_scalar_index 创建 Zone Map 索引(python/python/lance/dataset.py),index_type 传 "ZONEMAP":

import lance

dataset = lance.dataset("s3://my-bucket/images.lance")

# 在 my_col 上创建 Zone Map 索引
dataset.create_scalar_index("my_col", "ZONEMAP")

# 指定 rows_per_zone 参数
dataset.create_scalar_index(
    "my_col",
    "ZONEMAP",
    replace=True,
    rows_per_zone=16384,
)

API 文档对 ZONEMAP 类型的描述如下(python/python/lance/dataset.py):

ZONEMAP:这种不精确索引把列切分为固定大小的 zone 块,并为每个 zone 存储摘要统计(min, max, null_count, nan_count, fragment_id, local_row_offset)。它非常小,但只有当列大致有序时效果才好。

这段说明点出了 Zone Map 的适用前提:数据列应近似按序排列。若列值随机散乱,几乎每个 zone 的 [min, max] 区间都会覆盖全域,剪枝收益趋近于零。

通过扫描过滤受益

创建索引后,包含该列过滤条件的扫描会自动受益(python/python/lance/dataset.py):

my_table = dataset.scanner(filter="my_col != 7").to_table()

向量检索的预过滤(prefilter)场景同样可以利用标量索引加速:

my_table = dataset.scanner(
    nearest=dict(
        column="vector",
        q=[1, 2, 3, 4],
        k=10,
    ),
    filter="my_col != 7",
    prefilter=True,
)

常用参数

参数 默认值 说明
replace True 若同名列已存在索引,是否替换重建
train True 是否在数据上训练;False 时创建可后续填充的空索引
fragment_ids 无 仅在指定 fragment 上建索引,支持分布式/分片级索引
rows_per_zone "8192" 每个 zone 的行数(经 index_config 传入)
name 列名派生 索引名称

此外,create_scalar_index 还支持 index_uuid、progress_callback、format_version 等高级参数,具体签名见 python/python/lance/dataset.py。

参数调优与增量维护

rows_per_zone 的选择

rows_per_zone 是 Zone Map 唯一的核心调优参数,默认值 8192(常量 ROWS_PER_ZONE_DEFAULT,注释为“每两个 batch 一个 zone”,见 rust/lance-index/src/scalar/zonemap.rs)。其权衡如下:

  • zone 越小:剪枝粒度越细,假阳性越少,裁剪越精确,但统计文件行数越多、元数据开销越大;
  • zone 越大:索引文件更紧凑,但 [min, max] 区间更宽,假阳性更多,剪枝效果下降。

此外,rows_per_zone 还通过环境变量 LANCE_ZONEMAP_DEFAULT_ROWS_PER_ZONE 提供全局默认值(rust/lance-index/src/scalar/zonemap.rs)。注意:合并多个 Zone Map 段时,若各段的 rows_per_zone 或值类型不一致,会直接报错(见 merge_zonemap_indices 的校验逻辑,rust/lance-index/src/scalar/zonemap.rs),因此重建索引时应保持参数一致。

seed 机制与增量更新

Zone Map 索引支持“只更新新增数据”的增量维护(UpdateCriteria::only_new_data,rust/lance-index/src/scalar/zonemap.rs)。为了加速增量更新,Lance 引入了 seed 机制:建索引时把每个 fragment 的 zone 统计“种子”嵌入数据文件,增量更新时直接收获这些 seed 而不必重扫整列。

是否启用 seed 由 use_seeds 决定,创建索引时按列类型自动选择(default_use_seeds,rust/lance-index/src/scalar/zonemap.rs):

  • 启用:可变长度类型(Utf8/LargeUtf8/Utf8View/Binary/LargeBinary/BinaryView)、Decimal128/Decimal256、宽度 > 8 字节的 FixedSizeBinary、以及所有嵌套类型——这类列的扫描代价高,跳过整列扫描收益显著;
  • 禁用:宽度 ≤ 8 字节的定宽类型(如 Int64、Float64)——扫描足够快,seed 开销不划算。

空值位图的兼容性约束

旧格式索引(has_null_bitmap 为 false)没有 null 位图,此时:

  • IS NULL 退化为基于 null_count 的近似回答;
  • 增量更新时若旧索引无位图,合并后的新索引会保持无位图状态(源码注释明确指出:更新无法恢复缺失的信息,声称“结果无 null”将是假阴性),只有全量重建(retrain)才能生成完整的 null 位图(rust/lance-index/src/scalar/zonemap.rs)。

与其他标量索引的取舍

Zone Map 在 Lance 的标量索引家族中扮演“主跳读结构”的角色(见 docs/src/format/index/index.md)。与 B-Tree、Bitmap、Bloom Filter 相比,它的典型取舍是:

特性 Zone Map B-Tree Bitmap Bloom Filter
结果精度 不精确(IS NULL 除外) 精确 精确 不精确
体积 极小(每 zone 一行) 较大 与基数成正比 小
适用场景 近似有序列的范围/等值裁剪 高基数、多唯一值 低基数、多行每值 等值/不等值过滤
支持的谓词 等值、范围、集合、IS NULL、前缀 等值、范围、排序 等值、集合 等值、不等值

正因为体积小、构建快,Zone Map 常常作为“默认就位”的轻量剪枝层,与重量级精确索引配合使用:先用 Zone Map 粗筛、再用数据页内 recheck 兜底,形成“不精确过滤 + 精确复核”的两级管线。

小结

Zone Map 索引是 Lance 中体积最小、构建最廉价的标量索引形态:它将列按 rows_per_zone(默认 8192)切成 zone,以单文件 zonemap.lance 保存每个 zone 的 min/max/null_count/nan_count 及 fragment 内边界信息,通过 [min, max] 区间裁剪为等值、范围、集合与前缀查询提供不精确的 AtMost 候选集,并借助全局 null 位图为 IS NULL 提供精确结果。其实现要点——NaN 语义、嵌套类型退化、全 NULL zone 的保守保留、seed 增量更新与旧格式兼容——都可在 rust/lance-index/src/scalar/zonemap.rs 的源码中得到印证。在实际业务中,对“大致有序”的列(如时间戳、单调递增 ID)建立 Zone Map 索引,是低成本提升扫描过滤与向量预过滤性能的首选手段。

登录后查看全文
lance