Row-level concurrency for OSS Delta: reconcile the writes that provably cannot conflict (umbrella) #3

Background

Delta's documented row-level concurrency states that several concurrent-write pairs on a table with
deletion vectors cannot conflict — two DML statements editing disjoint rows, a compaction
OPTIMIZE vs a concurrent DELETE/UPDATE, a blind INSERT against anything. OSS Delta today
still aborts the loser in most of these: ConflictChecker conservatively treats a file that a
concurrent commit removed, or added a DV to, as a conflict — even when the two commits are logically
independent.

This umbrella tracks closing that gap without any protocol change and without row tracking, as a
series of small, independently reviewable, opt-in (default-off) additions to ConflictChecker.

Organizing principle

Rather than enumerating special cases, the work is driven by one property:

Reconcile a concurrent pair whenever the loser's outcome is provably reconstructable from
deletion-vector positions, reader statistics, or a derivable output offset — never from a
whole-table read, a row permutation, or row lineage.

Everything reconstructable from that information is in scope (Phase 1); anything needing a
whole-table read, a row permutation, or row tracking is backlog. This lands exactly at parity with
the documented contract, because the deferred cases are the ones the reference implementation does
not reconcile either.

Phase 1 — opt-in, no row tracking

Tracked issues / PRs

Each case carries its own design in its own issue.

• Case 3 — OPTIMIZE vs non-blind append — [RLC] Case 3 — exclude relocation (dataChange=false) files from the append-conflict check #6 · upstreamed as [File-level concurrency] Exclude no-data-change (OPTIMIZE) files from append-only conflict checks delta-io/delta#7331 (fork PR [RLC] Case 3 — exclude relocation (dataChange=false) files from the append-conflict check #10 closed)
• Case 1 — conflict-time data skipping — [RLC] Case 1 — conflict-time data skipping (disjoint data ranges) #4 · PR [RLC] Case 1 — conflict-time data skipping (disjoint data ranges) #8
• Case 2 — same-file disjoint DML ⟂ DML (DV union) — [RLC] Case 2 — same-file deletion-vector merge (concurrent DML ⟂ DML) #5 · PR [RLC] Case 2 — same-file deletion-vector merge (concurrent DML ⟂ DML) #2
• Case 4 (write side) — capture & persist compaction composition — [RLC] Case 4 — OPTIMIZE ⟂ DML reconciliation (compaction offset remap) #7 · PR [RLC] Case 4 — Capture & persist compaction OPTIMIZE source composition (write side) #12
• Case 4a — compaction OPTIMIZE loses to DML (forward remap) — [RLC] Case 4 — OPTIMIZE ⟂ DML reconciliation (compaction offset remap) #7 · PR [RLC] Case 4a — OPTIMIZE loses to DML (forward compaction offset remap) #9
• Case 4b — DML loses to compaction OPTIMIZE (reverse remap) — [RLC] Case 4 — OPTIMIZE ⟂ DML reconciliation (compaction offset remap) #7 · PR [RLC] Case 4b — DML loses to OPTIMIZE (reverse compaction offset remap) #11

Dependencies. Case 4 reuses Case 2's deletion-vector helpers and splits into a shared write side
(PR #12) that captures & persists the composition, plus two reconcile readers that consume it —
forward (4a) and reverse (4b) — giving the stacking chain Case 2 → 4 (capture) → 4a → 4b. Cases
1 and 3 are independent. Suggested review order: this issue → 1 → 2 → 4 (capture) → 4a → 4b.

How the compaction cases stay cheap (Case 4)

Compaction concatenates each source file's live rows into one contiguous run in the output without
permuting within a file, so the whole problem reduces to where each source's run starts in the
output. That offset isn't derivable from the read plan (scan splits are sorted before packing, a
shuffle reorders rows, a non-Spark engine's order is opaque), so it is observed at write time: a
write-stage operator reads the per-row source-file identity that input_file_name() already exposes
and records, on each removed source's RemoveFile tombstone, the run it contributed —
compactedInto (the output path) and compactionInfo ({rowOffsetInTarget, sourceNumPhysicalRecords}).
Rows pass through unchanged: no _metadata.row_index, no helper column, no row copy.

sourceNumPhysicalRecords is a physical count, kept self-consistent with the tombstone's own DV;
the live run length is sourceNumPhysicalRecords − |sourceDV|, so a source that carried a read-time
DV has its non-contiguous live rows reconstructed lazily at conflict time. The tags live on the
short-lived tombstone rather than the output AddFile (which snapshot reconstruction replays on
every read), so the read hot path is untouched; tombstone retention (~7 days default) comfortably
outlives the conflict window (a concurrent transaction's runtime), so the tag is still present when a
losing DML reads it.

Safety model

• Opt-in, default off. Every case is behind its own flag; losing a reconcile only restores
  today's abort, so a bug can never produce wrong data — only a spurious (but correct) abort.
• Abort on any doubt. A reconcile proceeds only when the layout is fully captured and every
  affected row maps within its source's run; otherwise the loser aborts exactly as it does today.
• Genuine conflicts preserved. Same file, same rows still aborts; ZORDER / reclustering still
  aborts.
• Each PR is reviewable and revertable in isolation.

Backlog — needs row tracking, not part of this proposal

The reference contract does not reconcile these either, so Phase 1 already reaches full parity;
closing them would require load-bearing row tracking and a scan inside the otherwise-cheap,
synchronous conflict path.

Related work

• [Feature Request][Spark] Row-level concurrency delta-io/delta#7057 — row-level concurrency tracking issue.
• [Spark] Row-level concurrency conflict rebasing delta-io/delta#7306 — concurrent DML ⟂ DML via deletion vectors (row-tracking-gated). Overlaps
  Case 2; this umbrella's Case 2 proposes a deletion-vector-only path that does not require row
  tracking, and the remaining cases (compaction, append, reader-side skipping) are additive. Happy
  to coordinate.
• [File-level concurrency] Exclude no-data-change (OPTIMIZE) files from append-only conflict checks delta-io/delta#7331 — Case 3, already open.

Notes

Clean-room: this proposal cites only Delta's public row-level-concurrency contract and our own
black-box observations of its published behavior; it copies no proprietary source. Case 4's
composition carrier uses the compactedInto / compactionInfo tombstone-tag format so an OPTIMIZE
written by another engine can be reconciled against on a shared table; that interop is modeled on the
published format and is best-effort, not a verified guarantee (an unrecognized tag only forgoes the
reconcile — never wrong data).