Lance 的写入链路同时涉及文件布局、版本提交、删除标记、索引维护和 compaction。和传统数据库不同，Lance 不直接在原文件上修改数据，而是通过新增文件和更新元数据来产生新的表版本。

本文讨论几个实现问题：

• delete、update、merge insert 如何落到文件和元数据上。
• Deletion Vector 在 Lance 写入链路中的作用。
• Deletion Vector 如何参与写入冲突检测。
• Lance 和 Apache Paimon 在 Deletion Vector 设计上的差异。
• Compaction 如何挑选 fragment，以及为什么需要 index remap。
• Stable Row ID 如何降低 compaction 后的索引维护成本。

基本判断

Lance 写入的基本形式是：写入新数据文件或 deletion file，再通过 transaction 和 manifest 提交新版本。

Delete:
  不立刻重写 data file
  -> 记录 fragment 内被删除的 row offset
  -> 读时过滤 deletion vector

Update / Merge:
  写出更新后的新 rows 或新 columns
  -> 对旧 rows 写 deletion vector
  -> 提交 Operation::Update

Compaction:
  读取旧 fragments 的 live rows
  -> 写成新的 fragments
  -> 旧 row address 可能失效
  -> 索引需要 remap 或重建

Stable Row ID:
  让索引指向稳定逻辑行 ID
  -> compaction 后只需要维护 row_id -> row_address 映射
  -> 降低索引 remap 成本

Lance 的持久化元数据里通常叫 DeletionFile，内部处理时使用 DeletionVector：

DeletionVector:
  内存中的删除集合语义

DeletionFile:
  DeletionVector 在表目录下的持久化文件引用

写入链路的统一模型

从 LanceDB API 看，用户调用的是：

table.add(...)
table.delete("id = 42")
table.update(where="id = 42", values={"text": "new"})
table.merge_insert("id").when_matched_update_all().when_not_matched_insert_all()
table.optimize.compact_files()

但 Lance 底层看到的不是“修改一张表里的几行”，而是一次 dataset 状态转换：

读取当前 manifest
  -> 执行 scan / join / filter
  -> 写新的 data files / deletion files / index files
  -> 构造 Operation
  -> 写 transaction
  -> 提交新的 manifest version

一个版本的 manifest 描述当前表的完整状态：

Manifest version N
  schema
  fragments
  indices
  version metadata

Fragment 1
  data files
  deletion file
  row id metadata

transaction 描述本次提交对表状态的变更。因此，创建索引、compact 文件、更新配置都可能产生新版本，即使行数没有变化。

Delete：用 Deletion Vector 标记不可见行

Delete 不立刻改写 data file，而是把命中的行标记为 deleted。

简化链路如下：

delete where id = 42
  -> scan + predicate 找到命中 rows
  -> 捕获 row address
  -> 按 fragment 聚合成 local row offsets
  -> 更新 fragment.deletion_file
  -> Operation::Delete
  -> CommitBuilder.with_affected_rows(...)
  -> 提交新 manifest

假设 Fragment 7 有 1000 行：

Fragment 7
  data file: 1000 physical rows
  deletion file: {3, 19, 42}

读取 Fragment 7 时:
  offset 3、19、42 被过滤
  其他行仍然可见

源码上，Fragment 元数据中有一个可选的 deletion_file 字段，语义是“这个 fragment 内被删除的 local row offsets”。DeletionFileType 目前有两类：

Array:
  适合较稀疏的删除集合

Bitmap:
  适合较密集的删除集合

源码入口：

rust/lance-table/src/format/fragment.rs
  DeletionFile
  DeletionFileType
  Fragment.deletion_file

rust/lance-table/src/io/deletion.rs
  write_deletion_file
  read_deletion_file

rust/lance/src/dataset/write/delete.rs
  apply_deletions
  DeleteBuilder

这种设计的作用是：

• 删除少量行时，不需要重写整个 fragment。
• 对象存储上也不需要改写旧 data file。
• 删除集合可以独立演进，manifest 只需要指向新的 deletion file。
• 后续 compaction 可以再把删除物化掉。

对应的成本是：读路径需要加载 deletion vector，并在扫描时跳过 tombstoned rows。

Update：写新行，再删除旧行

Update 的常见实现是：写入更新后的新数据，再把旧行 tombstone 掉。

普通 update 的主链路接近 RewriteRows：

update set text = 'new' where id = 42
  -> scan where 条件命中的 rows，并带上 row id / row address
  -> 对 batch 应用更新表达式
  -> write_fragments_internal 写出新的 fragments
  -> 对旧 row address 应用 deletion vector
  -> Operation::Update { update_mode: RewriteRows }
  -> CommitBuilder.with_affected_rows(...)

以一张 10 列表只更新 1 列为例：

更新前:
  Fragment 1
    row offset 42 = (c1, c2, c3, ..., c10)

UPDATE SET c3 = c3_new WHERE id = 42

更新后:
  Fragment 1
    deletion file 标记 offset 42 deleted

  Fragment 9
    新写入 row = (c1, c2, c3_new, ..., c10)

RewriteRows 不是把整个旧 fragment 都重写，而是把命中的 rows 作为新 rows 写出去。对于每一条被更新的 row，它会写出完整行。

源码入口：

rust/lance/src/dataset/write/update.rs
  UpdateJob::execute_impl
  scanner.with_row_id()
  write_fragments_internal(...)
  apply_deletions(...)
  Operation::Update { update_mode: RewriteRows }

Lance 还有 RewriteColumns 模式，主要出现在部分 schema 的 merge/update 场景中。它面向“大量行、少量列”的更新，但会增加 fragment、列文件、索引覆盖范围和冲突检测的维护成本。

Merge Insert：Upsert 语义，不等于主键约束

LanceDB 的 merge_insert 可用于 upsert：

(
    table.merge_insert("id")
    .when_matched_update_all()
    .when_not_matched_insert_all()
    .execute(source)
)

这里的 id 是 source 和 target 做匹配的 join key，不是数据库里强约束的 primary key。

简化流程是：

source 与 target 按 key join
  matched:
    更新 target rows

  not matched:
    插入 source rows

  not matched by source:
    keep 或 delete

在 full schema 路径上，merge insert 的处理方式接近普通 update：

matched rows:
  写出更新后的完整 rows 到新 fragments
  对旧 target rows 写 deletion vector

not matched rows:
  作为新 rows 写入新 fragments

commit:
  Operation::Update { update_mode: RewriteRows }

在 partial schema 路径上，它会走 RewriteColumns：

source 只包含部分列
  -> update_fragments(...)
  -> Operation::Update { update_mode: RewriteColumns, fields_modified }

源码入口：

rust/lance/src/dataset/write/merge_insert.rs
  MergeInsertBuilder
  update_fragments
  Operation::Update { update_mode: RewriteRows | RewriteColumns }

Deletion Vector 与写入冲突检测

Deletion Vector 不只是读时过滤被删除行，它还让 Lance 能把一部分写入冲突从“fragment 级冲突”降低到“row 级冲突”。

先看没有 Deletion Vector / affected rows 时的问题：

T1:
  delete row (Fragment 1, offset 10)

T2:
  delete row (Fragment 1, offset 20)

如果只从 fragment 级别看，两个事务都修改了 Fragment 1，于是很容易被判定为冲突。但实际上它们删除的是不同的行，可以合并：

T1 deletion vector: {10}
T2 deletion vector: {20}

rebase 后:
  Fragment 1 deletion vector: {10, 20}

Lance 在 delete/update 提交时会把命中的 row address 传给 commit 层：

CommitBuilder.with_affected_rows(RowAddrTreeMap)

这让冲突检测可以判断：

两个并发事务是否真的修改了同一批 rows？

如果只是修改同一个 fragment 的不同 rows，而且另一个事务没有改 data files，只是改 deletion file，那么当前事务有机会 rebase。也就是说，它可以基于新的 fragment deletion file 再写出合并后的 deletion vector。

典型情况：

可 rebase:
  T1 delete F1.offset 10
  T2 delete F1.offset 20
  -> affected_rows 不重叠
  -> 合并 deletion vector

不可 rebase:
  T1 update F1.offset 10
  T2 delete F1.offset 10
  -> affected_rows 重叠
  -> 语义冲突

不可简单 rebase:
  T1 delete F1.offset 10
  T2 compaction/rewrite F1
  -> fragment 的 data files 被重写
  -> row address / fragment 状态发生大范围变化

源码入口：

rust/lance/src/dataset/write/commit.rs
  CommitBuilder.with_affected_rows

rust/lance/src/io/commit/conflict_resolver.rs
  TransactionRebase
  check_delete_txn
  check_update_txn

因此，Deletion Vector 并不会消除所有写入冲突。它提供的是 row-level affected rows 的表达能力，使 Lance 可以避免一部分 fragment-level false conflict。

对于包含大量样本的数据集，更新、删除、merge 往往只影响少量行。如果并发控制只能做到 fragment 粒度，就会把很多不相交的行级修改判定为冲突。

Lance 与 Paimon 的 Deletion Vector 差异

Lance 和 Apache Paimon 都有 Deletion Vector，但它们要解决的问题并不完全一样。

维度	Lance	Apache Paimon
主要数据模型	面向 Arrow / Lance fragment 的列式数据集	面向湖仓表、主键表、LSM、bucket、snapshot
DV 粒度	fragment 内 local row offset	data file 内 row position
典型用途	delete、update、merge、冲突检测、读时过滤、compaction materialize deletions	主键表 MOW 模式下避免读时 merge，写入时生成 DV 文件
与更新的关系	update 常见路径是写新 rows + tombstone 旧 rows	主键表依赖 LSM 查找旧数据并生成 DV
与列级演进的关系	Lance 有 fragment 多 data files 和 row id metadata，更新后仍围绕 fragment/row address 维护	Paimon Data Evolution 采用按列 overlay，同 first row id 的文件读时合并
与冲突检测的关系	affected_rows 可以让并发 delete/update 做 row-level rebase	更偏向主键表写入链路和文件级读过滤

Paimon 的 DV 文档语义很清晰：它记录一个 data file 中被删除的 row positions，读文件时过滤这些行。Paimon 的 Merge On Write 模式依赖 LSM，可以在写入阶段查询主键，生成对应 data file 的 deletion vector，从而让读取时不用再做完整 merge。

Paimon 的 Data Evolution 表采用另一套路线：只把更新列写到新文件，原始数据文件保持不变，读取时把相同 first row id 的多组文件合并成完整行。因此 Paimon Data Evolution 明确要求关闭 deletion vectors，并且暂不支持普通 Delete / Update statement。

下面是 Data Evolution 与 DV 组合时的一个简化例子：

base file:
  firstRowId = 100
  columns: id, a, b, c

update file:
  firstRowId = 100
  columns: b_new

读时:
  base file + update file
  -> 按 firstRowId 对齐
  -> 得到完整行

如果再引入 file-level deletion vector：

删除 base file 的某一行:
  a / c 也被隐藏
  但 b_new 的 overlay 文件如何处理？

删除 update file 的某一行:
  b_new 不可见
  但 base file 的旧 b 是否应该恢复？

如果同时支持这两套机制，读写路径需要同时处理“行删除”和“列 overlay 合并”。Paimon 将 Data Evolution 和 Deletion Vector 分开，避免这两套语义相互影响。

Lance 的典型更新路线是：

新 rows / 新 columns 写入新 fragment 或新 data files
旧 rows 通过 deletion vector tombstone
manifest 统一描述当前版本的 fragment 状态

因此，Lance 的 Deletion Vector 不只是读过滤工具，也参与并发写入的 rebase 和冲突判断。

Compaction：什么时候挑选 fragment

Deletion Vector 降低了 delete/update 的写放大，但会留下两个问题：

• 小批 append 可能制造大量小 fragments。
• 多次 delete/update 后，fragment 中 deleted rows 比例可能很高。

Compaction 用于处理这些布局退化问题。

Lance 的 compaction 不是简单按文件 size 挑选，而是主要看 fragment 的行数和删除比例：

if deletion_percentage > materialize_deletions_threshold:
  选中这个 fragment
  目的：把 deletion vector 物化掉，只写 live rows

else if physical_rows < target_rows_per_fragment:
  选中这个 fragment
  目的：和相邻的小 fragments 合并成更大的 fragment

else:
  不参与本轮 compaction

默认配置中：

target_rows_per_fragment = 1024 * 1024
materialize_deletions_threshold = 0.1

对应行为是：

• 删除比例超过 10% 的 fragment，即使它自己一个 fragment，也值得重写。
• 行数低于目标值的小 fragment，会尝试和相邻候选 fragment 合并。
• compaction 按 row count 规划，而不是直接按文件字节数挑选。

源码入口：

rust/lance/src/dataset/optimize.rs
  CompactionOptions
  plan_compaction
  CompactionCandidacy::CompactItself
  CompactionCandidacy::CompactWithNeighbors

这里有一个索引约束：compaction 不会把“被某个索引覆盖的 fragment”和“没有被这个索引覆盖的 fragment”混在同一个 rewrite group 里。

原因是 Lance 的 index metadata 里有 fragment_bitmap，它描述这个索引覆盖哪些 fragments。如果一个 rewrite group 里混合了 indexed 和 unindexed fragments，compact 之后的新 fragment 无法被清晰归类为 indexed 或 unindexed。

所以 compaction planner 会按照 index coverage 把候选 fragment 分 bin：

F1 indexed by vector_index
F2 indexed by vector_index
F3 not indexed

允许:
  compact(F1, F2) -> F10

不允许:
  compact(F2, F3) -> F11

Compaction 为什么会牵引出索引 remap

Compaction 的本质是 rewrite：

old fragments:
  F1, F2

new fragments:
  F10

如果索引里记录的是 row address，compaction 后就需要维护索引中的地址。

Lance 的 row address 由 fragment id 和 row offset 组成：

row_address = (fragment_id, row_offset)

compaction 前：

F1.offset 0
F1.offset 1
F2.offset 0

compaction 后：

F10.offset 0
F10.offset 1
F10.offset 2

逻辑上仍是同一批 live rows，但物理地址变了。索引中保存的 row address 必须随之更新，否则索引会指向旧 fragment。

Lance 对 compaction 后的索引有几种处理方式：

1. 同步 remap index
   compaction 时生成 old row address -> new row address 映射
   重写受影响的 index files

2. defer_index_remap
   compaction 时不立即重写所有索引
   建立 fragment reuse index
   查询时或后续维护时再做 remap

3. stable row id
   索引不再直接依赖易变的 physical row address
   而是指向稳定 row id

在 transaction 应用 Operation::Rewrite 时，Lance 会处理两类元数据：

fragments:
  old fragments 从 manifest 移除
  new fragments 加入 manifest

indices:
  更新 fragment_bitmap
  必要时替换 index uuid 和 index files

源码入口：

rust/lance/src/dataset/transaction.rs
  Operation::Rewrite
  handle_rewrite_fragments
  recalculate_fragment_bitmap
  handle_rewrite_indices

rust/lance/src/dataset/optimize/remapping.rs
  fragment reuse index
  deferred index remap

不同索引的维护方式不同。是否能 remap，取决于索引内部是否保存了可以从 old row address 映射到 new row address 的明细。

可以按索引内部记录的内容区分：

较容易 remap:
  能逐条或逐 segment 映射到 row address 的索引

较难 remap:
  内部结构强依赖训练结果、聚类结果、posting layout 或 block layout 的索引

例如向量索引通常不仅仅是一个 key -> row address 映射。IVF 这类索引内部有聚类中心、partition、向量列表、row id 列表等结构。compaction 之后虽然向量值没变，但 row address 变了，索引内部的 row id/address payload 需要一致更新。如果索引格式没有提供廉价、局部、可靠的 remap 能力，就只能重写或借助 fragment reuse index 延后处理。

因此，compaction 的难点不只在重写 data files：

数据文件重写之后，索引仍然要能定位到同一批逻辑行。

Stable Row ID：把索引从物理地址中解耦

Stable Row ID 给每个逻辑行分配稳定 ID，使索引不再直接依赖会变化的 row address。

没有 stable row id 时：

row id ~= row address

索引命中:
  vector index -> row address -> 回表

compaction:
  row address 改变
  -> index payload 需要 remap

开启 stable row id 后：

row id = 稳定逻辑行 ID
row address = 当前物理位置

索引命中:
  vector index -> stable row id
  -> RowIdIndex 查 row id 当前对应的 row address
  -> 回表

compaction:
  stable row id 不变
  row address 改变
  -> 更新 row_id_meta / RowIdIndex
  -> 索引主体可以复用

可以画成这样：

                 without stable row id

Index payload ------------------> RowAddress(F1, 42)
                                      |
                                      | compaction 后失效
                                      v
                                  RowAddress(F10, 8)


                 with stable row id

Index payload ---> StableRowId(10086)
                         |
                         v
                   RowIdIndex(version N)
                         |
                         v
                   RowAddress(F10, 8)

RowIdIndex 的实际表示

RowIdIndex 不是用户手动创建的索引，也不是每一行存一条独立的 row_id -> row_address 记录。它是 stable row id 开启后，Lance 在读取需要时基于 fragment 元数据构建出来的版本级内存索引，并缓存在 metadata cache 中。

构建入口在：

rust/lance/src/dataset/rowids.rs
  get_row_id_index(dataset)
    -> 如果 manifest.uses_stable_row_ids()
    -> 从 metadata_cache 获取或构建 RowIdIndex

  load_row_id_index(dataset)
    -> 读取每个 fragment 的 row_id_meta
    -> 读取该 fragment 的 deletion vector
    -> 构造 FragmentRowIdIndex
    -> RowIdIndex::new(...)

每个 fragment 上保存的是 row_id_meta，它描述这个 fragment 中“物理行顺序对应的 stable row id 序列”：

Fragment 10
  row_id_meta:
    physical offset 0 -> stable row id 100
    physical offset 1 -> stable row id 101
    physical offset 2 -> stable row id 105
    physical offset 3 -> stable row id 106

  deletion vector:
    {1}

构建 RowIdIndex 时，会把 deletion vector 应用进去：

offset 0 live     -> 100 -> RowAddress(F10, 0)
offset 1 deleted  -> 跳过
offset 2 live     -> 105 -> RowAddress(F10, 2)
offset 3 live     -> 106 -> RowAddress(F10, 3)

源码里的核心结构是：

pub struct RowIdIndex(
    RangeInclusiveMap<u64, (U64Segment, U64Segment)>
);

可以把它理解成：

RowIdIndex
  key:
    这一段 row id 覆盖的范围

  value:
    row_id_segment:
      这一段实际存在的 row ids

    address_segment:
      与 row_id_segment 一一对齐的 physical row addresses

也就是说，RowIdIndex 的一个 chunk 不是一条映射，而是一段映射：

coverage range:
  100..=106

row_id_segment:
  [100, 105, 106]

address_segment:
  [RowAddress(F10, 0), RowAddress(F10, 2), RowAddress(F10, 3)]

查询 row_id = 105 时，流程是：

1. 用 105 到 RangeInclusiveMap 中找到覆盖它的 chunk
2. 在 row_id_segment 中找 105 的位置
3. 假设位置是 1
4. 从 address_segment 取第 1 个地址
5. 得到 RowAddress(F10, 2)

对应源码是：

rust/lance-table/src/rowids/index.rs
  RowIdIndex::get(row_id)
    -> self.0.get(&row_id)
    -> row_id_segment.position(row_id)
    -> address_segment.get(pos)
    -> RowAddress::from(address)

U64Segment 是这里的压缩表示。它会根据 row id 序列的形态选择不同结构：

Range:
  连续有序，例如 100..200

RangeWithHoles:
  大体连续，但有少量空洞

RangeWithBitmap:
  大体连续，使用 bitmap 标记哪些位置存在

SortedArray:
  有序但比较稀疏

Array:
  无序序列

这解释了一个问题：开启 stable row id 后，Lance 并不是为每一行都写一条元数据。通常情况下，连续插入的 row id 可以用 range 表示；经过 update、delete、compaction 后，如果出现空洞或乱序，才会逐步退化到 bitmap 或 array 这类表示。

源码入口：

docs/src/format/table/row_id_lineage.md
  Row Address vs Row ID
  stable row id behavior

docs/src/format/index/index.md
  Stable Row ID for Index

rust/lance/src/dataset/rowids.rs
  get_row_id_index
  load_row_id_index

rust/lance-table/src/rowids/index.rs
  RowIdIndex
  FragmentRowIdIndex

rust/lance-table/src/rowids/segment.rs
  U64Segment

Stable Row ID 的作用包括：

• compaction 后索引不必因为物理地址变化而整体重写。
• update 后如果 indexed column 没变，可以减少索引失效范围。
• 适合长期维护的大表、频繁 compaction、索引构建成本高的场景。

但它也有成本：

• 查询时多一次 stable row id -> row address 的映射。
• 每个 fragment 需要维护 row_id_meta。
• 删除和更新会让 row id sequence 从连续 range 演化成 holes、bitmap、array 等形态。
• 这个功能需要在创建 dataset 时启用，不能在已有未启用的表上后补。

因此，Stable Row ID 不适合无差别默认打开。对于一次性导入、低频更新、可以接受索引重建的小表，它未必值得。对于索引构建成本高、compaction 频繁、需要长期维护的数据集，它更有价值。

一个完整例子

假设有一张 Lance 表：

schema:
  id: int64
  text: string
  vector: fixed_size_list<float32>[768]

indices:
  vector index on vector
  scalar index on id

初始状态：

Manifest v1
  Fragment 1: rows 0..999
  Fragment 2: rows 1000..1999

Vector index:
  fragment_bitmap = {1, 2}

执行一次 update：

UPDATE table
SET text = 'new text'
WHERE id = 42;

处理步骤：

1. scan 找到 id = 42 的 row address
2. 写出更新后的新 row 到 Fragment 3
3. 给 Fragment 1 写 deletion file，标记旧 offset deleted
4. 提交 Operation::Update
5. affected_rows = {(Fragment 1, offset 42)}

如果与此同时另一个事务删除 id = 43：

T1 affected_rows = {(F1, 42)}
T2 affected_rows = {(F1, 43)}

两者落在同一个 fragment，但 row 不重叠。只要没有其他 data file rewrite，Lance 就有机会通过合并 deletion vector 完成 rebase。

后续执行 compaction：

Fragment 1:
  deleted rows 超过 threshold

Fragment 2:
  小于 target_rows_per_fragment

planner 会检查：

这些 fragment 是否相邻？
它们是否有相同 index coverage？
删除比例是否值得单独 materialize？

如果最终 rewrite：

old:
  Fragment 1
  Fragment 2

new:
  Fragment 10

那么索引必须处理：

fragment_bitmap:
  {1, 2} -> {10}

row address:
  old addresses -> new addresses

如果开启 stable row id：

index payload 仍然指向 stable row id
RowIdIndex 更新 stable row id 到新 RowAddress 的映射

这个例子覆盖了 Deletion Vector、Compaction、Index Remap 和 Stable Row ID 之间的关系。

小结

Lance 的写入链路不是传统数据库的原地更新，也不是简单 append-only log。它是一套版本化的列式数据集写入机制：

• delete 通过 deletion vector 让旧行不可见。
• update 和 merge 通过写新 rows / columns 加 tombstone 旧 rows 来表达修改。
• Deletion Vector 同时服务读过滤和 row-level 写入冲突检测。
• Paimon 的 DV 更偏主键表 MOW 和文件级读过滤；Paimon Data Evolution 为了列 overlay 语义关闭 DV。
• Compaction 负责合并小 fragments、物化删除、改善布局。
• Compaction 会改变 row address，因此会牵引出 index remap。
• Stable Row ID 通过引入稳定逻辑行 ID，把索引从物理 row address 中解耦。

可以把 Lance 写入链路的设计压力概括为：

文件重写之后，deletion、version、index 和 row identity 仍然需要表达同一批逻辑行。