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

交易，述此提交于表之变。故创索引、紧缩文件、更配置，虽行数无改，亦生新版。

删除：以删除向量标不可见行。

删除不即改写数据文件，但标所中行为已删。

简其链路如下：

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 有千行：

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

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

源码上，Fragment元数据中有一可选deletion_file字段，义为“此 Fragment 内已删之本地行偏移”。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，且于扫描时越行已作 tombstone。

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(...)

以一十列表仅更一列为例：

更新前:
  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 }

刪除向量與寫入衝突檢測

刪除向量非唯讀時過濾已刪行，亦使Lance能將部分寫入衝突自“片段級衝突”降為“行級衝突”。

首观无 Deletion Vector / 受损行时之惑：

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 提交时，传所中行址于 commit 层：

CommitBuilder.with_affected_rows(RowAddrTreeMap)

是使冲突检测可判：

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

若但改同 fragment 之异行，且他事未改 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非能尽消写入之冲突。其所具者，乃行级受影响之能也，使Lance可避一部分片段级之虚冲突。

于含众样本之数据集，更新、删除、merge往往仅损少行。若并发控制仅达片段之粒，则多将不相交之行级修文判为冲突。

Lance与Paimon之Deletion Vector异同

Lance与Apache Paimon皆具Deletion Vector，然其所解之题非尽同。

维度	Lance	阿帕奇派蒙（Apache Paimon）
主要数据模型	向 Arrow / Lance 片段列式数据集	对湖仓表、主键表、LSM、bucket、snapshot而言
影之细也	fragment中局部row偏移	数据文件内行位置
典型之用	删除、更新、合并、冲突检验、读时过滤、压缩实现删除	主键表 MOW 模式下，读时无合并，写时生 DV 文。
與更新之關係	更新常見途徑乃寫新行，並覆蓋舊行之墓碑	主鍵表依賴 LSM 查舊資料，生成 DV
與列級演進之關係	Lance 有片段多數據檔及行 ID 元數據，更新後仍維繫片段/行位址	Paimon 資料演進採按列疊蓋，同first row id之檔案讀時合併
與衝突檢測之關係	affected_rows可令並發 delete/update 做行級重基	更主于键表之写入链路及文件级读滤

Paimon之DV文义甚明：录data file中删去之row位置，读文件时滤此诸行。Paimon之Merge On Write式赖LSM，可于写入时询主键，生应data file之deletion vector，使读时毋须复行全合。

Paimon之Data Evolution表另辟蹊径：唯将更新列书于新文件，原数据文件仍其旧，读时合同first row id之众文件为完整行。是故Paimon Data Evolution必闭deletion vectors，且暂不支寻常Delete/Update之令。

今举Data Evolution与DV组合之简例于下：

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

update file:
  firstRowId = 100
  columns: b_new

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

若复引文件级删除向量：

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

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

若欲兼行此二制，则读写之道须并理“行削”与“列叠合”。Paimon 分置 Data Evolution 与 Deletion Vector，以避此二义相扰。

兰斯之常更路线者：

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

故Lance之Deletion Vector，非独为读过滤之器，亦参与并发写入之rebase与冲突之辨。

夯土之时，何择碎片？

删除向量减损了删除/更新操作的写放大，然存二患：

• 小量增附，或致多生微片。
• 屡次删除更新，则 fragment 中已删之行列或众。

Compaction 用以治此布局之弊。

Lance 之 compaction，非徒按文件之巨细择之，乃重 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

其应如是：

• 删除逾十者，纵其独为 fragment，亦宜重书。
• 行数未达其目之小 fragment，将试与邻之候选 fragment 合并。
• compaction 按行数谋之，非直按文件之字数择焉。

源码入口：

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 依索引覆域将候选 fragments 分 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 之要义，乃重写也：

old fragments:
  F1, F2

new fragments:
  F10

若索引所载者乃行址，则经 compaction 后，必维索引之址。

Lance 之行址，由片段之标识与行之偏移所成：

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

虽逻辑上仍属同批活行，然物理之址已异。索引所存之行址，必随之更易，否则索引将指旧片段。

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

于事务之应用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，视乎索引内是否存有可自旧行址映新行址之明细。

可依索引内所载区分：

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

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

如向量索引，非独一 key -> row address 之映。IVF 此类索引内，有聚类中心、partition、向量列、row id 列等构。compaction 之後，向量值虽未易，row address 则变，索引内之 row id/address 负载须一致更新。若索引格式未予廉价、局部、可靠之 remap 能力，则唯重写或借 fragment reuse index 延后处置。

是故，compaction之难，非独在重书data files：

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 之序自连绵之范围，渐化而为 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 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 乃以新行新列之增，附旧行之墓碑，以彰更易。
• 删除向量，兼司读滤与行级写入冲突之检。
• Paimon 之 DV，尤主键表 MOW 与文件级读滤；Paimon 数据演化，为列覆盖之谓，乃闭 DV。
• 压实，主于合微片段、物化删除、善布局。
• 压实易行址，故引索引重映。
• 稳定行 ID，以引稳逻辑行 ID，使索引脱物理行址。

Lance 写入链路之设，其压力可概为：

文件重写之后，deletion、version、index及row identity仍需表同批逻辑行。