企业官网建设流程全解析

Lance Label List Index 详解：基于位图的多值列集合查询加速

【免费下载链接】lanceOpen Lakehouse Format for Multimodal AI. Convert from Parquet in 2 lines of code for 100x faster random access, vector index, and data versioning. Compatible with Pandas, DuckDB, Polars, Pyarrow, and PyTorch with more integrations coming..项目地址: https://gitcode.com/GitHub_Trending/la/lance

Label List Index 是 Lance 为"一行包含多个标签（tags/labels）"这类列表型列专门设计的标量索引，它通过底层位图（bitmap）将array_has/array_contains、array_has_all、array_has_any等集合类过滤从全表扫描改写为"查位图 + 并/交运算"，并返回精确结果。本文以 docs/src/format/index/scalar/label_list.md 为骨架，结合 rust/lance-index/src/scalar/label_list.rs 等源码实现，完整讲解其存储布局、加速查询类型、NULL 语义以及实际使用方式，帮助你在标签类多值列上正确建索引并验证加速效果。

什么是 Label List Index

在真实业务中，一个数据行往往携带多个离散标签：例如一篇文章的tags = ["ai", "database", "vector"]、一部电影的genres = ["action", "sci-fi"]，或一个用户的roles = ["admin", "editor"]。这类列在 Arrow 中通常建模为List<T>（或LargeList<T>）类型，针对它的查询绝大多数是集合成员判断：

• 这一行是否包含某个标签？
• 是否同时包含多个标签（and 语义）？
• 是否包含任意一个标签（or 语义）？

对这类多值列，普通的 B-Tree 或 Zonemap 索引难以直接生效，而逐个展开列表做全表扫描在数据量大时代价高昂。Label List Index 正是为此而生：它把列表列"摊平（unnest）"成一个个独立的值，为每个唯一标签建立一张行位图，查询时只需查位图再做集合运算，从而把集合过滤加速到接近 O(1) 的位图查找级别。

从 Python SDK 的文档字符串可以看到它的官方定位（python/python/lance/dataset.py）：

LABEL_LIST. A special index that is used to index list columns whose values have small cardinality. For example, a column that contains lists of tags (e.g.["tag1", "tag2", "tag3"]) can be indexed with aLABEL_LISTindex. This index can speed up list membership filters such asarray_has_any,array_has_all, andarray_has/array_contains.

适用前提可以概括为两点：

• 列类型必须是List<T>或LargeList<T>，且元素类型不能是嵌套类型（如List<List<...>>不允许）；
• 标签基数（cardinality）较小、每值行数较多时收益最明显——这与 BITMAP 索引的适用场景一致，因为底层就是一张位图查找表。

索引元数据：LabelListIndexDetails

原文档通过如下 protobuf 占位符引用索引的元数据消息：

%%% proto.message.LabelListIndexDetails %%%

对应的消息定义在 rust/lance-index/protos/index_old.proto：

message LabelListIndexDetails {}

这是一个空消息。正如该 proto 文件头部注释所解释的：目前多数索引细节要么是硬编码的（例如固定文件名），要么直接存储在索引文件自身，因此不需要在 proto 中携带额外字段。文件还特别注明：不要在此文件新增索引细节，新消息应放到index.proto（lance.index包命名空间），此处的消息仅用于向前兼容。

在实际实现中，索引版本号是硬编码常量LABEL_LIST_INDEX_VERSION: u32 = 1（见 rust/lance-index/src/scalar/label_list.rs），插件版本version()也返回该值；每次创建/更新/合并索引时，都会把LabelListIndexDetails::default()序列化为prost_types::Any写入CreatedIndex.index_details。

存储布局与文件 Schema

Label List Index内部使用位图索引，数据存放在一个固定名称的文件中：

1. bitmap_page_lookup.lance—— 位图索引，负责把每个唯一标签映射到出现该标签的行 ID 集合

该文件名在源码中以常量形式硬编码（rust/lance-index/src/scalar/label_list.rs）：

pub const BITMAP_LOOKUP_NAME: &str = "bitmap_page_lookup.lance";

这个文件同时也是普通 BITMAP 索引的存储文件（见 docs/src/format/index/scalar/bitmap.md 与 rust/lance-index/src/scalar/bitmap.rs 中的同名常量），印证了 Label List Index 是"位图索引之上的封装"这一设计。

文件内部是标准的 Arrow/RecordBatch 布局，Schema 如下：

其中bitmaps列的序列化载体是RowAddrTreeMap——Lance 中用于存储行地址集合的结构（支持与 RoaringBitmap 互相转换、并/交运算和序列化）。注意keys列的类型{DataType}是占位符，实际写入时由被索引列的元素类型决定（例如Utf8、Int32等）。

此外，文件中还会通过 Schema 元数据携带一条特殊的附加信息（rust/lance-index/src/scalar/label_list.rs）：

pub const LABEL_LIST_NULLS_METADATA_KEY: &str = "lance:label_list_nulls"; pub const LABEL_LIST_NULLS_MIN_VERSION: i32 = 1;

lance:label_list_nulls元数据中序列化了一份"列表级 NULL 行集合"（见后文 NULL 语义一节），由write_label_list_bitmap_index通过BitmapIndexPlugin::write_bitmap_index_with_extras连同位图状态一起写入文件（rust/lance-index/src/scalar/label_list.rs）。

加速的查询类型

原文档给出了 Label List Index 可以精确加速（返回 Exact 结果）的三种查询：

这一行为在源码中有完整对应。查询解析器 rust/lance-index/src/scalar/expression.rs 中的LabelListQueryParser将 SQL/DataFusion 表达式翻译为内部查询对象：

• array_has(col, v)（DataFusion 会把array_contains归一化为array_has）→ 构造LabelListQuery::HasAnyLabel(vec![scalar])；
• array_has_all(col, [v1, v2, ...])→ 构造LabelListQuery::HasAllLabels(scalars)；
• array_has_any(col, [v1, v2, ...])→ 构造LabelListQuery::HasAnyLabel(scalars)。

执行侧（rust/lance-index/src/scalar/label_list.rs）的ScalarIndex::search分别调用：

LabelListQuery::HasAllLabels(labels) => { let values_results = self.search_values(labels, metrics); self.set_intersection(values_results, labels.len() == 1).await } LabelListQuery::HasAnyLabel(labels) => { let values_results = self.search_values(labels, metrics); self.set_union(values_results, labels.len() == 1).await }

其中search_values对每个标签构造一个SargableQuery::Equals(value)查询，交给底层BitmapIndex::search_exact取回该标签对应的NullableRowAddrSet；随后set_intersection/set_union对这些行地址集合做按位与（&=）或按位或（|=）运算（rust/lance-index/src/scalar/label_list.rs）。也就是说：

• array_has：单次位图查找，命中即返回；
• array_has_all：逐标签查位图 → 集合取交集 → 剩余的行就是"包含全部指定标签"的行；
• array_has_any：逐标签查位图 → 集合取并集 → 累计的行就是"包含任意指定标签"的行。

最终结果包装为SearchResult::Exact(row_ids)返回。值得注意的是，该插件明确声明provides_exact_answer() -> true（rust/lance-index/src/scalar/label_list.rs），因此查询计划会以精确过滤（prefilter）方式执行，不需要回表逐行复核。

查询解析的边界情况

LabelListQueryParser对以下情况会拒绝使用索引并回退到扫描（源码中直接返回None）：

• array_has/array_has_all/array_has_any之外的其他表达式（BETWEEN、IN、IS NULL、普通比较等，见visit_between、visit_comparison等方法的空实现）；
• 第二个参数（needle）不是标量或列表字面量；
• 空列表参数array_has_all(col, [])/array_has_any(col, [])；
• array_has(col, NULL)：DataFusion 中该表达式不匹配任何行，而位图索引会把包含 NULL 元素的行也算命中，为避免语义偏差，代码注释明确"回退以匹配 DataFusion 行为"（rust/lance-index/src/scalar/expression.rs）。

NULL 语义：list_nulls 位图的由来

多值列表列中 NULL 出现在两个层次：元素级 NULL（如["foo", NULL]）和列表级 NULL（整个列表为NULL）。Label List Index 对二者做了严格区分，这也是它和裸 BITMAP 索引的关键差异。

在训练（构建）阶段，索引构建器需要把列表列"摊平"成单值流再喂给底层位图构建逻辑（unnest_chunks/unnest_batch，见 rust/lance-index/src/scalar/label_list.rs）。但unnest会直接丢弃列表级 NULL（NULL 列表没有元素可展开），如果直接丢掉这些信息，array_has_any(col, ['foo'])的精确语义就无从谈起。为此，训练流程先用track_list_nulls包装输入流，在 unnest 之前记录下所有"列表本身为 NULL"的行地址（rust/lance-index/src/scalar/label_list.rs），得到list_nulls集合。

查询时（rust/lance-index/src/scalar/label_list.rs），位图交集/并集的结果会与list_nulls合并：

let row_ids = if self.list_nulls.as_ref().is_empty() { row_ids } else { let mut nulls = row_ids.null_rows().clone(); nulls |= self.list_nulls.as_ref(); row_ids.with_nulls(nulls) };

这背后的语义约定是：NULL 元素一律不算匹配。LabelListSubIndex::search_exact中还有一段重要注释（rust/lance-index/src/scalar/label_list.rs）：Label List 语义把 NULL 元素视为不匹配，因此array_has_any/array_has_all在列表本身非 NULL 时只应保留 TRUE/FALSE 结果，需要清除元素级 NULL 传播，即调用row_ids.with_nulls(RowAddrTreeMap::new())。

这些细节都有对应的 Python 测试用例严格验证（python/python/tests/test_scalar_index.py）：

• test_label_list_index_array_contains：含 NULL 元素时索引结果与非索引执行结果一致；array_contains(labels, NULL)不使用索引（ScalarIndexQuery不出现）。
• test_label_list_index_empty_list_filters：空列表参数不 panic，且与索引前结果一致。
• test_label_list_index_null_element_match：NULL 元素不算匹配，NOT array_has_*的结果同样精确。
• test_label_list_index_null_list_match：列表级 NULL 行不会因位图查询被误命中。

在 Python 中创建与使用

创建 Label List Index 走通用的标量索引 APIcreate_scalar_index。以 python/python/tests/test_scalar_index.py 中的最小示例为模板：

import pyarrow as pa import lance tags = pa.array(["tag1", "tag2", "tag3", "tag4", "tag5", "tag6", "tag7"]) tag_list = pa.ListArray.from_arrays([0, 2, 4], tags) tbl = pa.Table.from_arrays([tag_list], names=["tags"]) dataset = lance.write_dataset(tbl, "dataset") dataset.create_scalar_index("tags", index_type="LABEL_LIST") indices = dataset.describe_indices() assert len(indices) == 1 assert indices[0].index_type == "LabelList"

关键点说明：

• index_type必须传"LABEL_LIST"（大小写不敏感，内部注册名为LabelList，见 rust/lance-index/src/scalar/label_list.rs 的name()实现）；
• 被索引列必须为List/LargeList类型，元素类型非嵌套；否则训练阶段会直接报错LabelList index can only be created on List or LargeList type columns或LabelList index item type must be non-nested（rust/lance-index/src/scalar/label_list.rs 的validate_label_list_data_type，配套的test_rejects_nested_item_type测试在 rust/lance-index/src/scalar/label_list.rs）；
• 该 API 属于实验性接口，具体参数签名见 python/python/lance/dataset.py 的 docstring。

建好索引后，直接使用标准过滤表达式即可自动走索引，例如：

# array_has / array_contains：单标签命中 result = dataset.to_table(filter="array_contains(labels, 'foo')") # array_has_all：必须包含全部 result = dataset.to_table(filter="array_has_all(labels, ['ai', 'database'])") # array_has_any：包含任意一个即可 result = dataset.to_table(filter="array_has_any(genres, ['comedy', 'drama'])")

验证查询是否真的命中了索引，可以用执行计划确认其中出现ScalarIndexQuery：

explain = dataset.scanner(filter="array_contains(labels, 'foo')").explain_plan() assert "ScalarIndexQuery" in explain

参考 python/python/tests/test_scalar_index.py。仓库还提供了针对该过滤器的基准测试（python/python/benchmarks/test_search.py），以array_has_any(genres, ['comedy'])作为 prefilter 场景，说明这正是官方关注的核心性能路径。

构建与维护：训练、增量更新、重映射与分布式合并

除了查询，Label List Index 的构建和维护在源码中同样有清晰实现。

训练（train_index）：LabelListIndexPlugin作为BasicTrainer，在 rust/lance-index/src/scalar/label_list.rs 中实现。流程为：校验列类型 → 用track_list_nulls收集列表级 NULL →unnest_chunks摊平列表 →BitmapIndexPlugin::build_bitmap_index_state构建HashMap<ScalarValue, RowAddrTreeMap>状态 → 连同list_nulls一起写入bitmap_page_lookup.lance。训练数据要求携带行 ID（TrainingCriteria::new(TrainingOrdering::None).with_row_id()）。

增量更新（update）：ScalarIndex::update（rust/lance-index/src/scalar/label_list.rs）对新增数据重复上述"跟踪 NULL + unnest + 构建位图状态"的过程，然后与既有状态合并（位图做并集、list_nulls做并集），再写出一份新版本索引。update_criteria声明为"仅新数据"（UpdateCriteria::only_new_data），且需要行 ID。

行地址重映射（remap）：在数据整理（compaction / rewrite）导致行地址变化时，remap（rust/lance-index/src/scalar/label_list.rs）会基于RowAddrRemap映射重写底层位图状态和list_nulls，生成新的索引文件。

分布式分段合并（merge_label_list_indices）：针对分布式向量/标量构建场景，每个分片会先训练出覆盖局部 fragment 的"分段索引"，最后由merge_label_list_indices（rust/lance-index/src/scalar/label_list.rs）合并。由于分段覆盖的行互不相交，合并本质上是"底层位图状态的并集 +list_nulls的并集"，不需要重新扫描源数据；若提供old_data_filter，还会先从各分段中剔除退役 fragment 的行，再执行合并。合并过程通过IndexBuildProgress上报两个阶段的进度。

缓存编解码：为了减少重复加载，LabelListIndexState实现了CacheCodecImpl（rust/lance-index/src/scalar/label_list.rs），其线格式为"前导的list_nulls（RowAddrTreeMap 可移植编码）+ 自定界的嵌套BitmapIndexState"，配套测试test_label_list_state_codec_roundtrip与test_label_list_nested_lookup_is_zero_copy（rust/lance-index/src/scalar/label_list.rs）分别验证序列化往返一致性和嵌套位图 lookup 段的零拷贝解码（确保前导数据块不会把嵌套 IPC 段挤出 64 字节对齐边界）。

与 BITMAP 等其他标量索引的定位差异

Label List Index 底层就是 BITMAP 索引（两者共用bitmap_page_lookup.lance文件），但面向的查询形态不同：

• BITMAP（见 docs/src/format/index/scalar/bitmap.md）加速单值列的=、BETWEEN、IN、IS NULL等谓词，适用于低基数单值列；
• LABEL_LIST面向List<T>多值列，加速array_has/array_contains、array_has_all、array_has_any集合谓词，并在 BITMAP 之上额外解决了"列表摊平后的 NULL 语义"这一专有问题。

在 python/python/lance/dataset.py 列出的全部标量索引类型中（BTREE、BITMAP、LABEL_LIST、NGRAM、ZONEMAP、INVERTED/FTS、BLOOMFILTER），LABEL_LIST 是唯一一个直接针对列表列集合查询的类型。从实现看，LabelListIndex结构就是"一个BitmapIndex+ 一个list_nulls行集合"（rust/lance-index/src/scalar/label_list.rs），可谓"位图索引 + 空值语义补丁"的经典组合。

小结

Label List Index 是 Lance 标量索引家族中专门服务多值列表列的一员：它把List<T>列摊平后为每个唯一标签维护行位图，通过位图查找 + 交/并运算精确加速array_has/array_contains、array_has_all、array_has_any三类集合查询；存储上仅需一个固定命名的bitmap_page_lookup.lance文件（含keys与bitmaps两列），元数据消息LabelListIndexDetails当前为空、索引版本为 1。其实现对 NULL 语义（NULL 元素不匹配、列表级 NULL 单独记录为list_nulls）做了细致的处理，并提供训练、增量更新、行地址重映射、分布式分段合并与缓存编解码等完整生命周期能力。若你的数据集中存在"每行多个标签、标签基数不大"的列，且过滤以集合成员判断为主，那么为该列创建LABEL_LIST索引是一个直接且精确的加速手段。

【免费下载链接】lanceOpen Lakehouse Format for Multimodal AI. Convert from Parquet in 2 lines of code for 100x faster random access, vector index, and data versioning. Compatible with Pandas, DuckDB, Polars, Pyarrow, and PyTorch with more integrations coming..项目地址: https://gitcode.com/GitHub_Trending/la/lance