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 仍然需要表達同一批邏輯行。