Lance 索引体系深度解析标量索引、向量索引与系统索引的存储与查询原理【免费下载链接】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本篇指南以 Lance 官方格式规范文档 Indices in Lance 为骨架结合仓库内 table.proto 的 protobuf 定义、各类索引子文档以及 Rust 实现源码系统讲解 Lance 的索引架构索引如何作为独立于数据文件之外的可选结构分层存在索引段index segment如何创建、加载、更新与失效以及查询引擎在删除行、原地更新、overlay 文件与压缩compaction等复杂场景下如何保证索引结果的正确性。读完本文你将理解 Lance 索引格式的完整设计掌握索引生命周期的事务化流程并能据此判断索引查询中各类正确性规则覆盖位图、排除集、稳定行 ID 等的适用场景。一、索引的本质定位独立于表布局的可选结构Lance 将索引视为叠加在表行标识row identifier之上、彼此独立的冗余数据结构。这一设计决策意味着文件格式本身不内建任何搜索结构索引格式可以独立于表布局演进。数据集可以在完全不加载任何索引的情况下被打开和读取——索引只在查询能够受益时才被按需加载。从索引覆盖的语义看Lance 的索引段之间不需要覆盖全部 fragment索引不必完全处于最新状态。当索引未覆盖某些 fragment 时查询引擎可以将查询拆分为走索引的子计划与不走索引的子计划再合并两路结果。二、三类索引概览Lance 支持三大类索引来加速数据访问类别作用典型结构查询输入/输出标量索引Scalar indices加速整数、时间戳、字符串等标量类型的查询Zone Map主跳过结构、B-tree、位图索引、全文检索FTS索引接收等值、范围、集合成员或 token 匹配谓词返回匹配的行标识向量索引Vector indices面向高维 embedding 的近似最近邻ANN搜索IVF 系列布局、HNSW 图接收查询向量返回行标识与距离分数系统索引System indices支撑表内部维护与行标识解析Fragment Reuse Index压缩后的高效重映射不被终端用户直接查询其中标量索引进一步分为主跳过结构如 Zone Mapzonemap.md与次级结构如 B-tree、bitmap、全文检索。主跳过结构在数据写入/落盘时生成用于快速剪枝次级结构则是独立构建、可被查询引擎检索的辅助结构。三、四项核心设计原则Lance 索引格式建立在以下四项设计选择之上按需加载Loaded on demand打开数据集不加载任何索引仅当查询需要时按需加载从而最小化内存占用、加速数据集打开。渐进式加载Loaded progressively查询时只加载索引的必要部分。例如查询 B-tree 时先加载一个小型页表page table确定本次查询需要哪些索引页再只加载这些页执行检索。这样冷索引查询的代价被摊薄——每次查询只需加载索引的一小部分。可合并为比 fragment 更大的单元Coalesced beyond fragments索引文件远小于数据文件因此将索引段合并以覆盖多个 fragment 是高效的可减少查询时需要打开的索引文件数量与需要查询的索引结构数量。不可变Immutable索引文件一旦写入便不可修改只能通过创建新文件来变更因此可以安全地在内存或磁盘中缓存无需担心一致性问题。四、基本概念索引、索引段与 fragment 覆盖一个 Lance 索引定义在数据集的一个或多个列上通过名称唯一标识。索引由多个**索引段index segment**组成每个段由全局唯一的 UUID 标识是覆盖部分数据子集的独立、自包含的索引。每个索引段覆盖数据集中互不相交的 fragment 子集段必须覆盖其所含 fragment 的全部行唯一例外是若某 fragment 在索引创建时已带有删除标记索引段可以不包含这些被删除的行。段覆盖的 fragment 记录在fragment_bitmap字段中该字段在 protos/table.proto 中定义为 32 位 Roaring bitmap 序列化结果并同时保存在索引元数据中——这是为了防止旧版本被删除后无法从数据集侧反查覆盖关系。以官方文档中的示例数据集对应示意图 starter-example.drawio.svg为例数据集包含 id 为 0、1、2 的三个 fragment其中 fragment 1 有 10 行被删除记录于删除文件。索引id_idx有两个段一个覆盖 fragment 0另一个覆盖 fragment 1fragment 2 未被覆盖。使用该索引的查询需要同时查询两个段再直接扫描 fragment 2查询覆盖 fragment 1 的段时还需过滤掉那 10 行被删除的行。索引vec_idx只有单个段覆盖全部三个 fragment。由于全覆盖使用该索引的查询无需直接扫描任何 fragment但仍需过滤 fragment 1 中的 10 个删除行。五、索引存储_indices/{UUID}目录每个索引的内容存储在数据集基路径base path下的_indices/{UUID}目录中该位置被称为索引目录。目录内的实际内容因索引类型而异可以是索引实现自定义的任意文件但通常由包含索引数据结构的 Lance 文件组成从而复用现有 Lance 文件格式的读写代码。例如B-tree 索引由page_lookup.lanceBTree 结构映射值范围到页号和page_data.lance叶子层的扁平子索引保存排序值与行 ID两个文件组成见 btree.mdZone Map 索引则只包含单个zonemap.lance文件FTS 索引由tokens.lance、docs.lance、invert.lance、metadata.lance等多个文件组成且支持多分区文件如part_0_tokens.lance详见 fts.md。向量索引则固定由index.idx搜索结构文件与auxiliary.idx量化向量存储文件两个 Lance 文件组成详见 vector/index.md。此外IndexMetadata中的IndexFile消息table.proto记录了索引段内每个文件相对索引目录的路径与字节大小如index.idx、auxiliary.idx使引擎打开索引时可跳过 HEAD 请求、直接报告索引大小。六、创建与更新索引段完整的事务化流程索引段通过事务化流程创建和更新分为三步步骤 1构建索引数据。从待索引的 fragment 中读取相关列数据构造索引数据结构写入新建的_indices/{UUID}目录{UUID}为新生成的唯一标识。步骤 2准备元数据。创建IndexMetadata消息包含以下关键字段完整 protobuf 定义见 table.proto字段类型含义uuidUUID新建索引段的全局唯一标识namestring索引名若追加到既有索引必须与既有段同名同一数据集版本内唯一fieldsrepeated int32索引依赖的列被搜索的 keyed 列在前紧随其后的是covering_fields中声明的仅携带列fields[0]永远是 keyed 列covering_fieldsrepeated int32fields的尾部子集索引携带其值但不以其为键。查询若只投影这些列可免于回表take直接由索引回答。不携带额外列时为空。注意声明本身不代表可服务——见下文服务携带列fragment_bitmapbytes该段覆盖的 fragment ID 集合index_detailsgoogle.protobuf.Any索引类型特有的配置与参数dataset_versionuint64构建索引所基于的数据集版本index_versionoptional int32该索引类型的最小兼容 Lance 版本created_atoptional uint64索引创建时间UTC 毫秒时间戳向后兼容旧索引可为空base_idoptional uint32数据文件基路径索引用于跨数据集引用的场景filesrepeated IndexFile索引段内文件列表及其大小其中fields与covering_fields的关系有一个刻意设计携带列同时出现在fields中。这样所有把fields当作索引依赖集消费的逻辑staleness 判断、提交冲突检测、schema 演进守卫都会自然覆盖携带列无需修改也不会遗漏。步骤 3提交事务。写入包含新索引段的新 manifest将其登记到IndexSection中。该操作与数据写入使用同一原子事务机制。原地更新列的特殊规则当不删除行、直接原地更新某列时引擎必须从所有fields包含该列无论 keyed 还是仅携带的索引段的fragment_bitmap中移除受影响的 fragment ID。这将这些 fragment 标记为需要重新索引而无需使整个段失效并防止从索引读到无效数据。七、索引兼容性校验与携带列服务规则兼容性检查。使用索引段前引擎必须验证自身支持该段检查索引类型index_details是 protobufAny消息其 type URL 标识索引类型如 B-tree、IVF、HNSW。引擎无法识别该类型时应跳过此索引段。Lance API 以 type URL 作为索引类型标识符用户提供的简单字符串如btree会被转换为/lance.table.BTreeIndexDetailstype URL 的比较不区分大小写。检查版本IndexMetadata.version字段标识索引段的格式版本。引擎不支持该版本时跳过此段使索引格式可以随时间演进并保持向后兼容。引擎无法使用某索引段时应回退为直接扫描该段本应覆盖的 fragment。服务携带列Serving carried columns的权威规则covering_fields只记录索引段声明携带的列并不代表段的存储中确有这些值——段的存储 schema 才是权威。在通过携带列回答查询之前引擎必须确认该列存在于其打开的存储中否则回退为对基表的 take。声明了存储并不持有的列是合法状态而非损坏维护操作在重建过程中无法搬运载荷时允许撤回载荷而保留声明。需要特别指出的是当前状态文档原注目前尚无索引构建器真正写入携带值因此当前所有声明都超前于存储。读取covering_fields的引擎必须仅将其视为声明在自行验证存储之前一律从基表服务各列。该状态是过渡性的而存储 schema 权威这条规则不是。八、加载索引的过程与优化加载索引分为三步从 manifest 的index_section字段取得索引段区的偏移量从 manifest 文件读取索引段区——一个IndexSectionprotobuf 消息table.proto内含描述每个索引段的IndexMetadata消息列表从数据集目录下的_indices/{UUID}读取索引文件{UUID}即索引段 UUID。优化技巧当 manifest 文件较小时可以急切地读取并缓存索引段区避免加载索引时额外的文件读取。从源码实现看这一流程由 rust/lance/src/dataset/index.rs 等模块承载索引段区被读取后按需从对象存储拉取_indices/{UUID}下的实际文件与按需加载、渐进加载的设计原则相吻合。九、处理删除行与失效行四种必须过滤的情形由于索引段不可变它们可能包含已被删除或更新的行的引用查询执行时必须过滤。对应示意图 indices-fragment handling.drawio.svg有四种情况fragment 有部分删除行行地址在删除文件中被标记应使用删除文件中的行地址过滤索引结果。fragment 被整体删除可通过检查fragment bitmap 中的 fragment ID 是否已从数据集消失来检测。该 fragment 的所有行地址都应被过滤。fragment 有索引列被原地更新仅检查元数据无法检测此情况。为防止读到无效数据引擎应过滤掉不在索引当前fragment_bitmap中的任何行地址。注意该列不必是索引的 keyed 列——fields中的每一列都算数包括covering_fields中仅携带的列携带列可以在 keyed 列未动时被更新若段仍覆盖该 fragment就会用过期的携带值回答查询。fragment 有 overlay 文件中的更新值检测方式是检查索引fragment_bitmap中是否有 fragment 存在 overlay 文件。对每个committed_version大于索引段dataset_version的 overlay其携带的更新值未反映在索引中所覆盖的行必须从索引结果中排除。被排除的行要在扁平路径flat path上按当前overlaid值重新求值——只排除不重估会静默丢失在新值下本该匹配的行。排除是字段感知的只有覆盖索引fieldskeyed 或仅携带中某列的 overlay 才相关仅限定 keyed 列会让携带列被 overlay 更新后仍被段覆盖从而服务过期值。可以只排除受影响的行也可以排除整个 fragment——后者更简单更安全但会重估更多行。完整的排除集、重估与正确性不变量见 Data Overlay Files 的 Index Integration 一节。overlay 的committed_version是生效版本而非读取版本这一点是正确性关键索引记录的是构建时的dataset_version只有当committed_version index.dataset_version时才需排除。写入总是通过新增 overlay 改变单元而新增 overlay 的提交版本必然大于任何既有索引的dataset_version因此排除总是充分的。十、压缩与行地址重映射当 fragment 被压缩compaction时其中行的行地址会改变导致引用这些 fragment 的索引段不再指向有效行地址。有三种处理方式对应示意图 indices-compaction.drawio.svg什么都不做让索引段不再覆盖这些 fragment。简单且有效但压缩会立即让索引过期是查询性能最差的选项。立即重写索引段并重映射行地址。保证索引始终最新但压缩期间会产生显著写放大。创建 Fragment Reuse IndexFRI将旧行地址映射到新行地址读者在读取索引段时于内存中重映射。查询执行时增加少量 IO 与计算开销但避免了压缩期间的写放大。FRI 是系统索引的典型代表当用户推迟压缩中的索引重映射时创建 FRI每次执行压缩累积一个新的reuse version。只要所有标量与向量索引都创建于某个 reuse version 之后该版本即可被裁剪trim。FRI 的存在还会改变并发操作之间的冲突检测语义并给每次索引加载增加重映射成本索引缓存后不影响查询性能。用户应定期安排进程裁剪过期 reuse version控制 FRI 体积详见 frag_reuse.md。十一、稳定行 IDStable Row ID索引可以选择使用稳定行 ID 替代行地址。稳定行 ID 是逻辑标识符即使行在压缩中被移动也保持不变。收益压缩后无需重映射更新只在索引某个fields列keyed 列或covering_fields中任意列的数据变化时才使索引失效。权衡查询时需要额外的查找将稳定行 ID 翻译为物理行地址。该特性目前处于实验阶段性能评估仍在进行中以确定该权衡何时值得。十二、各类索引的加速查询能力速查从子文档可以归纳出各类标量索引的查询语义查询类型的定义与示例可分别在对应文档中查看索引类型等值范围IN 集合IS NULL结果精确性Zone Map含 min ≤ v ≤ max 的 zone区间重叠的 zone可能含任意值的 zonenull_count 0 的 zone前三种 AtMost可能误报IsNull 精确B-treeBTree 定位页 子索引内查找遍历重叠页多次查找并合并所有 null_count 0 的页全部精确Bitmap直接返回该值位图范围内所有值位图求并指定值位图求并预计算 null 位图精确FTScontains_tokens / match / phrase / boolean / multi_match / boost———AtMostZone Map 是不精确过滤器能确定性地排除 zone但可能包含需要复查的误报同时因其维护空值位图IS NULL查询可返回精确结果。B-tree 采用两级结构——上层page_lookup.lance缓存于内存叶子page_data.lance通过子索引检索文档给出的量级参考是10 亿个值只需 256K 个 4K 大小的叶子BTree 元数据仅需几 MiB 内存即可把任何检索缩小到 4K 个值。FTS 索引则支持分词器、停用词、词干化等完整配置多分区布局下每次查询需扫描所有分区的 token 字典因此更少更大的分区通常查询性能更好LANCE_FTS_TARGET_SIZE环境变量控制合并分区大小见 fts.md 的 Training Process 一节。结语Lance 的索引体系通过独立分层 不可变段 事务化元数据的组合在保持文件格式简洁的同时实现了可演进、可扩展的查询加速能力。理解IndexMetadata的字段语义、fragment_bitmap的覆盖规则以及删除行/overlay/压缩场景下的四类过滤规则是正确实现或深度使用 Lance 索引的关键。若需进一步深入可继续阅读 标量索引总览、向量索引存储布局 V3、Fragment Reuse Index以及在 protos/table.proto 中查看IndexMetadata的完整字段注释。【免费下载链接】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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考