Spike: Action-level conflict resolution design

[wjones127]

Parent PRD

Milestone: Action-based Transactions (UserOperation) — see milestone description for full PRD.
Discussion: #5960

Anchor design

A draft design exists on a prototype branch:
rust/lance-table/design/action_based_conflict_resolution.md.

This spike adopts that doc as its starting point. The work here is to land
the doc in-tree, fill out its TODO sections (§4 catalog, §5 matrix,
§6 rules, §8 payloads, §11 migration), and resolve its open questions.

What to build

Design how conflict resolution works at the Action level rather than the
Operation level. The new system must detect conflicts and rebase using only
Action types and payloads — no higher-level operation intent.

Three design patterns from the doc anchor the rest of the work and must
be confirmed or revised in this spike:

1. Criterion-based targeting (§3.1) — actions targeting open sets carry
   predicates over (fragment_ids, field_ids, ...), not identity lists.
   Motivating case: Update on column X || concurrent AddIndex on column X.
2. Late binding of action output (§3.2) — payloads use FragmentTemplate
   (no id) rather than Fragment. IDs assigned at apply time from manifest
   counters. Rebase becomes a no-op for produced IDs.
3. Symbolic intra-transaction references (§3.3) —
   FragmentRef::ProducedBy { action_idx, output_idx }, resolved through
   TxnContext as the driver walks the action list. Pins compound-txn
   dependencies to an ordered list, not a DAG.

These three together change the shape of the Action trait from the
current apply(&Manifest) + conflicts_with(&other) pair to a five-method
contract (reads/writes/validate/rebase/apply) plus a driver loop
that uses mask intersection to gate rebase. This is the most consequential
piece for #6450–#6453 to be designed against.

Catalog reconciliation (must do before #6451/#6452 land)

The milestone PRD's 14-action catalog and the design doc's §4 catalog
disagree on three concrete points. This spike must resolve them so
implementation issues design against the right shape:

Topic	Milestone PRD	Design doc §4	Resolution needed
Single-fragment updates	UpdateFragment(Fragment) (omnibus: deletion files, replaced columns, swap data files)	Split into UpdateDeletionVector, ReplaceFragmentColumns, RewriteFragments	Decide whether to split. If yes, migrate #6450's shipped UpdateFragment to UpdateDeletionVector (the only translation that landed — Delete — used it that way).
Index coverage	AddIndex / RemoveIndex only	Plus InvalidateIndexCoverage, RebindIndexCoverage, RegisterFragReuse	Decide whether to add the three coverage actions. Required to express open-set cross-resource cases (§3.1).
Compact distinction	RemoveFragments + AddFragments	RewriteFragments (asserts data equivalence; enables index salvage via RebindIndexCoverage)	Decide whether RewriteFragments warrants its own action.

Acceptance criteria

• Land the design doc at rust/lance-table/design/action_based_conflict_resolution.md
• §4 action catalog complete: enumerate all remaining actions (Append-only, AddIndex, DropIndex, UpdateConfig, Restore, ReserveFragments, Project, UpdateBases, Clone, DataReplacement, Merge), each with payload + read-set + write-set + commutativity notes
• Three catalog reconciliation decisions above resolved and reflected in the doc
• §5 conflict matrix filled in (N×N over the §4 catalog, cells C / X / R(n))
• §6 rules written for every R(n) cell (detection predicate + resolution: rebase rewrite, fail, or auto-merge)
• §7 Action trait shape ratified or revised; current Action::apply + conflicts_with deprecated path documented
• §8 payload changes called out per action, including proto-breaking changes
• §11 migration map: each existing check_*_txn in conflict_resolver.rs mapped to its action-level replacement (or flagged as not-yet-expressible)
• Open questions in the doc (§§ "Open Questions") resolved or explicitly deferred with rationale
• Knock-on edits to milestone Compute min/max values for columns to support file-level and chunk-level pruning. #11 PRD action catalog and to RemoveFragments + UpdateFragment actions (internal) #6450/Schema actions: AddFields, DropFields, UpdateSchemaMetadata (internal) #6451/Index actions: AddIndex, RemoveIndex, UpdateMemWalIndex (internal) #6452/Config/metadata actions: UpdateConfig, UpdateTableMetadata, SetDataFormat, SetFeatureFlags, ReserveFragmentIds (internal) #6453 issue scopes

Out of scope

• Implementing the trait or any new action types (those live in RemoveFragments + UpdateFragment actions (internal) #6450–Config/metadata actions: UpdateConfig, UpdateTableMetadata, SetDataFormat, SetFeatureFlags, ReserveFragmentIds (internal) #6453 and follow-ups).
• Isolation-level taxonomy (§12) beyond a brief sketch.
• Physical commit protocol / manifest layout.

Blocked by

None — can start immediately.

Blocks

• Schema actions: AddFields, DropFields, UpdateSchemaMetadata (internal) #6451, Index actions: AddIndex, RemoveIndex, UpdateMemWalIndex (internal) #6452, Config/metadata actions: UpdateConfig, UpdateTableMetadata, SetDataFormat, SetFeatureFlags, ReserveFragmentIds (internal) #6453 (catalog reconciliation must land first)
• Design: representation of Update auxiliary fields #6843 (Update auxiliary fields — largely answered by §4 decomposition of Update; depends on catalog)
• DataReplacement Operation translation (apply-time) #6842 (DataReplacement translation — likely subsumed by ReplaceFragmentColumns; depends on catalog)

User stories addressed

• User story 6: single code path for conflict resolution

[westonpace]

Very excited to see some work here.

User story 6: single code path for conflict resolution

I'm curious, what is this 😅?

[wjones127]

There’s a full PRD (written by an agent after a conversation with me) in the expanded milestone description. This bulletin reads:

As a library developer, I want a single code path for conflict resolution, so that adding a new action type doesn't require updating every conflict-checking function.

I’m hoping we can simplify conflict resolution. We’ll see if that’s true.

[wjones127]

Re-scoped this issue against the draft design doc on the prototype branch (link).

Material changes from the original scope:

1. Three design patterns (criterion-based targeting, late binding, symbolic refs) become load-bearing for the rest of milestone 11. Acceptance criteria now require resolving them, not just sketching a matrix.
2. Action trait shape changes. The doc specifies a five-method contract (reads/writes/validate/rebase/apply) plus a driver loop using mask intersection. This replaces the current apply + conflicts_with pair shipped in RemoveFragments + UpdateFragment actions (internal) #6450. Migration path needs to be in this spike.
3. Catalog reconciliation is now part of the spike. The milestone PRD's 14-action catalog and the doc's §4 catalog disagree on three concrete points (omnibus UpdateFragment split; index-coverage actions; RewriteFragments as distinct action). Schema actions: AddFields, DropFields, UpdateSchemaMetadata (internal) #6451/Index actions: AddIndex, RemoveIndex, UpdateMemWalIndex (internal) #6452/Config/metadata actions: UpdateConfig, UpdateTableMetadata, SetDataFormat, SetFeatureFlags, ReserveFragmentIds (internal) #6453 should not start implementation until those land.
4. Knock-on issue updates. Design: representation of Update auxiliary fields #6843 (Update misc fields) and DataReplacement Operation translation (apply-time) #6842 (DataReplacement apply-time) are likely subsumed or reframed by the doc's decomposition of Update and ReplaceFragmentColumns respectively. Will revisit after the spike concludes.

[wjones127]

First-draft action catalog (strawman)

Posted for review. Drafted by a subagent against the design doc (commit e5105f7b), the milestone #11 PRD, and the current implementation. Not yet ratified — this is the strawman this spike should accept, revise, or replace.

Working from the design doc commit e5105f7b, milestone #11 PRD, and the legacy Operation enum in rust/lance/src/dataset/transaction.rs (15 variants). The doc's §4 carries explicit TODOs to enumerate Append-only, AddIndex, DropIndex, UpdateConfig, Restore, ReserveFragments, Project, UpdateBases, Clone, DataReplacement, Merge — this fills them.

Conventions used:

• Fragment = the in-memory fragment with a concrete ID.
• FragmentTemplate = the doc's late-bound fragment (data files, deletion file, row counts, preserved_row_ids hint, no id, no stable-row-ID base).
• All actions implement the §7 validate / rebase / apply trait.

1. Catalog

#	Action	Payload	Read-set	Write-set	Commutes with / Conflicts with
A1	AddFragments	{ fragments: Vec<FragmentTemplate>, preserved_row_ids: Option<Vec<PreservedRows>> }	NextFragmentId, NextRowId, optionally source fragments named in preserved_row_ids	fragment list (append), NextFragmentId, NextRowId	Commutes with everything that does not read the new fragments. Counter overlap with concurrent AddFragments is resolved by reassignment at apply (§3.2). Conflicts only with schema-narrowing actions that drop a field the new fragments require.
A2	RemoveFragments	{ fragment_ids: Vec<u64> }	fragment list	fragment list	Commutes with disjoint RemoveFragments and any action on disjoint fragments. Conflicts with UpdateDeletionVector / ReplaceFragmentColumns / RewriteFragments / RegisterFragReuse on overlapping ids; also with AddIndex over a bitmap that names one of the removed ids.
A3	UpdateDeletionVector	{ fragment_id: u64, new_deletion_file: DeletionFile, affected_rows: Option<RowAddressRanges> }	fragment row count, existing deletion file	fragment.deletion_file	Commutes on different fragments. Same-fragment merges by union iff both carry affected_rows and data files unchanged; else conflict. Conflicts with RemoveFragments / RewriteFragments / ReplaceFragmentColumns when offsets overlap.
A4	ReplaceFragmentColumns	{ fragment_id: u64, field_ids: Vec<u32>, new_data_files: Vec<DataFile>, updated_row_offsets: Option<RowOffsetBitmap> }	data files for these fields on this fragment	fragment.files for listed fields; last_updated_at_version for the rows in updated_row_offsets	Commutes on disjoint (fragment_id, field_id) pairs. Conflicts with another writer of the same (fragment_id, field_id), with AddIndex/RewriteIndex covering those fields, and with RewriteFragments touching that fragment. Implements DataReplacement and Update-RewriteColumns.
A5	RewriteFragments	{ old_fragment_ids: Vec<u64>, new_fragments: Vec<FragmentTemplate>, preserves_row_ids: bool }	full old fragment contents	splice old → new in fragment list	Conflicts with anything touching old_fragment_ids' data/deletions; with overlapping RewriteFragments; with AddIndex over a bitmap that straddles a remap group. Distinguished from Remove+Add by asserting data equivalence so index coverage can be salvaged.
A6	AddFields	{ new_fields: Vec<Field>, fragment_files: Vec<(u64, Vec<DataFile>)> }	current schema, existing fragments named in fragment_files	schema (append), per-fragment data files (additive)	Commutes with disjoint-fragment data actions on existing fields. Conflicts with concurrent AddFields touching the same field IDs, DropFields of a referenced parent, Overwrite-derived schema changes, and AddIndex over the new fields.
A7	DropFields	{ field_ids: Vec<u32> }	schema, fragment file lists (closure over fields)	tombstone field IDs in schema; remove from fragment file lists	Conflicts with anything reading or writing the dropped field IDs (AddIndex, ReplaceFragmentColumns, AddFragments whose template references the dropped fields).
A8	ChangeSchema	{ new_schema: Schema }	none	schema (replaced)	Used only inside Overwrite-style transactions. Conflicts with every other schema-mutating action; commutes only with actions that do not touch schema.
A9	UpdateSchemaMetadata	{ schema_updates: UpdateMap, field_updates: HashMap<u32, UpdateMap> }	schema metadata	schema/field metadata key/value	Two updates commute when their key sets are disjoint; same-key concurrent writes conflict (matches today's check_update_config_txn for schema metadata).
A10	AddIndex	{ index: IndexMetadata, replaces: Option<Uuid>, criterion: IndexCoverageCriterion } where criterion = { field_ids, fragment_filter: All | Bitmap } (§3.1)	schema field IDs, fragment list (to populate fragment_bitmap)	indices list (append/replace)	Commutes with disjoint-field/disjoint-fragment AddIndex. Conflicts with RemoveIndex of same UUID, with AddIndex of same name over an overlapping field set, and with DropFields / UpdateDeletionVector / ReplaceFragmentColumns / RewriteFragments whose effect on the criterion isn't already absorbed by InvalidateIndexCoverage or RebindIndexCoverage.
A11	RemoveIndex	{ index_id: Uuid }	index entry	indices list (remove)	Commutes with everything except concurrent mutation of the same UUID.
A12	RewriteIndex	{ old_id: Uuid, new_id: Uuid, new_files: Vec<IndexFile>, new_index_details: prost::Any, new_index_version: i32 }	old index entry	replace index entry by UUID	Conflicts with any AddIndex/RemoveIndex/RewriteIndex on same UUID. Used by Rewrite without stable row IDs.
A13	InvalidateIndexCoverage	{ fragment_ids: Vec<u64>, field_ids: Vec<u32> }	index fragment_bitmap, field membership	shrink fragment_bitmap for every index covering any of field_ids	Pure criterion (§3.1). Commutes with itself; conflicts with a concurrent RebindIndexCoverage that has already moved the same (frag, field) away.
A14	RebindIndexCoverage	{ remap: Vec<(u64, u64)>, preserved_fields: Vec<u32> }	index fragment_bitmap, field membership	swap old → new IDs in fragment_bitmap for indices over preserved_fields only	Commutes with disjoint-bitmap AddIndex; conflicts with AddIndex/RewriteIndex straddling a remap group and with InvalidateIndexCoverage on the same (frag, field).
A15	RegisterFragReuse	{ index: IndexMetadata, entries: FragReuseEntries }	current frag_reuse_index	replace frag_reuse_index	Singleton per commit window — second instance conflicts. Conflicts with AddIndex whose coverage straddles a deferred-remap group.
A16	UpdateConfig	{ config_updates: UpdateMap, table_metadata_updates: UpdateMap }	manifest config, table metadata	same	Two updates commute iff key sets are disjoint and neither is replace=true; otherwise conflict (matches upsert_key_conflict today).
A17	ReserveFragmentIds	{ num_fragments: u32 }	NextFragmentId	NextFragmentId (advance)	Commutes with everything except itself / AddFragments (and even then trivially — both just bump the counter). Kept primarily for round-trip with legacy Operation::ReserveFragments.
A18	AddBases	{ new_bases: Vec<BasePath> }	existing BasePath list	append-only	Conflicts only on duplicate id/name/path; commutes with all data/schema/index actions.
A19	UpdateMergedGenerations	{ generations: Vec<MergedGeneration> }	MemWAL index state	MemWAL index entry	Conflicts with another UpdateMergedGenerations sharing a shard with disagreeing generations (mirrors check_merged_generations_conflict).

Notes:

• Symbolic refs (§3.3) appear in A1's preserved_row_ids (could reference an earlier action's output) and in A10's criterion.fragment_filter when AddIndex follows AddFragments in the same transaction (criterion All resolved against working manifest after A1 applies — covers compound "append + create index" cleanly).
• Restore/Clone remain not actions; they are top-level TransactionKind variants, as already coded.
• ChangeSchema (A8) is intentionally narrower than a free-floating replace — it exists for Overwrite/Project and is the action that earns "schema replaced" semantics with proper validate.
• Project is ChangeSchema over the existing schema's column subset; no separate action.

2. Legacy Operation → Action decomposition

Legacy Operation	Action list	Payload gap?
Append { fragments }	[AddFragments]	none
Delete { updated_fragments, deleted_fragment_ids, predicate }	one UpdateDeletionVector per updated fragment + RemoveFragments (if any). predicate → UserAction.description.	none (current code stuffs full Fragment into UpdateFragment; the new A3 carries only the deletion file, so legacy round-trip must reconstruct other fragment fields from manifest — verify)
Overwrite { fragments, schema, config_upsert_values, initial_bases }	[RemoveFragments(All)¹, ChangeSchema, AddFields², AddFragments, UpdateConfig?, AddBases?]	¹ RemoveFragments needs a "criterion = all current ids" form — propose extending payload to { fragment_ids: Selector } where Selector = Ids(Vec<u64>) | AllCurrent. ² Only if new schema has fields the old did not.
CreateIndex { new_indices, removed_indices }	one AddIndex per new + one RemoveIndex per removed	IndexMetadata.fragment_bitmap already carries coverage; criterion form encodes this
Rewrite { groups, rewritten_indices, frag_reuse_index }	one RewriteFragments per group; then either (stable IDs) RebindIndexCoverage + optional RegisterFragReuse; or (no stable IDs) one RewriteIndex per rewritten_indices entry	none
DataReplacement { replacements }	one ReplaceFragmentColumns per DataReplacementGroup. replaces field-set inferred from DataFile.fields of the swap.	needs apply-time read of current fragment files — covered by the §7 in-progress manifest
Merge { fragments, schema }	[AddFields(new_fields), UpdateFragment-style per existing fragment with new column files] — i.e. fan-out into one ReplaceFragmentColumns (adding new fields' files) per fragment + AddFields	ReplaceFragmentColumns payload assumes fields already exist; for Merge the AddFields must precede. Compound is symbolic-ref-safe via ordering.
Restore { version }	top-level TransactionKind::Restore	n/a
ReserveFragments { num_fragments }	[ReserveFragmentIds]	none
Update { removed_fragment_ids, updated_fragments, new_fragments, fields_modified, merged_generations, fields_for_preserving_frag_bitmap, update_mode, inserted_rows_filter, updated_fragment_offsets }	RewriteRows: RemoveFragments(removed_fragment_ids) + AddFragments(new_fragments, preserved_row_ids) + per-leftover UpdateDeletionVector + per-touched-index InvalidateIndexCoverage(fields_modified) + RebindIndexCoverage(_, fields_for_preserving_frag_bitmap) + optional UpdateMergedGenerations. RewriteColumns: one ReplaceFragmentColumns(updated_fragment_offsets) per (frag, field-set) + InvalidateIndexCoverage.	inserted_rows_filter — see §5; no action carries it today.
Project { schema }	[ChangeSchema(schema)] (no field/data drop required because Project only narrows in-memory view)	confirm whether Project ever physically tombstones fields; if so, add DropFields
UpdateConfig { config_updates, table_metadata_updates, schema_metadata_updates, field_metadata_updates }	[UpdateConfig, UpdateSchemaMetadata] (split data/table from schema/field metadata)	none
UpdateMemWalState { merged_generations }	[UpdateMergedGenerations]	none
Clone { … }	top-level TransactionKind::Clone	n/a
UpdateBases { new_bases }	[AddBases]	none

3. Design-pattern application

Action	§3.1 criterion-based	§3.2 late binding	§3.3 symbolic ref
A1 AddFragments	—	yes (fragment_id, row_id)	source of refs
A2 RemoveFragments	optional (Selector::AllCurrent for Overwrite)	—	—
A3 UpdateDeletionVector	—	—	could ref ProducedBy for compound dedup-then-delete
A4 ReplaceFragmentColumns	—	—	may ref preceding AddFragments
A5 RewriteFragments	—	yes for new ids	source of refs
A6 AddFields	—	yes (field IDs allocated)	source of refs
A7 DropFields	—	—	—
A8 ChangeSchema	—	—	—
A9 UpdateSchemaMetadata	—	—	—
A10 AddIndex	yes (criterion.fragment_filter)	yes (index UUID)	criterion may match ProducedBy
A11 RemoveIndex	—	—	—
A12 RewriteIndex	—	yes (new UUID)	—
A13 InvalidateIndexCoverage	yes (every index over field set)	—	—
A14 RebindIndexCoverage	yes	—	—
A15 RegisterFragReuse	—	—	—
A16 UpdateConfig	—	—	—
A17 ReserveFragmentIds	—	yes	—
A18 AddBases	—	—	—
A19 UpdateMergedGenerations	—	—	—

4. Deltas

vs. milestone PRD (14 actions)

• Kept (renamed/reshaped): AddFragments, RemoveFragments, AddFields, UpdateConfig, ReserveFragmentIds (← ReserveFragmentIds), UpdateMergedGenerations (← UpdateMemWalIndex).
• Split UpdateFragment (the omnibus in RemoveFragments + UpdateFragment actions (internal) #6450) into 3: A3 UpdateDeletionVector, A4 ReplaceFragmentColumns, A5 RewriteFragments. Per the design doc, these carry different read/write sets and different conflict rules; collapsing them loses the criterion / late-binding distinctions and forces conflict resolution to peer inside Fragment diffs.
• Split AddIndex into 4: A10 AddIndex (criterion-based), A12 RewriteIndex, A13 InvalidateIndexCoverage, A14 RebindIndexCoverage, A15 RegisterFragReuse. The PRD bundle could not express Rewrite's "remap coverage" semantics or the Update→index criterion shrink without re-encoding intent.
• Renamed: UpdateTableMetadata → folded into UpdateConfig; UpdateSchemaMetadata kept (A9). SetDataFormat and SetFeatureFlags dropped from first pass — neither has a decomposition entry from existing Operation variants. Listed in §5.
• Added: A8 ChangeSchema (needed for Overwrite/Project; PRD silently bundled into AddFields/DropFields), A18 AddBases (PRD omitted; Operation::UpdateBases exists).
• Dropped: DropColumns as a standalone action; it's A7 DropFields + A4 ReplaceFragmentColumns on each fragment.

vs. design doc §4

• §4 lists 9 actions and explicitly TODOs the rest. Kept all 9 as-is (with the named field tweaks). Added: A6 AddFields, A7 DropFields, A8 ChangeSchema, A9 UpdateSchemaMetadata, A11 RemoveIndex, A16 UpdateConfig, A17 ReserveFragmentIds, A18 AddBases, plus RemoveFragments::Selector to support Overwrite.
• The doc's UpdateDeletionVector (A3) replaces today's omnibus Action::UpdateFragment already in-tree; current code will need to narrow.

5. Open questions

1. Operation::Update.inserted_rows_filter (KeyExistenceFilter). Used by check_append_txn and check_update_txn to detect primary-key collisions between concurrent INSERTs. No proposed action carries it. Options: (a) attach to AddFragments as conflict-detection metadata (the design doc's §7 closing line hints at this); (b) introduce a sibling AssertNoKeyCollision { filter, key_columns } action. Recommend (a) for round-trip simplicity but flag for review.
2. Operation::Update.fields_for_preserving_frag_bitmap vs. fields_modified. Mapping treats these as RebindIndexCoverage.preserved_fields and InvalidateIndexCoverage.field_ids. Confirm these two sets are always disjoint in practice; if not, the per-action targeting needs splitting per index.
3. RemoveFragments selector vs. PRD's plain id list. The PRD insists fragment ids are explicit; the doc's §3.1 motivates AllCurrent for Overwrite. We need a selector. Worth a small design note rather than smuggling it in.
4. Should ChangeSchema (A8) exist or should Overwrite decompose into DropFields + AddFields? The latter is more uniform but loses "schema replaced wholesale" intent that check_overwrite_txn's last-writer-wins relies on (doc §9 worked example).
5. SetDataFormat / SetFeatureFlags from the PRD. Have no Operation consumer today. Per the ground rules, dropped — but resurfacing once the new-format writer feature flag lands (would be at least one user). Confirm OK to defer.
6. DataReplacement translation (DataReplacement Operation translation (apply-time) #6842). A4 ReplaceFragmentColumns needs the current fragment's per-field file layout to validate the "same layout across fragments" rule today's Operation::DataReplacement enforces. This is doable in validate/apply against manifest, but the payload may need an optional expected_layout_hash: Option<u64> for defensive checks during rebase. Flag for DataReplacement Operation translation (apply-time) #6842.
7. Operation::Merge and the physical_rows alignment rule. Today Merge asserts new fragments align with old fragments row-by-row. Per-fragment ReplaceFragmentColumns carries this implicitly (fragment id binds the alignment), but the empty-fragment edge case (Merge of a brand-new column where row count came from elsewhere) needs a worked example.
8. PRD might be right on RewriteFragments absent. The PRD folded Rewrite into AddFragments + RemoveFragments. The doc keeps RewriteFragments specifically so index coverage can be salvaged. Doc wins — but worth stating that the PRD's instinct made the round-trip mapping for Rewrite lossy, which is the concrete justification.
9. UserAction.description as the only home for Operation::Delete.predicate. Round-trip-lossless today, but if Python/Rust callers ever programmatically introspect "what predicate caused this delete," that field becomes load-bearing prose. Worth deciding if predicate (and Update's predicate-equivalent) deserves a typed slot on UpdateDeletionVector.
10. ReserveFragmentIds (A17) — does it survive the migration? No new compound-transaction use case needs it; it exists only for legacy round-trip and for the rare "I'm going to write the data outside, give me ids" workflow. Could be dropped if we're willing to translate Operation::ReserveFragments to a no-op AddFragments-with-empty list — but probably cleaner to keep.