merge.md

Branch merge

Audience: engine contributors Authority: current merge routes and invariants; public conflict behavior is in the user merge guide

Omnigraph::branch_merge performs a graph-level three-way merge from the source branch into a target branch. The merge base, source, and target are resolved once; final publication revalidates their exact graph and native-ref identities.

Per-table decision

For every table lifetime present in the accepted catalogs, merge compares:

• the table visible at the merge base;
• the source result;
• the current target result.

Stable table/incarnation identity decides whether entries belong to the same lifetime. Aliases and paths are not merge identity. A rename preserves a lifetime; drop/re-add is a different declaration even if the name is reused.

The table classifier chooses one of four routes:

1. No change: source contributes nothing.
2. Pointer adoption: target still equals the base and the exact source table state can become the target's visible pointer without copying rows. A first-touch lazy target stays on this ref-only route.
3. Proven insertion replay: target still permits data replay and the complete retained source interval proves a contiguous sequence of exact-ID, insertion-only transactions.
4. General merge: compare base/source/target through proven lineage candidates or an ordered full walk, and stage the selected delta.

An optimization miss is not a merge failure. Missing transaction history, unknown certificate fields, or an unfamiliar Lance shape falls back to the general route.

On the adopt route, every named target selects the source's exact table ref, version, and metadata, including when the target already owns a fork. Main keeps its data-delta route for a source on a named ref. Numeric table versions are not compared across refs: the publication's manifest version orders the registration within the graph branch (RFC 0062).

The source's owner metadata stays with an adopted pointer. A later target write creates a unique target-owned fork from the accepted source version. Old target forks remain available to other branches and native descendants; explicit cleanup reclaims only forks outside that protection set. Pointer adoption still computes any required validation delta and runs the shared constraint evaluator.

Proven insertion route

The internal omnigraph.insert_absence = "v1" transaction property says that the filtered physical IDs were proven absent from that transaction's effective parent. Merge accepts it only when every version in the complete source interval is present and structurally proves:

• one exact previous-version link and transaction UUID;
• an insertion-only filtered Update over exactly physical id;
• no removed/updated fragments or unrelated maintenance effect;
• complete nested schema/index-coverage metadata;
• physical-row totals matching the manifest delta;
• exact source and target native branch incarnations under the final gates.

History proof reads transaction records directly with an ordered window of eight reads and a 1,024-version limit; it does not open a Dataset for every historical version. Missing or unprovable history falls back.

The route stages bounded immutable fragments, then commits the same certified filter-bearing Update shape. It performs no target MergeInsert join or target ID preflight. The marker is not a signature and raw Lance writers remain unsupported. RFC 0023 owns the detailed proof and performance evidence.

General route

The merge_lineage session setting at on (the release default, verify in a debug build; request scope, process default OMNIGRAPH_MERGE_LINEAGE, read by the merge from its session) derives candidate IDs from compatible pinned fragment and deletion metadata. Deletion differences remain compressed until bounded offset chunks are needed; known positions use direct reads against the pinned before-image. The 32 MiB candidate budget is checked before keys are copied. Candidate row filters may still scan data when a usable ID index is absent. A proof or budget miss falls back to the ordered walk. off uses that walk directly; verify executes both classifiers and compares their results.

The fallback is an ordered three-way cursor merge. Each cursor streams one snapshot's rows in id order in two phases so no payload column ever reaches a SortExec input:

• a narrow ordered scan sorts only id + _rowid + _rowaddr (8,192 rows and 32 MiB per decoded batch as targets — a few dozen bytes per sorted row);
• sorted keys are hydrated back into complete rows in bounded chunks through an unordered, fragment-scoped scan filtered to the chunk's exact _rowaddr set against the same pinned dataset. Every retained batch is compacted and hard-charged as it streams; a chunk that crosses the 64 MiB retained ceiling is dropped mid-stream and retried with half the rows, so peak hydration memory is the ceiling plus one in-flight scanner batch for any row-width shape — the width estimate that plans chunk sizes only reduces retries, it is never load-bearing for the bound. A single indivisible row wider than the ceiling still hydrates alone;
• Blob columns hydrate as descriptors; Blob-bearing rows are materialized under the same operation budget;
• selected new IDs stage as strict inserts, existing IDs as known-present updates, and removals as deletes;
• the transaction plan is pre-minted and bounded before recovery arm;
• selected validation deltas share one operation-wide memory budget.

Logical conflicts are computed before effects. Value constraints, uniqueness, referential integrity, and cardinality run through the shared validator against the target plus the complete selected delta.

Cost model

Route selection determines the cost class. For one table, let N be the live rows in an input image, delta the selected rows, K the retained source versions, and C the bounded publish chunks.

Route	Classification	Publication
Pointer adoption	Metadata-only when no validation delta is needed; otherwise the delta may require base/source ordered scans	Manifest-pointer change; no table fork or row copy
Proven insertion replay	Walk K <= 1,024 transaction records and scan only the certified source interval	C <= 1,024 join-free fenced inserts; no target ID preflight or MergeInsert join
Adopt with delta	At least two full ordered scans, base and source	New rows use preflighted fenced inserts; changed rows use update-only KnownPresentUpdate; deletes are chunked
General three-way	Lineage candidate discovery and filtered reads when proven; otherwise at least three full ordered scans	New rows use preflighted fenced inserts; existing rows use KnownPresentUpdate; deletes are chunked

Strict insertion keeps Lance's index-disabled, filter-bearing path so the transaction carries the exact-id conflict proof. KnownPresentUpdate can use an id index when its coverage is safe, falls back to the full join otherwise, and never inserts.

Every ordered cursor asks Lance to sort the full table by logical id. The sort is O(N log N) and consumes all input before producing its first row. An id BTREE accelerates filters but does not provide ordered enumeration, so it does not remove this sort. Only the narrow key projection enters the sort; payload columns (vectors, wide strings, Blob descriptors) are read once through the bounded hydration takes, so row width raises hydration read cost but not sort or spill cost, and a pre-existing wide row cannot fail an unrelated merge at the sort's single-row cap.

Ordered scans run in a bounded spill context: each execution has a 150 MiB memory pool, a 100 GiB scratch quota, and a 37.5 MiB cap on the batches fed into a sort. If spilling is disabled, the scratch quota is exhausted, or an indivisible row exceeds the hard cap, merge fails loudly; it never returns a partial result. A hard-cap failure reports the byte count Lance measured (the limit + 1 sentinel survives only for an unparseable upstream message), and cursor-context failures name the table and base/source/target snapshot role. The 8,192-row and 32 MiB scanner settings are batch targets, not hard decoded-batch limits.

Validation is delta-scoped and retains at most 32 MiB of projected scalar state. Usable physical indexes reduce uniqueness and relationship probe cost; missing coverage falls back to scans without changing correctness. Tables and chunks publish sequentially inside the one recovery envelope, and all routes defer index construction to reconciliation.

Cost tests cap common fast-forward manifest opens/scans at three and diverged merges at four, five for a non-bound target. Each scan still folds the surviving append-only __manifest history. optimize can reduce fragment overhead but does not make journal decoding independent of retained history. The decoder reduces one Arrow batch at a time rather than retaining the complete batch collection.

Successful local publication preserves the existing coherent projection after lineage adoption, avoiding a full reconstruction on the next unchanged refresh. The publisher still reads historical records needed for its validation; its fold consumes those maps instead of copying them. Cold opens and publication therefore remain sensitive to retained history. See captured authority for the freshness and fallback rules, and the small cache/layout controls in the benchmark guide to separate these costs.

Diagnosing a slow merge

MergeWriteProbes is a task-local test and benchmark seam; production leaves it unset, so timing does not read the clock. Its top-level timing flow is:

OuterPrepare -> ((ProvenInsertHistory -> ProvenInsertPlanScan) | TableWalk) -> CandidateValidation -> FinalRevalidation -> RecoveryArm -> PhysicalPublish -> RecoveryConfirm -> ManifestPublish -> RecoveryCleanup -> OuterRestoreRefresh.

The parenthesized classification routes are chosen per table, so a mixed-table operation can record both route families. TableWalk covers one general classifier (lineage candidates or ordered fallback) and delta staging; for Blob tables it begins after the operation-wide descriptor preflight. KeyedStage and KeyedCommit are sub-buckets of PhysicalPublish. merge_timing_snapshot reports total, maximum, and exact interval count for every phase; the count remains meaningful when a short duration rounds down to zero microseconds. Structural probes identify the chosen data path. The columns below correspond to ordered_cursor_scan_calls, stage_fenced_insert_calls, stage_known_present_update_calls, stage_merge_insert_calls, and strict_insert_preflight_calls:

Route	Ordered cursors	Fenced inserts	Known-present updates	MergeInsert upserts	Strict-insert preflights
Proven insertion replay	0	C	0	0	0
Adopt with delta	at least 2	insert chunks	changed-row chunks	0	insert chunks
General three-way	0 for lineage candidates; at least 3 for ordered fallback	insert chunks	updated-row chunks	0	insert chunks

Blob descriptor selection can add cursor passes, so the fallback counts are lower bounds. Debug verification runs both classifiers; use the completed classifier counters to distinguish it from either single route. Candidate scan-row, exact-address-take, and provenance-read counters expose work that ordered-cursor counts do not measure. Other useful signals are:

• high ProvenInsertHistory means the retained transaction walk dominates;
• high ProvenInsertPlanScan means scanning or materializing the certified source interval dominates;
• ordered cursors on a named-target pointer adoption can be required for validation; on a main-target insert replay they indicate a provenance miss;
• high KeyedStage means target lookup/join or Blob materialization dominates;
• high ManifestPublish with a tiny delta points to manifest history or CAS retries;
• validation projected-byte counters expose pressure on the 32 MiB delta budget, while Blob payload and external-probe counters isolate object cost.

The probe set also records requested cursor batch bounds, raw proven-insert batch sizes, and legacy whole-delta scans. stage_vector_index_calls and scan_staged_combined_calls should remain zero on current merge routes.

Conflicts

The engine reports structured conflict kinds:

• DivergentInsert
• DivergentUpdate
• DeleteVsUpdate
• OrphanEdge
• UniqueViolation
• CardinalityViolation
• ValueConstraintViolation

Conflict detection never silently picks a winner. The HTTP layer maps the structured result to its public 409 representation.

Publication and recovery

A merge with physical table effects uses one BranchMerge recovery sidecar. Its complete intended delta includes pointer-only siblings as well as the physical effects. Unique first-touch names and owners are fixed in that sidecar before native creation. A merge containing only pointer changes needs no table effect sidecar. Both routes publish the target through one manifest CAS.

After recovery arm, a failed table link or publish retains recovery ownership and returns RecoveryRequired. Merge does not re-run semantic classification around a committed prefix. Full recovery either publishes the complete confirmed result or compensates the owned partial set before visibility.

Outcomes

MergeOutcome is one of:

• AlreadyUpToDate — source adds no target-visible change;
• FastForward — the target adopts source state without a divergent three-way result;
• Merged — a productive three-way merge publishes a new graph commit.

Owners

• crates/omnigraph/src/exec/merge.rs — classification and execution.
• crates/omnigraph/tests/merge_truth_table.rs — operation-pair semantics.
• crates/omnigraph/tests/merge_fast_forward.rs — pointer/proven-insert routes and bounded fallback.
• crates/omnigraph/tests/branching.rs — branch identity and Blob behavior.
• crates/omnigraph/tests/merge_cost.rs — delta scope and manifest-history cost contracts, not semantics.
• crates/omnigraph/src/instrumentation.rs — route and timing probes.

See writes.md, recovery.md, and RFC 0023.