Lance Zone Map 索引(Zone Map Index)详解:基于分区统计的谓词下推与扫描剪枝机制
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 统计信息只落在一个文件里:
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 位图全局缓冲区在索引文件中的序号 |
rows_per_zone在写入时由write_index写入文件 Schema metadata(rust/lance-index/src/scalar/zonemap.rs),加载时若缺失则回退到默认值ROWS_PER_ZONE_DEFAULT = 8192(见 rust/lance-index/src/scalar/zonemap.rs)。null_bitmap记录 null 位图在**全局缓冲区(global buffer)**中的索引号,读取时通过read_global_buffer(idx)反序列化为RowAddrTreeMap(rust/lance-index/src/scalar/zonemap.rs)。
全局缓冲区
| 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 索引,是低成本提升扫描过滤与向量预过滤性能的首选手段。