Lanceの書き込みパイプラインはファイルレイアウト、バージョンコミット、削除マーク、インデックスのメンテナンス、コンパクションに関わっています。従来のデータベースとは異なり、Lanceは元のファイル上で直接データを変更せず、新しいファイルを追加し、メタデータを更新することで新しいテーブルバージョンを生成します。

本稿では、いくつかの実装上の問題について議論します：

• delete、update、merge insertがファイルとメタデータにどのように適用されるか。
• 削除ベクトル（Deletion Vector）がLanceの書き込みパイプラインでの役割。
• 削除ベクトルが書き込みコンフリクト検知にどのように関与するか。
• LanceとApache Paimonが削除ベクトルの設計においてどのように異なるか。
• コンパクションがどのようにフラグメントを選択し、インデックスリマップが必要な理由。
• Stable Row ID はコンパクション後のインデックスメンテナンスコストをどのように削減するか。

基本的な判断

Lance の書き込みの基本形は：新規データファイルまたは deletion file を書き込み、次にトランザクションとマニフェストを通じて新バージョンをコミットする。

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 version N
  schema
  fragments
  indices
  version metadata

Fragment 1
  data files
  deletion file
  row id metadata

トランザクションは、今回のコミットによるテーブル状態の変更を記述します。そのため、インデックスの作成、コンパクト化ファイルの作成、設定の更新によって新バージョンが生成される可能性がありますが、行数が変わっていない場合もあります。

Delete：削除ベクトルを使用して非表示行をマークします

Delete：すぐにデータファイルを書き換える代わりに、対象の行を削除済みとしてマークします。

連携を簡略化すると以下のようになります：

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 内で削除されたローカル行オフセット」です。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行をスキップする必要があることです。

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全体を書き換えるのではなく、ヒットした行を新しい行として書き出す。更新される各行に対して、完全な行が出力される。

ソースコードエントリーポイント：

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 が一部の書き込み衝突を「fragment レベルの衝突」から「row レベルの衝突」に低減できるようにします。

まず、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 のコミット時に、ヒットした row address をコミット層に伝えます：

CommitBuilder.with_affected_rows(RowAddrTreeMap)

これにより、衝突検知が以下のように判断できます：

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

同じ fragment の異なる行を変更し、他のトランザクションがデータファイルを変更せず、削除ファイルのみを変更した場合、現在のトランザクションは rebase の機会があります。つまり、新しい fragment 削除ファイルに基づいてマージされた削除 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

したがって、削除ベクターはすべての書き込みコンフリクトを解消するわけではありません。それが提供するのは、行レベルの影響を受けた行の表現能力であり、Lanceが一部のフラグメントレベルの誤ったコンフリクトを回避できるようにします。

多くのサンプルを含むデータセットにおいて、更新、削除、マージは通常少数の行に影響を与えます。もし並行制御がフラグメント粒度しか達しなければ、多くの交差しない行レベルの変更をコンフリクトと判断してしまうでしょう。

LanceとPaimonの削除ベクターの違い

LanceとApache Paimonはどちらも削除ベクターを持っていますが、それらが解決しようとしている問題は完全に異なります。

次元	Lance	Apache Paimon
主なデータモデル	Arrow / Lance fragment に対応した列式データセット	湖仓表、主キー表、LSM、バケット、スナップショットに対応
DV粒度	fragment内のローカル行オフセット	データファイル内の行位置
典型的な用途	削除、更新、マージ、衝突検知、読み取り時のフィルタリング、コンパクションで削除を具体化	主キー表のMOWモードで読み取り時のマージを回避し、書き込み時にDVファイルを生成
と更新の関係	updateの一般的なパスは、新しいrowsを書き込む + 墓碑で古いrowsを削除することです	主キー表はLSMを使用して古いデータを検索し、DVを生成します
列ベースの進化との関係	Lanceはfragmentが多く、data filesとrow id metadataを持っており、更新後もfragment/row addressを中心に維持します	Paimon Data Evolutionは列ごとのオーバーレイを採用し、first row idのファイル読み込み時にマージします
衝突検知との関係	affected_rows並行なdelete/updateがレベルで再ベースを可能にします	は主キー表への書き込み経路とファイルレベルの読み取りフィルタリングにより偏っている

PaimonのDVドキュメントの意味は明確である：それはdata file内で削除された行の位置を記録し、ファイルを読み取る際にこれらの行をフィルタリングする。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 を分離し、これらの2つの意味が相互に影響しあうのを避けています。

Lance の典型的な更新ルートは以下の通りです：

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

したがって、Lance の Deletion Vector は読み取りフィルタリングツールだけでなく、並行書きの rebase とコンフリクト判断にも関与します。

コンパクション：どのタイミングでフラグメントを選択

Deletion Vector は delete/update の書き放大を低減しますが、2つの問題が残ります：

• 小規模な append が大量の小さなフラグメントを作成する可能性があります。
• 複数回のdelete/updateの後、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

対応する動作は以下の通りです：

• 削除割合が10%を超えるfragmentは、たとえ自分自身が一つのfragmentでも、書き直す価値があります。
• 行数が目標値以下の小さなfragmentは、隣接する候補fragmentとマージしようとします。
• compactionは行数に基づいて計画され、直接ファイルのバイト数で選ばれるわけではありません。

ソースコードのエントリーポイント：

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

ここにインデックス制約がある：コンパクションは「特定のインデックスで覆われたフラグメント」と「そのインデックスで覆われていないフラグメント」を同じリライトグループに混ぜない。

その理由は、Lanceのインデックスメタデータにfragment_bitmapがあるからで、これはどのフラグメントがインデックスで覆われるかを記述している。リライトグループにインデックス化されたフラグメントと非インデックス化されたフラグメントが混ざると、コンパクション後に生成された新しいフラグメントは明確にインデックス化されたものか非インデックス化されたものかのどちらにも分類されにくくなる。

したがって、コンパクションプランナーはインデックスのカバレッジに基づいて候補フラグメントをバインに分類する：

F1 indexed by vector_index
F2 indexed by vector_index
F3 not indexed

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

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

コンパクションがなぜインデックスリマップを引き起こすのか

コンパクションの本質はリライトである：

old fragments:
  F1, F2

new fragments:
  F10

インデックスに記録されているのが行アドレスの場合、コンパクション後はインデックス内のアドレスを維持する必要がある。

Lanceの行アドレスはフラグメントIDと行オフセットで構成される：

row_address = (fragment_id, row_offset)

コンパクション前：

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

コンパクション後：

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

論理的には同じセットのライブ行だが、物理アドレスは変わる。インデックスに保存されている行アドレスはそれに合わせて更新しなければ、インデックスが古いフラグメントを指すことになる。

Lanceはコンパクション後のインデックスに対していくつかの処理方法がある：

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

異なるインデックスのメンテナンス方法は異なります。リマップが可能かどうかは、インデックス内に old row address から new row address にマッピングできる詳細情報が保存されているかどうかによって決まります。

インデックス内の記録内容に基づいて区分けできます：

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

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

例えば、ベクトルインデックスは通常単一の key -> row address マッピングではありません。IVF などのインデックスは、クラスタリング中心、パーティション、ベクトルリスト、row id リストなどの構造を内部に持っています。コンパクション後、ベクトル値は変化しないものの、row address は変化するため、インデックス内の row id/address ポリシは一貫して更新する必要があります。インデックス形式が安価で、局所的で、信頼性の高いリマップ機能を提供しない場合、書き換えやフラグメント再利用インデックスによる後工程処理に依頼するしかありません。

したがって、コンパクションの難点はデータファイルの再書きに限定されない：

データファイルが再書きされた後でも、インデックスは同じ論理行を正しく位置付ける必要がある。

安定行ID：インデックスを物理アドレスから分離

安定行IDは各論理行に安定したIDを割り当て、インデックスが変化する行アドレスに直接依存しないようにする。

安定行IDがない場合：

row id ~= row address

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

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

安定行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 メタデータに基づいて構築したバージョンごとのメモリインデックスであり、メタデータキャッシュにキャッシュされています。

の構築エントリは：

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 が変わっていなければ、インデックスの無効範囲を減らすことができます。
• は、長期的なメンテナンスに適した大テーブル、頻繁なコンパクション、インデックス構築コストが高いシナリオに適しています。

しかし、コストもあります：

• クエリ時にstable row id -> row addressのマッピングが1回追加されます。
• 各フラグメントはrow_id_metaをメンテナンスする必要があります。
• 削除や更新では、行IDシーケンスが連続範囲からholes、bitmap、arrayなどの形態に進化します。
• この機能はデータセットを作成する際に有効にする必要があり、既存の未有効なテーブルに後付けできません。

したがって、Stable Row ID は無差別にデフォルトで有効にするのは適していない。一度に大量のデータをインポートし、低頻度で更新され、インデックスの再構築を許容できる小規模なテーブルの場合、それは必ずしも価値があるとは限らない。インデックス構築のコストが高く、コンパクションが頻繁で、長期的なメンテナンスが必要なデータセットの場合、それがより価値がある。

完全な例

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 に含まれるが、行は重複しない。他の data file の再書き込みがない限り、Lance は deletion vector のマージを通じて rebase を完了する機会がある。

の後、コンパクションを実行します：

Fragment 1:
  deleted rows 超过 threshold

Fragment 2:
  小于 target_rows_per_fragment

プランナーは次を確認します：

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

最終的なリライト：

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、コンパクション、Index Remap、Stable Row IDの関係をカバーしています。

まとめ

Lanceの書き込みパイプラインは、従来のデータベースのオンサイト更新でも、単純なappend-only logでもありません。それは、バージョン管理された列式データセットの書き込みメカニズムです：

• delete deletion vectorを使って古い行を非表示にします。
• update そしてmerge 新しい行/列を書き込み、古い行にトムストーンを追加することで変更を表現します。
• 削除ベクターは読み取りフィルタリングと行レベルの書き込み競合検知の両方をサービスします。
• PaimonのDVは主キー表MOWとファイルレベルの読み取りフィルタリングに偏っています。Paimon Data Evolutionは列オーバーレイの意味でDVをオフにします。
• Compactionは小さなフラグメントのマージ、物化削除、レイアウトの改善を担当します。
• Compactionは行アドレスを変更するため、インデックスリマップが引き起こされます。
• Stable Row IDは安定した論理行IDを導入することで、インデックスを物理行アドレスから解耦します。

Lanceの書き込みチェーンの設計のプレッシャーをまとめると：

ファイルを再書き込みした後、削除、バージョン、インデックス、および行識別子は依然として同じ論理行を表現する必要があります。