RFC 0016: Equality and range indexes

• Date: 2026-07-10 (reverse iteration settled 2026-08-08)

Summary

Adds a moraine-native equality index: a catalog object (create_index / drop_index on the RFC 0003 verb surface) whose entries live in a new index subspace and serve two reads — row identity (key values → stable row ids) and uniqueness enforcement at commit. DuckLake v1.0 models no indexes, so this is a native feature: real inside moraine, invisible to every DuckLake catalog scan. Entries are live-only (no temporal versioning) and point at row ids, which DuckLake preserves across flush, update-rewrites, and compaction — data movement never touches the index. Uniqueness rides SlateDB’s write-write conflict detection: a unique entry’s store key is the key value, so racing commits inserting the same value collide mechanically and the loser resolves to a typed Constraint under RFC 0004’s ordinary retry. Rows moraine holds are indexed automatically; externally written Parquet is covered by writer-supplied entries at registration (embedding API) or by moraine’s scoped read of the registered file (extension path). Builds too large for one commit run staged: the definition lands in a building state, backfill streams in bounded batches while writers maintain entries from day one, and a final commit flips the index ready (Staged builds).

The index is ordered. The canonical encoding is order-preserving for every type, so the same index storage answers comparison queries (<, <=, >, >=, BETWEEN, half-open) as a bounded sub-scan — equality is the degenerate closed [v, v] case. Each column carries a declared direction (ASC/DESC, realized by complementing its framed bytes, so an ascending store scan yields the declared order) and a NULL placement (NULLS FIRST/LAST). A descending store scan serves the exact opposite order from the same index. None of this adds a maintenance path: coverage, staged builds, uniqueness, and the scoped read are unchanged — they just call the ordered encoder (Range and comparison queries).

The store is one index; the ways in are two. The embedding (verb) API creates and maintains indexes directly — the bulk of this RFC. The extension path reaches the same index storage from DuckDB SQL through registered moraine functions, and covers DuckLake-written Parquet by the scoped read, which also enforces uniqueness over SQL writes. DuckLake-native CREATE INDEX belongs to DuckLake, which owns the user-table binder and refuses index DDL before moraine is consulted (Extension path).

Goals

• An index covers all live rows of its table — inlined, flushed, and externally registered — or refuses the operation that would breach that; uniqueness that silently under-covers is worse than none.
• Index maintenance rides the commit it belongs to: entries land in the same single WriteBatch (RFC 0002 atomicity invariant), and a unique violation aborts the commit that caused it, never a later one.
• Flush, compaction, and update rewrites — every operation that moves a row without changing its identity — cost the index zero writes.
• Concurrent appends to one indexed table keep RFC 0004’s append-append benignity unless they actually collide on a unique key value.
• Reads are consistent: a lookup and the snapshot it serves reflect one cut of the store (RFC 0009 pinned handles).
• Stores that never create an index are byte-identical to stores built before this RFC, and remain readable by older binaries.

Non-goals:

• Serving DuckLake’s planner transparently. DuckLake owns the user-table binder and optimizer. The extension path integrates through an explicit surface — registered functions and the scoped read — never downstream ducklake_* changes or a planner fork. Requests for a supported upstream integration live in ../ducklake.md.
• Locale/collation-aware order. String order is DuckDB’s default binary (bytewise) order; collation-sensitive ordering is out of scope.
• Approximate structures (bloom filters, zone maps) — they cannot carry uniqueness; RFC 0013’s pruning stance already covers the skipping use case.

Background

DuckLake v1.0 has no index tables, so an index cannot be smuggled in as another row-faithful ducklake_* mapping — it is moraine inventing a capability, and the honest shape for that is a native feature stored where no catalog scan (current or time-traveling) can see it.

Three established facts carry most of this design:

• Row ids are stable identity. DuckLake allocates row ids per table (next_row_id in tstat, RFC 0004) and preserves them across inline flush, UPDATE’s delete-and-rewrite, and compaction — row lineage. Ordinary files derive dense ids from row_id_start; rewrite and flush files may instead carry arbitrary preserved ids in _ducklake_internal_row_id. The row id is therefore the durable join key, while physical placement and delete application remain DuckLake’s responsibility.
• moraine does not read Parquet on the scan path (RFC 0006 non-goal) — merge-on-read, lineage, and pushdown are DuckLake’s. On the embedding API it sees row contents at exactly two moments: inline_insert and flush (moraine writes that Parquet itself); entries for external rows are writer-supplied, like file column stats. The extension path adds one bounded exception: projecting the indexed columns of a freshly registered file (Extension path) — a raw-value projection with no merge, not the scan path the non-goal guards.
• Write-write conflict detection is the store’s only race primitive (RFC 0004): no read-write detection, no key CAS. A design that needs “detect that someone else inserted this value” must arrange for the race to be a write-write collision on one key.

Design

The index definition — a catalog entity

A new index kind in current/history, keyed (table_id, index_id) with index_id allocated from the global next_catalog_id. The value carries the index name, the ordered list of indexed columns referenced by field id (never by name — the RFC 0012/0013 rule, so renames are free), the unique flag, and begin_snapshot. Staged builds add a state field and a build cursor to the same value (Staged builds); a definition without a state field is ready, so single-commit creates are unchanged on disk. The definition is temporally versioned like any entity — time travel reconstructs which indexes existed at snapshot S — even though entries (below) are not.

Verbs on Transaction:

Verb	Effect
create_index(table, name, columns, unique)	Insert the definition; build entries for every live row (see Coverage) in the same commit.
drop_index(index)	End the definition into history. Entries are orphaned and reclaimed lazily (see Reclamation).

ReadScope exposes indexes_of(table) and index_by_schema_name(schema, name); domain types include IndexId and IndexInfo. New index names are case-insensitively unique within a schema, checked inside the creation commit for both SQL and embedding callers. The physical definition remains table-scoped. Older catalogs with duplicate names remain readable; schema-level resolution refuses ambiguity, and the table-qualified Rust API can remove the ambiguous definitions.

Commit classification. Index DDL is recorded in changes_made as altered_table:<table_id> — DuckLake’s parser throws on unknown kinds (RFC 0004), so the entry must use vocabulary it parses. altered_table is also correct, not just parseable: an alter truly conflicts with concurrent inserts, deletes, and other alters, in both directions — exactly what index DDL needs. A create_index racing a register_data_file must not win mechanically (its backfill was staged against the old file set), so the race aborts as CommitConflict and the caller re-drives with fresh backfill. For coherence with DuckLake’s own classification (every alter bumps), index DDL sets schema_changed; the cost is one spurious schema-cache refresh per index DDL.

Column DDL on indexed columns. drop_column and alter_column (type change) on a column a live index references fail with Constraint — the canonical encoding is type-bound, and a silent cascade would discard an object the host created deliberately. Drop the index first. rename_column is unaffected (field-id references).

The index subspace and entry keys

A new subspace, one leading discriminant byte appended to the Key enum — a SlateDB segment of its own (RFC 0002), so entry churn from a hot indexed table compacts independently of the metadata subspaces, the same isolation inline gets. Golden vectors pin the discriminant like every other kind.

Kind	Key components	Value
index/unique	index_id, canon(key values)	row_id
index/multi	index_id, canon(key values), row_id	(empty)

Two shapes, one deliberate asymmetry:

• Unique entries key on the value alone. The store key is the claim of uniqueness. Two commits inserting the same value — the race no read-side check can close, since SlateDB detects write-write conflicts only — write the same key and collide in the store’s own conflict detection. The loser retries per RFC 0004, re-runs its closure, sees the winner’s entry, and returns Constraint. Uniqueness under concurrency is correct by construction, with zero new race machinery.
• Non-unique entries append the row id, so rows sharing a value occupy distinct keys: concurrent appends of different rows write disjoint entry keys and stay benign under the append-append refinement — indexing a table does not serialize its writers. A lookup for v is the ascending prefix scan index/multi/{index_id}/{canon(v)}/ (RFC 0002 forward-only).

index_id-first keying makes each index one contiguous range — the unit lookups scan and drop orphans (Reclamation).

Canonical value encoding

Entry keys embed column values — a deliberate, bounded exception to RFC 0002’s “no strings in keys” rule, which exists so entity keys stay rename-stable; an index key’s whole job is to be the value. The contract is canonical and order-preserving bytes, per DuckLake column type (encode(x) < encode(y) as unsigned bytes iff x < y in the type’s SQL order), pinned by golden vectors and proptest roundtrips like every other store codec:

• Integers: fixed-width big-endian, sign bit flipped; widths normalized per the column’s type. Order-preserving.
• Strings/blobs: the UTF-8/raw bytes, storekey-escaped so component boundaries stay unambiguous in composite keys; bytewise order is DuckDB’s default binary order.
• Floats: -0.0 normalized to +0.0 and every NaN collapsed to one pattern, then the standard total-order transform (flip the sign bit of a non-negative value, all bits of a negative one) so the big-endian bytes sort numerically, with NaN greatest.
• Temporal types: their underlying integer representation.
• Composite indexes concatenate component encodings in declared column order; storekey tuple framing keeps ("ab","c") distinct from ("a","bc") and preserves order (a shorter value sorts before its extension).

Direction is per column. A DESC column stores the bitwise complement of its fully framed component (terminator included, so variable-length values reverse correctly — "ab" < "a"); the leading NULL flag is not complemented, so NULL placement is independent of direction. An ascending scan yields the declared composite order and a descending scan yields its exact opposite, both directly from SlateDB’s iterator.

NULL placement is per column (NULLS FIRST/LAST). Each column’s component carries a leading flag byte separating NULL from non-null, ordered per the placement. A row with a NULL in an indexed column is stored — so IS NULL can find it (Range and comparison queries) — but always multi-shaped (the row id is in the key) and exempt from the value collision: SQL treats NULLs as distinct, so a unique index still admits any number of NULL rows. An equality point lookup on NULL still has no answer (= NULL is unknown); NULL rows are reached only through IS NULL.

The explicit read surface deliberately keeps comparison and NULL scans separate. index_range clamps open sides to the non-null region, while index_nulls emits only the matching NULL subrange in either scan direction. It does not combine the two into an ORDER BY … NULLS FIRST/LAST result; that behavior belongs to any future DuckLake planner integration, not this API’s contract.

Oversized values are refused. Indexed values beyond a fixed cap fail with Constraint at insert/registration — huge keys degrade the whole segment, and equality over megabyte values is not this feature’s job. Hash-overflow is rejected for v1.

Coverage — who writes entries, and when

Coverage is total over live rows, maintained at the three moments rows enter, and the two moments they die. Who computes an entry depends on who wrote the rows, which differs between the two paths:

Moment	Who has the rows	Embedding API	Extension path
inline_insert	moraine (rows arrive through the API)	computed by moraine, staged in the same batch	same
flush (RFC 0005)	moraine (it writes the Parquet)	nothing to do — entries point at row ids, which flush preserves	same
register_data_file	the writer	writer-supplied: (row ordinal, key values) pairs alongside the file, mapped to row ids at commit (row_id_start + ordinal) — or (row_id, key values) for rewrite files that preserve row ids — like the file column stats the writer already computes	moraine reads the file
inline_delete of a store-resident row	moraine (the chunk is in the store)	moraine recomputes the key values from the chunk and stages the entry delete	same
register_delete_file, or inline_delete against flushed rows	the writer (it read the rows to produce positions)	writer-supplied: (row_id, key values) per deleted row; moraine deletes the named entries	moraine reads the delete file

The embedding-path rule generalizing the last two: any operation that kills rows moraine cannot read from the store must name their indexed key values — entries are keyed by value, and moraine cannot derive a value from a row id it cannot dereference. (The extension path lifts that premise by reading the file.)

Registration without entries is refused. A register_data_file or register_delete_file on an indexed table that omits the required entries fails with Constraint — a silently under-covered unique index is a lie (mark-stale is recorded in Alternatives).

DuckLake registrations read instead of refusing. The refusal above is the embedding-API contract: the writer computes entries as it computes stats. A DuckLake staged registration carries no entries by construction, so on any indexed table moraine derives them by the scoped read (Extension path) — however the index was created. Reject-vs-read splits by who writes, not by which API made the index.

So on the extension path every entry is moraine’s own work: it opens the registered data file, or the delete file and then the rows it names, and computes the key values from the rows themselves. Nothing a writer asserts is taken on trust, because no writer asserts anything.

A data store is mandatory for an indexed table on that path. Deriving entries needs the file, so a commit registering a data or delete file on a table that carries a maintained index fails Constraint when the attach supplied no DATA_PATH store, naming the file it could not read. The index is never quietly left short: the commit does not happen. create_index is fail-closed at the other end for the same reason — a table that already holds files cannot be indexed without a store to backfill from. So an attach with no META_DATA_PATH can carry an indexed table only while its rows stay inlined, and a test written that way exercises none of the file reads above.

An UPDATE on the verb path (expire + register preserving row ids) composes: the delete side removes old entries, the insert side adds new — same commit, same batch, uniqueness checked against the post-image.

Backfill at create_index. Rows moraine holds (inlined, any schema version) are backfilled by scanning the chunks. Rows in external files need writer-supplied backfill entries passed to create_index — except through CREATE INDEX, which has no writer and backfills by scoped-reading every live data file of the table, so its build cost is the table’s indexed columns, and the one-commit bound bites hardest exactly there. The reader overlaps a fixed number of immutable files and sends bounded Arrow batches through a bounded channel, so it retains no complete per-file result sets. The transaction still owns the table-wide encoded entry set: the whole build is one commit and one atomic batch, uniqueness is validated over that assembled set before staging, and a duplicate aborts the create. A backfill that exceeds the store’s batch bound fails typed before staging anything, and the caller re-drives as a staged build (Staged builds).

Uniqueness enforcement

At commit, for each new unique entry the committer point-gets the entry key through the transaction handle (RFC 0004 step 1’s read discipline): present with a different row id → Constraint; present with the same row id → no-op (a re-derived entry for a rewrite file, Extension path); absent → stage the put. Duplicates within the commit are checked in memory. The race window between the get and a concurrent commit’s identical put is closed by the key collision described above — that is the load-bearing property of keying unique entries on the value alone.

Because entries are live-only, “present” means “a live row holds this value”: deletes remove entries in the same batch that kills the row, so delete-then-reinsert behaves as SQL expects, within one commit or across commits.

A unique entry’s key is the value alone, so a delete by key removes whichever row holds the value. A deletion supplied by a writer through the verb API is therefore guarded: the committer reads the entry and drops the deletion unless the stored row id is the row being removed. A deletion the committer derives itself — from a scoped read of a delete file’s target or a dropped file, or from an inlined row — names a row live at the base snapshot, and while the index is ready no other row can hold that row’s value, so it is staged without the read. A building or poisoned index may hold the value for another row, so its derived deletions keep the guard.

The rejection names the index, the claiming row, the holding row, and which state it collided with — the commit’s own additions or a row already indexed. Those two branches otherwise produce the same message from different causes, and a holder that is not live says the index holds a stale entry rather than the table holding a duplicate. It names no indexed value: errors on this path carry shapes and counts, never key data.

The Constraint here is a verb-path error (embedding API) — no DuckLake wire contract applies to its text. It is nonetheless worded free of the four substrings DuckLake’s commit loop retries on, so a rejected bulk INSERT surfaces at once rather than being re-run (RFC 0006’s wire contract).

How the probes run. A bulk load stages one entry per indexed row, so this step decides whether a large commit is minutes or hours, and whether it fits in memory at all. These properties govern the implementation:

• One probe per distinct key, not per entry. Repeats within a batch collapse in memory; two entries claiming one value for different rows collide there, before any read.
• Bounded concurrency of point reads. Ready additions form chunks of at most 128; a pending source flushes a partial chunk rather than delaying it. At most 1,024 logical uniqueness probes are in flight, each a transactional point read. Probe futures have concrete types, with no per-probe BoxFuture. A point read’s cost is bounded by the sources the key could be in: an absent key is answered by each SST’s filter, and a data block is fetched only on a hit. A shared range scan over a chunk’s key span was tried and withdrawn: it saves CPU on an in-memory store, but it opens every overlapping L0 SST and sorted run per chunk with no filter to rule any out, so its cost is set by the store’s shape rather than by the chunk, and on a remote store that turned a sorted build’s commits into minutes. A put’s expected outcome is a miss under any index — a hit is the same row again or a violation — so the scan optimised the exception at the expense of the common case.
• Every commit staging index entries reports how its probes were served — count, hits, misses, known-absent puts, peak in flight, window and service time — at info when an entry targets a building index and at debug otherwise.
• A build probes only keys its filter has seen. The driver keeps one bloom filter over the physical keys it has staged (Staged builds), and a unique entry whose key the filter has never seen is staged as known absent: the planner records its claim, so two such claims of one value in a commit still collide, and stages the put with no read. A positive probes as before. The filter is sound because every key that can be in the index is either one the build staged, or one a writer put for a row inserted after the definition, and the build derives that row too — its source is newer than the cursor — so the pair collides on the probe when the build reaches it. A key the filter never saw therefore belongs to no live row. Single-key batches remain point reads. Both modes use the original transaction, preserving its snapshot, local writes, tombstones, and merge semantics. Outcomes are applied as batches complete; the first surfaced error aborts the commit.
• Entries stage onto the transaction directly. They never enter the write list the committer retains for the maintained projections. No projection reflects an index entry, so retaining them would hold a second copy of the batch’s largest part in memory for nothing.

The deletion phase still completes before any addition is staged. While it runs, additions keep being derived and planned, and at most 512 of their logical probes are launched (1,024 once deletions are done); the rest wait planned in memory. The windows bound what is launched, never what is polled: every stream the stager owns is driven on every wait, in both phases. A derivation left unpolled can hold what a deletion waits on — a permit the encoding limiter has assigned to its queued waiter, or a block read the store coalesces on its first reader — and hold the commit forever. The commit’s entry budget bounds what the run-ahead can buffer, and the transaction’s write batch holds every staged entry until commit anyway. Telemetry continues to count logical probes, hits, misses, and peak logical concurrency; summed probe service counts a shared read batch’s interval once (including any sparse-key fallback), while batches planned as point reads retain their individual service intervals.

Physical key builders reserve the exact outer-framed size as each component arrives, including the row-id suffix only when required. Canonical and physical bytes stay unchanged, including escaping, direction, NULL placement, and the unique-to-multi transition on NULL. Existing encoding property tests remain the compatibility oracle.

Every catalog batch rewrites sys/head, including head-preserving maintenance, and the store admits only one writer process. Tracking every index key cannot reject a commit the head collision would admit, but SlateDB 0.16 nevertheless materializes the batch’s complete key set for conflict detection. It also clones the transaction’s write batch at commit. Moraine accepts that upstream behavior and bounds the resulting peak with count and encoded-byte limits.

Commit size is bounded, and why it must be

Direct measurement with 49-byte keys attributed about 250 bytes per entry while staging and about 1.2 KiB per entry at commit peak. The latter included SlateDB’s write-batch clone and conflict-key materialization as well as WAL and memtable work; it was not the encoded key size and was not all retained after the commit.

A commit’s footprint is therefore set by how many entries it stages, and a bulk load stages one per indexed row per index — memory proportional to the whole table. Tens of millions of rows ask for tens of gigabytes, and the failure mode is not an error but a thrash: swapping, no progress, nothing logged. So stage_index_entries refuses a commit above MAX_INDEX_ENTRIES_PER_COMMIT before doing any work, with a message naming the count, the limit, and the remedy — split the load. The limit is one million entries. A second 64 MiB ceiling over encoded index key and value bytes protects the same path from fewer unusually wide keys and is checked before each write enters SlateDB’s batch.

The refusal’s text avoids DuckLake’s four retry substrings, as the uniqueness rejection does: it is terminal, and re-running it reaches the same answer more slowly.

Both limits are fixed safety invariants, not CatalogOptions fields. A caller cannot raise it and turn a bounded commit back into memory thrash; workloads above it must split the load or use a staged build. Changing the limit or making it configurable requires new measurements and a new design decision.

The extension asks DuckDB to flush its allocators after a successful staged commit with at least 100,000 equality entries or 64 MiB of encoded batch data, and after a failed staged commit. DuckDB’s flush also trims the system allocator used by the Rust static library. This does not change live-memory accounting; it returns free arenas that a large commit would otherwise leave in process RSS. Ordinary small successful commits avoid the global flush.

The remedy the refusal names — split the load — is only available to a writer that chooses its own batch boundaries. A DuckLake maintenance call does not: ducklake_merge_adjacent_files decides for itself how many files one snapshot merges. A commit that derived an entry per merged row would therefore hit an unsplittable refusal, and an indexed table past a few million rows could never be compacted again. It derives none (Compaction derives nothing), so the limit binds only writers who can obey it.

Two bounds on a step

Entry count is not the only thing that can make a commit impossible, and the second bound is not a smaller version of the first — they fail differently and are set by different facts about the machine.

The memory bound above is about the process: a kilobyte of write-path memory per staged entry, so a big enough batch thrashes. The transfer bound is about the link. A durable commit becomes exactly one object-store request: the store guarantees a write batch lands in a single WAL object, and WAL objects are written with a conditional single PUT — the fencing they rely on cannot be expressed through the multipart API — so the whole batch goes in one request body. object_store applies its request timeout (30 seconds by default) per attempt to that entire request, upload included. A batch too large to push inside the timeout therefore does not fail: it times out, is retried from the first byte, and is retried beneath moraine indefinitely. It never lands and never errors.

So a staged build step carries two bounds, and ends at whichever it reaches first:

• entries — the memory bound, defaulting to a million.
• bytes — the transfer bound, defaulting to 8 MiB. That clears the 30-second default at a little over 270 KiB/s, which is slower than any link a build has a right to expect.

entries bounds one step’s buffer, not the process: derivation holds the step being filled and the step being committed, plus the fixed read-ahead window described under Staged builds.

A step always carries at least one entry: an entry wider than the byte bound still has to be committed, and a step that admitted nothing would never advance.

At the defaults the byte bound always binds first, and the entry bound never does: an entry costs at least 19 bytes (the entry prefix, a one-byte NULL flag, and the row id), so 8 MiB admits at most about 440,000 of them. The entry bound is therefore not a second safety net at rest — it is what holds when bytes is raised. An operator on a fast in-region link who lifts the byte bound to cut commit count is exactly who needs a step still capped at a million entries, because at 256 MiB the byte bound alone would admit fourteen million and the memory limit above is real.

The byte figure is exact: entries are encoded to their physical keys as they are derived, so a step is measured on the key and value bytes its commit stages, escaping included.

Both are settable per call, because neither default can know the link. The transfer bound is the one an operator on a slow or distant link reaches for, and lowering it is strictly a latency trade: more commits, each cheaper and independently resumable from the cursor.

The commit stall warning reports the batch’s staged bytes for the same reason. A stalled durable write carries no error — the failure is retried below moraine, so there is nothing to report but the wait — and the batch’s size is the one fact that separates a batch that cannot be transferred from credentials that will not authorize it.

Deferred upkeep for non-unique indexes

Synchronous upkeep remains the default: the data snapshot and every index entry land atomically. An index created with maintenance := 'deferred' instead moves additions out of DuckLake’s data commit. This mode is limited to non-unique indexes: unique enforcement cannot acknowledge a row before its value has won the index collision.

When a SQL commit adds rows covered by a deferred index, the same snapshot that registers the rows flips that index from ready to maintaining and persists the repair cursor. It stages no additions for that index. Deletions remain synchronous in every state, so no stale entry survives while a repair is pending. An UPDATE therefore removes the old value in its data commit and leaves the new value for the repair.

maintaining is unavailable, never partially readable: every lookup fails with the same typed building error used by an initial staged backfill. After the data snapshot is durable, the extension drives the ordinary bounded backfill machinery over the missing live rows and flips the index back to ready. Repair failure cannot roll back a data snapshot that already landed; it is logged and leaves the durable maintaining marker for the next SQL commit or moraine maintenance pass to resume. Process loss has the same outcome. The maintenance scheduler repairs maintaining indexes before sweeping dropped ones.

Further writers arriving while a repair runs continue to defer additions and maintain deletions. Intermediate repair steps classify inserted_into_table, so they can advance beside concurrent appends while retaining conflicts with deletes, schema alters, and drops. The final ready flip uses a non-schema-changing altered_table operation, so a racing writer makes the repair re-derive from its durable source cursor rather than publish incomplete coverage. Both operations mint snapshots for durability but add no ducklake_schema_versions rows. Only an index’s initial publication and first build-to-ready flip are schema changes; routine upkeep cannot churn table schema history.

What data movement costs the index: nothing

The entry payload is a row id, not a location. Flush re-homes rows from chunks to Parquet; compaction and UPDATE rewrites re-home them across files; row ids survive all three. Moraine returns that identity directly. DuckLake uses its own file statistics and delete metadata to locate and adjudicate the row under the scan’s snapshot. No maintenance operation rewrites an entry. This is why live-only entries plus row-id payloads is the whole design: every alternative payload (file id, chunk key) turns flush and compaction into index rewrites proportional to moved rows.

Nothing removes a live index’s entries when a data file’s row leaves the catalog, either — the maintenance sweep reclaims only the entries of indexes that are themselves dropped. What keeps that sound is an invariant worth stating, because it is the thing a future data-file lifecycle could break: a file’s rows never leave without either a row-grain deletion having already taken their entries, or a replacement carrying them under their preserved row ids. A rewrite materializes deletes that each removed their entries when their delete file was registered; its survivors keep the entries they already had, untouched, because an entry names a row and not the file holding it (Compaction derives nothing). A merge subsumes its sources. Expiry and cleanup prune rows a replacement already covers. The whole sequence is held to the table’s own answer by the e2e test moraine_index_entries_survive_the_data_file_lifecycle.

A leaked entry would not be silent: the lookup table function exposes the stale row id directly and, under a unique index, the entry causes a bogus duplicate rejection when its value is claimed again. The ordinary DuckLake join still filters that identity when no live row carries it.

Compaction derives nothing

That an entry survives compaction untouched is the payload argument above. The commit path must also decline to re-derive it. A registration on an indexed table is otherwise read and derived unconditionally — the property that keeps coverage total — but under compaction that read costs one scoped read per merged file and one staged entry per row, to write back the index that is already there. At scale it is not merely wasted work: it is more entries than a commit may stage at all (Commit size is bounded), which would leave a large indexed table permanently uncompactable.

The signal is the commit’s own change set. DuckLake refuses to mix compaction with any other change in one transaction — a transaction either makes changes or compacts, enforced upstream where changes_made is built — so a snapshot naming merge_adjacent or rewrite_delete and nothing else re-homes rows and does nothing else to them: no ids allocated (RFC 0008), no values changed, no rows killed. Every entry its files would derive is already stored under the same key, so those files are not read for derivation; the commit reads only their row-id columns, to hold them to their sources (RFC 0008).

The rule is read off the staged ducklake_snapshot_changes row, so what it trusts is the commit’s own account of what it did — the same account the conflict matrix already decides races on (RFC 0004). The fallback is deliberately one-sided: a change set naming compaction and anything else — an append, a delete, a kind this binary does not model — names no compaction-only table, and every registration in it derives as before. Only an account claiming compaction and nothing whatever else skips; every less certain reading pays for the read.

What still derives. UPDATE also writes row-id-preserving files, but its rows’ values change; its commits carry inserted_into_table / deleted_from_table, never a compaction kind, so they derive. Inline flush likewise — inline_flush is a kind moraine does not model, so it can never read as compaction-only — and its output re-derives entries idempotently, bounded by how much data may sit inlined.

Lookups

One accessor family on ReadOnlyCatalog, served through ReadScope::reads() on the pinned read handle so the lookup and its catalog metadata share one consistent revision:

• index_lookup(table, index, key_values) -> Vec<u64> — point-get (unique) or prefix scan (non-unique) in index. Consumers join the returned row ids to DuckLake and let it select files and apply deletes. The extension path surfaces this accessor as moraine_index_lookup.
• index_lookup_many(table, index, keys) -> Vec<u64> — the IN accessor: deduplicate complete equality keys, resolve every distinct key under the same pinned read as one logical lookup, and return the union of their row ids. An empty key set returns no rows after validating the index. The probes run through a continuously refilled bounded window of 512 point-read futures: completion frees one slot immediately rather than waiting for a fixed chunk’s slowest read. The extension path surfaces this accessor as moraine_index_in.
• index_range(table, index, lower, upper) -> Vec<u64> — the comparison accessor (Range and comparison queries). Each bound is Included/Excluded/Unbounded; results come back in the index’s stored order. The extension path surfaces it as moraine_index_range.
• index_nulls(table, index, prefix) -> Vec<u64> — the IS NULL accessor. prefix is a leading run of Some(value) (equality) and None (IS NULL) predicates — [None] is a IS NULL, [Some(5), None] is a = 5 AND b IS NULL. At least one None is required; a gap (an unconstrained leading column, so a bare non-leading IS NULL) is not expressible and is left to a scan filter. Surfaced as moraine_index_nulls.

Every equality lookup emits one index lookup resolved diagnostic event. Durations are integer milliseconds: total lookup, head view, probe wall window, and summed probe service. Counts include requested and deduplicated keys, hits, misses, peak in flight, metadata/block cache deltas, cache errors, and object-store GET count, duration, and errors. The event measures the whole pinned lookup without changing the SQL result surface.

The event carries the same fields at either level: debug records every lookup, and info records the ones that took 250 ms or more, so a host running at its default level sees the slow probes without turning on debug for everything else. The probe window against the summed probe service says whether a slow lookup overlapped its probes or serialized them, and the disk-tier hit counts say whether the blocks it read came from memory.

Lookups, ranges, and null queries are head-only: entries are live-only, so snapshot_at(S) fails with a typed error and time travel falls back to what it always was — a scan problem. The hot path (current head) gets the index; the rare path pays nothing to keep it honest.

Head-only is also what lets a warm read-write handle serve every accessor above without opening a read session: the definition comes from the view the handle already holds, which on the store’s only writer is the head, and the probes are plain reads against the writer’s Db, so no transaction — and no transaction-manager lock — stands under a lookup. A pass the held view moved under is re-run through a session. A read-only handle probes under a session as before. RFC 0009 (A read-write handle resolves the head without reading it) carries the argument.

File-located lookups

A lookup resolves an indexed value to stable row ids as above. It may then locate those rows in the current physical data files, so a DuckLake scan prunes by file id as well as row id.

Physical location is derived cache state. It is not stored in the equality entry, takes no part in the commit protocol, and adds no index subspace keys — compaction and file rewrites leave every entry untouched. That is the same property as What data movement costs the index: nothing, extended to location: the index knows row ids, and where a row id currently lives is recomputable from the head view at any time.

The core returns a located row:

FileRowCandidate {
    row_id: u64,
    data_file_id: Option<DataFileId>,
}

ReadOnlyCatalog::locate_row_ids takes the DATA_PATH DataStore, its path prefix, a table id, and stable row ids, resolving every row against the same head view that enumerates current data files. More than one file may be a candidate for one row id: an update can leave an expired physical copy in an otherwise-current source file while the visible copy is written elsewhere.

None names a live inlined row. A row id in neither a current data file nor current inline data is also returned with None — a conservative fallback, so incomplete cache construction or catalog state cannot hide a row.

The extension surfaces two columns, row_id BIGINT and data_file_id UBIGINT, the latter nullable for inlined or unlocated rows. A consumer joins with null-safe equality on file id and ordinary equality on row id; a caller selecting only row_id is unaffected.

A tuple comparison — (rowid, data_file_id) IN (SELECT row_id, data_file_id …) — is unsafe against these columns: tuple IN compares with plain equality, under which a NULL file id matches nothing, so every inlined or unlocated row silently drops out of the result. As a DELETE or UPDATE predicate that strands the row with no error. The join with null-safe equality on file id is the supported shape.

Resolving a located delete’s positions emits one located rows resolved diagnostic event: requested pairs, the files and positions they landed in, the delete files and existing positions already registered against those files, the summaries the resolution had to build, inlined rows, and the positioning and total durations. It follows the same level rule as index lookup resolved — debug for every resolution, info once one takes 250 ms or more — so a host at its default level sees which half of a slow located delete, the probe or the positioning, spent the time.

Selective row lookup

locate_row_ids uses a per-table interval directory for verified dense file summaries. A cold directory resolves every current file once: row_id_start alone cannot exclude an embedded-ID file. Warm requests visit matching dense intervals and an overlap-aware interval index over arbitrary-ID summary bounds. Only summaries whose inclusive spans cover a requested ID receive a membership check; overlapping spans do not fall back to probing every summary. The same augmented balanced interval representation serves inline chunk lookup. Its immutable array is shared by warm directories and rebuilt from retained bounds only when that summary map changes, without rereading unchanged Parquet files. A lookup re-resolves nothing it has already summarized. Failed summaries still broaden every requested ID to that file. Retries wait 16 lookups initially, doubling after each failure up to 4096; a successful retry moves the file into the directory. File-list refreshes preserve the countdown, so new registrations cannot postpone a failed file’s retry indefinitely. Results preserve request order, deduplicate repeated requests, and retain overlapping physical and inline candidates.

The directory is keyed on the data-store cache identity, data prefix, and table prefix; a change to any of those rebuilds it. A change to the table’s file map refreshes the directory in place: the map it was built from is diffed against the current one, files that left are dropped, and only files that arrived or changed are summarized. A flush, replacement, or expiry therefore costs one summary per new file rather than one per current file, and unrelated catalog changes cost nothing. The directory’s size estimate is carried across refreshes the same way. No file summary is inferred from a catalog range before the footer establishes which row-ID source applies.

The directory also retains exact position summaries, including physical row order for permuted files. Position resolution and scoped row reads reuse these summaries even after auxiliary-cache eviction, provided the store identity, prefixes, and complete registered file record still match. Summary payloads are shared by reference and counted once in directory occupancy; removing or changing a file drops its retained summary.

Inline point lookups build a chunk interval directory, then materialize only requested offsets, scan tombstones only for those IDs, and fetch only chunks holding selected live versions. This path serves both recent_row and inline membership checks used by row location and position validation. A first lookup verifies the persistent directory against the chunk scan; an incomplete directory falls back to metadata from that scan. Further directory builds can read locators without bodies once completeness is established. Cached intervals require the read session’s full head stamp, including the maintenance batch sequence, so updates, flushes, and changes to chunk widths cannot reuse stale ownership. Manifest-following read-only sessions check the full head stamp before and after selection, body/schema reads, and failures. A changed stamp retries from the new head. Only a stable pass installs its directory. After three retries, the reader falls back to scanned bodies without caching, so sustained changes cannot make it re-fetch a body already removed by a concurrent flush.

Each catalog handle retains at most 256 table directories of each kind and evicts the least recently used one when a further table needs a slot, so a working set within the cap never rebuilds. Directory space follows source counts, not expanded row counts, and is included in the catalog projection-memory estimate. File directories share immutable file maps and the arbitrary-ID summaries they retain with the auxiliary cache; the estimate can count both again beside the current catalog projection. Eviction or a cold attach pays directory construction again. This is an in-memory read optimization with no key-layout or format-version change.

File-row sets

One immutable summary describes the physical row ids of one immutable data file, in whichever representation is smallest for that file:

• a half-open dense range, for a file carrying row_id_start and no reserved row-id column;
• a run-optimized 64-bit Roaring set, when it beats the raw ids;
• a sorted u64 vector, when fragmentation makes Roaring larger.

A summary also answers a row id’s positions — its physical ordinals within its file, which a delete file names. Positions are permanent facts of an immutable file, so caching them can never go stale; they are also implicit in the build, which reads the reserved row-id column front to back. Position is order information, and order rides beside the set rather than replacing it — membership keeps whichever representation is smallest, untouched. A dense range answers by arithmetic. For the sparse shapes the set’s rank is the position whenever the file’s ids ascend in file order, which the build verifies while it holds the column; an UPDATE that rewrote rows from several source files emits concatenated ascending runs rather than one ascending sequence, and such a file carries a rank-indexed permutation beside the set — u32 file positions in ascending-id order — so position remains one rank plus one array read. A cached summary from before positions existed carries no order verdict and cannot be trusted with one; decoding treats it as absent, and the next lookup rebuilds it from the file — a one-time cold start, never a guessed position. A permutation over contiguous ids answers no question a dense range could not answer more cheaply, so construction demotes that case to the plain Roaring set instead of pairing a permutation with a range.

A flushed inline file can contain several historical versions of one row ID. These are valid physical rows, not a malformed summary. The membership set deduplicates IDs; a repeated-order directory maps each member’s rank to a range of physical positions through u32 offsets and positions arrays. Exact reads and located deletions expand every position, then apply snapshot-aware delete visibility. This also removes the duplicate-ID summary failure after inline updates and flushes. Repeated-order summaries use new disk-cache tags (14 for Roaring membership, 15 for sorted membership); old tags remain readable and older readers treat the new tags as cache misses. Decoding validates offsets, cardinality, and the physical-position permutation.

A recorded row_id_start does not by itself imply the range: a flushed file carries both a dense start and the reserved column, and that column’s ids may hold gaps a range would invent rows across and, worse, end before — excluding a row the file holds. Which representation applies is therefore a question about the file’s schema, settled by its footer, and only then does a dense file skip reading any column. A miss on any other file reads only the reserved internal-row-id column, and reads of separate immutable files overlap under the bounded concurrency index backfill already uses.

Summaries are built lazily, by the lookup that first needs one. Nothing constructs them at write time, and nothing could cheaply: for a file the catalog numbers itself the summary is the catalog record, and for one carrying embedded ids — a compaction output or a rewrite — moraine holds only the file’s metadata, never its rows, so building at registration would mean reading back the Parquet it was just told about, inside the commit path. A summary is also process-local, and the writer is not the process that reads.

ReadOnlyCatalog::publish_row_summaries therefore exists to move that cost off the first lookup rather than into the commit: a caller spawns it after a commit that lands compaction outputs, and it builds exactly the summaries a cold lookup would. It is best-effort and idempotent — a resident or dense file costs nothing, an unreadable one is counted rather than raised — and warms one process, so a separate reader still builds its own. A pass that never runs changes latency and nothing else.

The summary cache is keyed by store identity, table id, data file id, path, and recorded file size. The store is held weakly, which both keeps the process-wide cache from pinning a catalog alive and separates two catalogs whose table and file ids coincide. Catalog ids are never reused; path and size make stale reuse fail closed even against an imported catalog that violates that. Decoded sparse summaries are byte-budgeted (RFC 0009); range summaries are cheap enough to rederive and take none of the budget.

A batch lookup sorts and deduplicates its row ids once, then intersects each file summary against that set — file-grouped candidates without a per-row location map.

Locating cannot lose a row

Equality entries remain the sole source of indexed values and uniqueness, so the location cache can neither create nor remove a result. Every degraded path broadens the candidate file set: a missing, evicted, unsupported, or failed summary leaves every requested row id a candidate for that file. The optimization may read files it did not have to; it cannot exclude a matching row. Choosing the visible physical copy of a stable row id remains DuckLake’s delete and snapshot processing.

Locating is head-only, exactly as equality lookup is: a time-travel scan consumes neither live-only entries nor this cache.

Locating across the DuckLake file list

The bundled DuckLake patch exposes data_file_id as an internal virtual UBIGINT column. A physical file emits its persistent catalog id as a constant; inlined and transaction-local sources emit NULL.

Static and dynamic filters on that column are pushed into DuckLake’s metadata file-list query as predicates on ducklake_data_file.data_file_id, using no column statistics; row-id filters continue through the existing reserved-field statistics path. A predicate naming both columns therefore restricts the file list and the rows read within the files that survive.

A join condition does not reach that far by itself. A hash join’s runtime filters are generated after DuckLake has built its file list, and DuckDB generates none at all for the null-safe equality the file-id column requires. Left alone, a located join reads every file whose row-id statistics admit the key — which, because each update writes a file spanning the ids it preserved, is every update the table has taken.

An extension optimizer rule first attempts the exact summary-driven scan below. When that scan is ineligible, an index read resolves its rows while binding, so a join against one is a join against a list of constants already visible to the planner; the rule restates that list as an IN filter on the other side of an inner or semi join. The filter only repeats what the join enforces, so it is added beside the join rather than replacing it: whatever the query projects from either side is unaffected, and an outer join — which keeps rows meeting no condition — is left alone. A file id resolved as NULL contributes an IS NULL disjunct under null-safe equality and nothing under plain equality, matching what each comparison would have accepted.

Prepared index plans use the dependency validation described below in Snapshot-validated index plans.

Each derived list is bounded, and the bounds differ by what evaluating the list costs. Up to 256 distinct row IDs retain the ordinary derived filter. From 257 through 4096, the sorted IDs become at most 16 optional pruning ranges attached directly to the DuckLake scan. The largest gaps separate ranges; smaller gaps are merged, admitting extra candidates that the join rejects. This bounds both scan-filter cost and DuckLake’s generated metadata predicates, without a per-row residual IN expression. Dense probes use one range. Above 4096 the rule declines row pruning and leaves any dynamic row-id filter available. The file-id list dedups to the files holding the rows and is checked against each file’s constant id, not against every row, so it stays worthwhile far wider — its much larger bound only keeps a pathological plan bounded. A wide probe over a churned table is exactly the case that needs this: near one row per rewrite file, the distinct file ids grow with the probe, and the file-id list is the only filter that names files exactly rather than testing row-id spans.

The rule runs after DuckDB’s own optimizers, because that is when every qualifying join exists: a SELECT writes its join directly, but DELETE … USING and UPDATE … FROM bind theirs through the WHERE clause as a filter over a cross product, and an EXISTS probe as a dependent join — both formed into comparison joins only during optimization, the latter flattened to a semi join over a projection of the lookup that the rule looks through. The built-in filter pushdown has already run by then, so the rule pushes the derived filter down its own subtree, landing it in the scan as table filters. A semi join is also the shape that most needs it: DuckDB generates no runtime join filters for one, so the derived filter is the only pruning an EXISTS probe gets, and only within the bounded list length.

The current DuckLake catalog view stays authoritative for file lifetime. Ended compaction inputs are simply absent, new outputs are cache misses, and nothing pairs sources with outputs or hooks catalog changes.

Ordinary predicates reach indexes through the rule

The optimizer translates pushed constant predicates into conjunctive column comparisons: equality or IN, lower and upper bounds, and IS NULL. The core selects a ready index with the longest usable prefix, reorders predicates into index-column order, and expands independent equality lists into complete keys, bounded to 4096 combinations. Full keys use batched point probes; an incomplete equality prefix or a final range uses an ordered scan; a prefix containing IS NULL uses the NULL-prefix lookup. Unsupported predicates remain residuals. The original SQL predicate remains evaluated over candidate rows.

ReadOnlyCatalog::index_predicate_rows(snapshot, table, predicates) accepts IndexPredicate { column, comparison }, where IndexComparison represents an equality list, NULL, or inclusive/exclusive lower/upper bound. It returns None when no ready index covers a leading predicate, otherwise candidate row IDs and whether a certified index answered every supplied predicate exactly. The call requires the pinned scope owning snapshot. The extension’s internal moraine_index_predicate_rows ABI translates typed SQL constants to this API; it replaces the single-column equality-only ABI.

A certified full-key probe can also feed positional DELETE, but only if the entire scan predicate was translated and no residual operator survives. Tuple equality and tuple IN first expose implied per-column choices before DuckDB rewrites lists into joins. The original tuple predicate remains, rejecting cross-products and preserving row-NULL semantics. A residual tuple filter directly above a scan also supplies its choices after optimization, so dense leading-column choices simplified to a range can still probe later composite columns.

Range and NULL-prefix probes retain predicate evaluation. Optional filters may prune reads but cannot certify a DELETE rewrite.

The metadata transaction’s pinned view, revision-keyed probe cache, and statement dependencies are shared with direct lookups. Candidates feed the existing selective reader or row/file pruning, so SELECT, UPDATE, and DELETE all benefit without naming an index in SQL.

The file filter prunes the file list through the metadata predicate the data_file_id column already has, and the row filter lets the reader skip to the row group holding the id. Neither needs the metadata manager to consult the index while it builds the file list — a design that was built, measured and retired, because it probed on every scan with no way to know whether a probe would pay and could narrow files but never rows.

Where the rule declines, the scan is left as it was:

• A table below the probe’s worth. A probe costs about 3 ms, about what scanning a megabyte does, so a table under MIN_PRUNABLE_TABLE_BYTES (4 MiB of data files, from the statistics the planner has already loaded) is scanned without asking. This is the gate the file-list design could not have: at that point nothing says how big the table is.
• Another snapshot. A scan at a snapshot other than the transaction’s — time travel — is a different cut than the index resolves against.
• Transaction-local inserts. Rows this transaction inserted carry no file id and no index entry yet; a file filter would drop them.
• No ready index on a usable leading prefix, a value of a type equality indexes do not cover, or a read that failed, which is logged rather than raised. An interrupt is raised, since the caller asked the statement to stop.

A value no row holds pushes a row-id range no row is in, so every file is pruned by its row-id statistics and inlined data passes nothing. A row the lookup could not place, or one living inlined, admits the rows with no file id beside the resolved files, as the join trigger’s null-safe condition does.

Measured on 100,000 rows in two files with keys permuted, counting one row by key:

how the row is named	files read	Parquet bytes read
WHERE a = k, no index	2	477,245
WHERE a = k, files pruned only	1	238,622
WHERE a = k, this trigger, filters pushed	1	99,443
WHERE a = k, this trigger, summary scan	1	96,532 (moraine’s reader)
… USING moraine_index_lookup(…), the join trigger	1	2,923

The file list is worth the file it drops; naming the rows is worth most of the rest. What this trigger still reads is the key column’s chunk in the one row group the located row sits in: the predicate it deliberately keeps has to be evaluated on something. The join form never pays it, because it carries no predicate on the column at all.

A SELECT elects the summary scan the way the join trigger does — the scan is replaced in place, its pushed filters stay with it, and the summary scan evaluates them over what it reads — and that moves the read from DuckDB’s reader to moraine’s without shrinking it. DuckDB’s Parquet writer starts a new data page only at 100 MiB uncompressed, so a column chunk is one page, and a read by position fetches the same chunk a read by row group does: on the fixture above, 993,508 bytes for SELECT b … WHERE a = k either way. The election would pay only on files whose chunks hold several pages, which DuckDB does not write. DML never elects it: a DELETE or UPDATE scan asks for file_row_number, which the summary scan does not produce.

The last row reads nothing through DuckDB’s reader because the positions come from moraine’s file-row summaries, which that counter does not see; it needs the index to answer the predicate exactly, so it stays the explicit surface rather than a rewrite. Dropping the predicate from the scan would reach the same place for a SELECT, and the lookup contract is close to licensing it — entries are live-only and the summary scan subtracts the transaction’s deletes — but every pruning here rests on the predicate being evaluated in full, and a stale entry would then surface as a wrong row rather than a slow one. That line is not crossed.

Snapshot-validated index plans

Contract

An index plan is reusable only when its execution observes the same logical read state and bound arguments that produced its resolved rows. Unconditional rebinding is replaced by validation of those dependencies, not by allowing DuckDB to retain unvalidated lookup results.

This preserves the existing exact cardinalities, empty-result elimination, and static row/file pruning. Refreshing only the lookup operator’s rows is insufficient: an optimizer may have removed that operator entirely after an empty lookup, or embedded its old file IDs elsewhere in the plan.

Core read scope

The core owns an opaque IndexReadScope. It pins the store read view and the catalog projection used by index-definition reads, probes, file placement, inline membership, and delete visibility. DuckLake’s file-list and metadata reads for the containing statement must observe that same scope. Validation and execution retain the scope together; a check followed by an unpinned latest-state read is not sufficient.

Its identity contains the attachment incarnation and committed store revision. Dirty transactions refuse reuse rather than guessing a local revision. The store revision is the revision of the pinned read view, not a sampled latest counter. Writer snapshots expose a SlateDB sequence number; reader scopes must expose an equivalent stable revision or refuse reuse. A DuckLake snapshot ID alone is not sufficient: maintenance can change files or inline state without advancing it. A projection-cache epoch alone is also insufficient: cache replacement is not a complete index-data mutation clock.

An unchanged logical view may reuse results even if SlateDB has rewritten its SSTs: an LSM compaction that preserves key/value visibility does not invalidate row results. DuckLake file replacement does invalidate them. The initial implementation may conservatively invalidate on every committed store revision; table/index-specific dependency clocks require separate proof.

ReadOnlyCatalog::index_read_scope returns a scope whose reads() surface shares one SlateDB transaction and catalog projection. identity() compares the store incarnation and that transaction’s sequence number. Manifest-following readers return None until an equivalent pinned reader view is available.

The additive moraine_snapshot_scoped ABI owns that scope in a transaction snapshot. moraine_snapshot_read_handle lends a read-only catalog alias until the snapshot is freed; callers must never detach it. The alias shares the attachment’s runtime and caches. moraine_snapshot_read_revision exposes the pinned sequence solely for pairing with DuckDB’s attachment OID, not as a DuckLake snapshot ID. Existing unscoped entry points remain available.

An index bind resolves the lake’s actual metadata catalog and obtains the Moraine transaction through DuckLakeTransaction::GetConnection, not through the outer client connection. Metadata, inline scans, and probes therefore use the same read view. Ordinary metadata reads must not implicitly start a DuckLake transaction merely to obtain a catalog version.

A DuckDB transaction that has staged writes keeps probing at the revision it started on. Its metadata reads move to the staged transaction’s own read point, but index entries carry no transaction-local overlay: rows the transaction inserted are not in the index, and rows it deleted are still there, under either read point. The starting pin is the view consistent with the DuckLake snapshot the transaction scans at, whereas the moving head could name files that snapshot does not hold. Probes inside such a transaction are therefore scoped, memoized, and statement-cacheable exactly as before its first write; the join against the DuckLake scan applies transaction-local deletes, and a bare index read continues to report the committed index. Only a time-travel attach, whose DuckLake snapshot is older than any pin, stays unpinned and uncached.

Scoped probe memo

The core memoizes successful probe results within an attachment, keyed by the pinned sequence, table and index IDs, and canonical probe arguments. Equality keys are deduplicated canonical encodings; range bounds preserve inclusivity, and range/NULL probes include direction. Modes cannot alias. Definitions are validated against the pinned catalog before consulting the memo. Errors and unscoped reads are not cached; empty successful results are.

Two further reads memoize under the same pinned sequence. The file candidates a probe’s row ids locate are kept keyed by those ids, so a rebind — which a summary-scan plan forces on every execution — repeats neither the lookup nor the location. A table’s committed inlined-deletion ledger, which every scan open subtracts from its positions, is read once per revision however many scans a statement opens: the coverage estimate and the read that follows it share one scan. Each memo has its own byte ceiling and the probe memo’s entry ceiling, and is skipped outside a pinned scope exactly as the probe memo is.

The probe memo admits at most 8 MiB of accounted entries and 4096 entries, evicting least-recently-used entries. Keys, row IDs and entry headers are accounted; container slack is additionally reported through projection_bytes in the memory tally. Oversized results are returned without admission. Entries retain neither transactions nor files; old revisions remain reusable only by a scope that actually pins that revision. Location resolution still runs against that scope, using the existing row-summary directory.

Prepared-statement lifecycle

1. Binding registers the pinned revision and metadata attachment OID in the statement’s read_databases, plus the lake dependency. These survive empty result elimination and other operator rewrites.
2. DuckDB’s catalog-version checks invalidate the whole plan on a changed attachment or revision. OnExecutePrepared and OnRebindPreparedStatement additionally validate the actual DuckLake metadata-connection scope. An outer metadata transaction’s version alone cannot establish equivalence.
3. The initial whole-plan fast path accepts direct literal index invocations, including literal lists, built-in range/row constructors and primitive Boolean/integer casts. Parameters, session-dependent expressions, hidden invocations in views/macros, and unsupported statement shapes conservatively rebind. Canonical arguments in the core memo then allow identical evaluated parameter values to reuse a probe without trusting SQL text.
4. A mismatch rebinds and optimizes the whole statement under its pinned scope. DuckDB’s other rebind requirements remain authoritative. In particular, its ordinary multi-file scan still requires rebind: indexed joins reuse the core probe memo while rebuilding their scan and pruning plan.
5. Prepared plans own their immutable row vectors, with an 8 MiB admission limit per index invocation. Copies and destruction follow DuckDB ownership; they never own a read transaction. Transaction completion, rollback and cancellation release execution scopes. Connection state retains only attachment names/identities, pruning detached associations on the next bind.

Evicting a core memo entry requires a fresh probe on a later rebind; it does not invalidate an independently owned, revision-validated prepared plan. SQL EXECUTE does not install a rebound physical plan back into DuckDB’s original named prepared statement, so it can continue rebinding after a revision change; the memo still prevents repeat probes for unchanged revised inputs.

The fast path is especially important for PREPARE immediately followed by EXECUTE: if arguments and the pinned read state are unchanged, the second operation must not repeat the index probe. A write between executions requires refresh; a long-lived prepared statement does not pin query results forever.

Filters and joins

Pruning filters can admit extra rows. Independent row-ID and file-ID lists also lose the pairing relation, and filters derived through projections or filters above an index read can be supersets of that child’s actual output. The general optimizer rule therefore retains the original join, including its extra conditions, output columns, null semantics, and multiplicity.

Join elimination is a separate exact rewrite: only after proving pair membership, uniqueness, all predicates, and output equivalence may a located read replace the join. Summary-driven scans do not require join elimination.

Exact summary-driven scans

For an inner or semi join whose two location conditions identify rowid and data_file_id on the same current-snapshot DuckLake table as the index read, the optimizer replaces the scan with moraine_summary_scan. It retains the join, including predicates, output columns, and multiplicity. Projections and filters above either child may narrow the bound candidate pairs; the scan reads their deduplicated superset, and the unchanged join decides membership.

The bind data holds pairs and table identity, never decoded rows. At execution, the scan uses DuckLake’s metadata connection and its pinned Moraine read scope. It verifies the snapshot, resolves exact ordinals through retained summaries, and removes positions deleted at that snapshot. ReadOnlyCatalog::scan_rows_at accepts located pairs and ordered top-level column names, returning a LocatedRowScan cursor. next_record_batch returns an owned Arrow batch with row and file IDs appended after the projection. The SQL scan exports the original buffers through the Arrow C Data Interface, without IPC encoding, copying, or decoding. Release callbacks own each batch independently of the cursor; the shim consumes both structs under RAII even if Arrow import throws. Parquet reads select only the requested columns and physical positions, using page indexes when available. Files open on demand; inline chunks are decoded one at a time. set_parallelism configures read-unit prefetch before iteration starts, defaulting to one for core callers. SQL uses moraine_summary_scan_threads (default four), clamped to DuckDB’s thread count and a per-cursor ceiling of the available CPUs, bounded to two through eight. The ceiling follows the requests an object store serves at once, not the cores available to decode them: a scoped read spends almost all of its time waiting on the store. Each worker reserves a single output slot before decoding its next batch, and that slot is what bounds a cursor’s queued batches. No process-wide pool gates a worker, so one cursor’s decoding never stands between another’s and its first byte range. Worker tasks are execution-owned; dropping the cursor aborts them and releases their pinned scope. Parallel execution partitions every selection into nonempty row-group work units using cached footer counts — the counts opening the file requires anyway, so no selection is small enough that partitioning costs a request. Each unit retains original file ordinals and exact row selection, so embedded row IDs, sparse selections, and delete filtering are unchanged. A selection inside one row group yields one unit and fans out to nothing. File and row-group units use the same one-batch output queues, never nested worker pools. files_read counts distinct files even when several groups are read concurrently. Parallel output has no file-order guarantee; an SQL ORDER BY remains authoritative. files_read counts opened data files for query profiles. A verified summary may disprove a conservative candidate; the selective reader omits that pair, while exact file-position resolution rejects absent pairs. The cursor refuses partially visible historical files; ordinary time-travel queries retain DuckLake’s per-row insertion-snapshot filtering.

Pushed scan predicates are evaluated on the projected batches before filter-only columns are removed. The join remains even when both location keys match exactly. The selective scan has no 4096-row derived-filter cap: it carries exact pairs, not a large SQL IN expression. When candidates exceed both 4096 pairs and one quarter of the table’s known row count, the optimizer keeps the ordinary scan to avoid selective-reader overhead on broad probes. This is a cost choice, not a correctness bound.

For more than 16 file-backed candidate pairs, the optimizer also estimates physical coverage under the pinned view, using summary positions, file schema projection, and cached Parquet footers/page indexes. It never decodes projected payloads for costing. prefers_selective_reads sums projected compressed bytes plus an 8 KiB allowance per range; adjacent selected pages form one range. Missing page indexes conservatively charge entire touched column chunks. If at least 16 row groups are involved in the candidate files and selected cost reaches 80% of their full projected cost, ordinary DuckLake scanning wins the estimate. This catches small result sets scattered over almost every page. The existing data-store range reader coalesces nearby fetches for retained selective scans. Positioning and delete visibility are checked again at execution; estimation retains neither decoded payloads nor a transaction in the prepared plan. Inline candidates are excluded from costing so preparing a query cannot fetch their chunk bodies for this estimate.

Scan selection is automatic, with no public runtime on/off switch. The moraine_summary_scan operator remains; moraine_summary_scan_threads only bounds its reader concurrency. The filter benchmark accepts --baseline <extension> to compare explicit builds using identical SQL and one unchanged fixture in separate processes. It alternates build order across query shapes, verifies every result, and reports each build’s selected scan path and warm median after discarding its first observation. This compares builds rather than isolating the rewrite if the reference also differs elsewhere. --parallel creates a four-file fixture and alternates serial and two-reader configurations with four DuckDB threads; --fixture can reuse a single-file fixture instead. The former --ordinary and --compare runtime-switch modes are removed. Profiles report coverage costing, positioning, batch-read elapsed time, active Parquet polling time, Arrow import time, fetched bytes/ranges, and peak read workers. Active polling includes synchronous cache access and decoding, but excludes asynchronous waits; fetch and polling times sum across workers and are not additive components of parallel wall time. Both paths retain their own caches.

The rewrite declines time travel, change scans, sampling, unsupported virtual columns, nested column projections, and types not supported by the core’s logical schema projection. Supported scalar types are booleans, integers through 64 bits, floating point, strings, UUIDs, dates, and timestamps. Other shapes retain DuckLake’s scan and the existing derived filters. A failed exact summary remains an error, never a fabricated position. The new scan retains the multi-file scan’s statement-cache restriction; the core’s memos still avoid repeated index resolution, row location, and ledger reads when rebinding.

Transaction-local changes do not disqualify the rewrite. Index-derived pairs name committed rows only, so rows the transaction inserted (new files or inlined data) can never join and need no scan. Rows the transaction deleted must not be returned: at execution time the operator collects DuckLake’s transaction-local deletions for every file it will read — the pending delete file the transaction wrote for the file, if any, plus inlined file deletions — and passes those positions to the core scan as exclusions, and drops pairs naming inlined rows the transaction deleted. Exclusions are gathered at execution, not binding, so a prepared plan executed after further deletes in the same transaction sees them. Under pinned probes this keeps the located delete’s SELECT on the selective path throughout a multi-statement write transaction.

Reusing positioning between costing and execution

The current costing cursor is discarded and execution resolves positions again. Any reuse must distinguish raw physical positions from visibility-filtered rows. position_requested_files resolves raw positions, while file_reads applies snapshot-filtered file and inline deletes and resolves versioned columns. Retaining that entire cursor is not a safe position cache.

Both delete-file readers cache their decoded result: the all-position reader by object, the snapshot-filtered reader by object and cut, so a transaction that opens the same files statement after statement decodes each once. Scan positioning resolves raw physical positions only; it takes the delete-file identity from its pinned snapshot and reads snapshot-filtered positions once. Only the located-delete API, which must hand the existing delete file’s full position set to the rewriter, materializes the unfiltered positions. A scan therefore never populates the all-position cache with entries it does not use.

A bounded position-only memo is the preferred boundary. Its identity includes the catalog store and pinned SlateDB revision, DuckLake snapshot, table, exact canonicalized row/file pairs, strict-versus-candidate mode, and data-store cache identity plus resolved path prefixes and file incarnation metadata. A DuckLake snapshot number alone is insufficient: maintenance can change metadata under that number, and numbers are not globally unique across catalogs. Unpinned manifest-following readers must bypass reuse. No entry retains a transaction, payload batches, errors, or a live read cursor.

Execution validates the identity and current files, then reapplies delete visibility and schema projection under its pinned scope. It may reuse successful summary-to-ordinal resolution, not an earlier execution’s post-delete result. Prepared statements miss after a revision change; an old pinned reader may reuse its own immutable revision. Exact schema/data identities also prevent a same-shaped table in another catalog or attachment from sharing positions.

Admission must be bounded by pair/position bytes and an entry ceiling, with oversized inputs falling back to normal resolution. Required regressions cover prepare then delete/update/flush/compaction, strict missing rows, candidate omission, historical delete-file snapshots, equal snapshot numbers in distinct stores, path changes, and eviction. Measure actual repeated positioning and allocation work before adding the memo: existing summaries and footers are already cached. This defines the reuse boundary, not a claim that a memo is present in the current scan implementation.

Exact-probe physical read batching experiments

Prefix filters, tombstones and sequence visibility remain SlateDB’s responsibility. Broad range scans are not a substitute for a multi-prefix API: the benchmark shows sparse-key over-read and cold-read parallelism regressions. The current SlateDB public API exposes no batched prefix probe sharing its internal SST setup.

The test-only physical coalescer keeps existing prefix probes and combines concurrently requested overlapping/adjacent SST byte ranges underneath them. It does not combine query results or scan intervening keys. It waits one scheduler yield, not a fixed timer; disjoint ranges remain independently in flight. Queued requests and merged response widths are bounded. Conditional, versioned, HEAD, unbounded and non-SST requests bypass coalescing. Failed combined reads fall back to the original requests so individual bounds and error behavior are preserved. Each response owns only its requested bytes: caching a small block must not keep an unaccounted megabyte-sized merged allocation alive. No persistent coalescer cache is added; ordinary decoded-block admission is unchanged.

This experiment does not remove per-probe iterator setup. Promotion requires measured dense benefits without material cold/scattered regressions, and robust cancellation and concurrent-query resource bounds. Production retains individual probes and does not gain a runtime batching switch from this benchmark.

The initial 324-observation comparison found essentially unchanged GET counts and no consistent latency benefit across clustered, gapped and scattered keys. It covered one or eight concurrent 192-key statements, cold/fresh/warm blocks, and memory or synthetic 20 ms storage, including a 32-request service limit. The coalescer therefore stays test-only. Reducing warm probe CPU requires a different boundary: sharing SST/iterator setup across exact prefixes inside SlateDB, not delaying independent storage requests in this wrapper.

Equality read-ahead

Non-unique equality probes use a separate 1 MiB read-ahead with two fetch tasks per SST iterator, admitting fetched blocks. Prefix bounds still prevent reads past the key’s range. Bulk and range scans retain their throughput settings; single-entry seeks retain one-block reads. The equality window bounds buffering without the one-GET-per-block penalty for high-fanout keys. It does not promise fewer GETs for small prefixes that already occupy a single block.

Validation and integration order

First add core pinned scopes and prove coherent metadata/index reads against concurrent commits and same-snapshot-ID maintenance. Then connect DuckLake statement metadata/file-list reads to those scopes. Finally enable validated plan reuse through the callbacks and remove unconditional rebinding for the covered functions. Until those prerequisites pass, the existing rebind guard remains the correctness fallback; changing its boolean alone is prohibited.

Required tests cover unchanged literal and parameter executions (one probe), changed parameters, insert/update/delete, absent-to-present and present-to-absent results, index drop/recreate, inline flush, file rewrite, same-ID maintenance, explicit transactions and rollback, reader polling, attach replacement, cancellation, and prepared-statement destruction. A deterministic concurrent commit between validation and execution must not mix scopes. Benchmarks report probe counts, validation time, prepare time, execution time, and retained bytes.

An indexed-equality DELETE needs no scan

The core exposes selective reads and exact position resolution. locate_row_positions_at(snapshot, store, data_prefix, table, pairs) takes an explicit snapshot, a data store, and (row_id, DataFileId) pairs, returning Vec<LocatedDeletion>. The head-snapshot wrapper and LocatedPositions container are removed; file positioning accepts no inline-row inputs or outputs. Inline reads remain part of the selective cursor.

The retired locator verbs’ scan_rows_at_strict, commit_located_deletion, DeleteFileRegistration, and table_write_directory are removed. Resolved file positions carry only the data-file ID, requested offsets, and optional existing delete offsets; callers no longer receive unused paths or delete file IDs. DuckLake owns deletion staging, writing, and commit.

The DuckLake patch retains file-position DELETE only. Its unused positional UPDATE, inline-row mutation argument, and deferred position-token resolver are removed, including the transaction-side request registry, token counter, and lock. The optimizer resolves an equality once, offering its result to the DELETE rewrite and reusing it for scan pruning when rewriting declines.

A DELETE whose whole predicate a certified index answers does not need to look at the table: the rows it would find are the rows the index reports. So the plan is replaced outright — LOGICAL_DELETE becomes a projection, carrying the delete’s own table index so the parent’s binding still resolves, over a ducklake_delete_positions call bound at post-optimize time. Physical planning never reaches DuckLake’s delete operator, and no table scan survives. Position resolution can still read row-id or delete metadata; the absence of scan I/O is not a claim of zero object-store reads.

Measured on 100,000 rows in two files, keys permuted so column statistics prune nothing, deleting one row by key:

how the row is named	files read	data read
WHERE a = k, index not certified	1	236.6 kB
WHERE a = k, index certified	0	nothing

The second row’s plan is a projection over DUCKLAKE_DELETE_POSITIONS, and EXPLAIN ANALYZE omits its Data Read line entirely, which it does only at zero scan bytes. It does not count reads made while resolving positions.

This is the one rewrite that replaces predicate evaluation rather than narrowing it, which is why it reads the certificate (The certificate): a wrong entry here deletes a row rather than returning one. It declines unless all of these hold, and leaves the ordinary plan alone when any fails:

• the index is certified, and Ready;
• the index answers every pushed predicate exactly, including every column of a composite key; optional hints and residual predicates cannot replace predicate evaluation;
• the scan is at the transaction’s snapshot, with no transaction-local inserts, and the table is past the probe’s size gate;
• every resolved row sits in a committed file, which is the positional writer’s scope;
• the table does not write deletion vectors, which the positional function does not support;
• there is no RETURNING, which DuckLake refuses on this path anyway;
• nothing but projections sits between the delete and its scan. A filter, join or aggregate there is a predicate the index did not answer.

The deletion-vector fallback preserves the existing operator; it does not add deletion-vector decoding to index upkeep, which currently requires Parquet delete files at commit.

Positions are resolved against the scan’s snapshot and the call names it, so DuckLake refuses them if its transaction has moved past that view.

UPDATE uses the automatic pushed-filter path. DuckLake plans one as delete-plus-insert, so it must construct the replacement row; the pushed-filter rule narrows reads of the required columns to the holding file. On the same fixture, every form reads the same amount:

UPDATE … SET b = 'z' WHERE a = k	files read	data read
predicate, index not certified	1	236.6 kB
predicate, index certified	1	236.6 kB
joined to a lookup on rowid — naming the row exactly	1	236.6 kB

On this fixture, naming the row exactly reads what the predicate reads. This supports keeping the ordinary UPDATE operator, including its assignment and constraint semantics. It does not establish a lower bound for files with different page layouts; a positional UPDATE rewrite remains a possible future optimization for those files.

Naming exact rows from SQL

A lookup reports (row_id, data_file_id), and both are columns a scan can be filtered on, so a statement names exact rows by joining the lookup to the table on them:

DELETE FROM lake.main.t
USING moraine_index_lookup('lake', 'main', 't', 'by_a', 150) hits
WHERE t.rowid = hits.row_id
  AND t.data_file_id IS NOT DISTINCT FROM hits.data_file_id;

The null-safe comparison on the file id is what admits an inlined row, whose file id is NULL. UPDATE … FROM takes the same shape, and carrying per-row new values is a join against a VALUES list on the same two columns. The optimizer rule recognises the join and pushes the resolved row ids and file ids as scan filters, so the read is the located row’s row group rather than the table.

This replaced a set of dedicated verbs — moraine_delete_located, moraine_rows_at and moraine_update — that resolved the same pairs against the snapshot. The deletion read no row data; the read and update verbs fetched the positioned rows. They were withdrawn: the join form expresses every row set they addressed, the optimizer rule closes most of the gap on reads, and the automatic path is where the remaining difference belongs rather than a surface a caller has to know to reach for.

What went with them is the one thing the join form cannot say: these rows as I read them, or fail. The verbs positioned against the pinned snapshot and refused a pair whose file no longer held it, so a caller that resolved a set in an earlier statement learned that it had moved. A join is last-write-wins — it operates on whatever matches now and silently changes fewer rows. A caller that needs the stricter contract has to compare the reported row count against what it resolved.

Range and comparison queries

Because the canonical encoding is order-preserving (Canonical value encoding), byte order is value order, so both entry kinds — index/unique (one value per key) and index/multi (value then row id) — are already single contiguous value-ordered ranges. A comparison query is therefore a bounded ByteRangeBounds sub-scan of the same range an equality lookup keys into. There is no new index kind, no new discriminant, and no new maintenance surface; the whole feature is the ordered encoding plus the accessor.

• Equality stays a point-get. = is a degenerate closed [v, v] range, but a unique lookup remains one get and a non-unique one a value-prefix scan; the model unifies the surface without making the point case pay a range’s cost.
• The definition carries per-column direction and NULL placement. The definition value grows a direction (ASC/DESC, default ASC) and a NULL placement (FIRST/LAST, default LAST) per column, recorded only when they diverge from the default so an ascending index is byte-unchanged on disk. create_index gains an ordered variant; the rest of the verb surface is untouched.
• Direction orients the scan. A DESC column’s byte order reverses value order, so index_range maps a value-lower bound to the byte-upper bound (and vice versa) for the range column — a single-column DESC index scans high value first, and half-open bounds map correctly.
• The B-tree access rule. A range query names an equality prefix over the leading columns plus one range on the next column (a = 5 AND b > 10); a bare range on a non-leading column cannot use the index and is refused, never scanned wrong. BETWEEN is a closed lower and upper; the strict comparisons are half-open; Unbounded is an open side.
• IS NULL is a prefix scan of the stored NULL rows. Comparison predicates never match a NULL (SQL: NULL > 5 is unknown), so range results exclude NULLs by construction. IS NULL is served separately: = v and IS NULL are both exact prefixes (a fixed value blob, or a fixed null flag), so a leading run of them is one bounded scan. Because a NULL-bearing row is stored multi-shaped (Canonical value encoding), index_nulls scans the multi subrange on the encoded prefix, with the value framing’s terminator dropped so it matches every key that extends the run. A gap (unconstrained leading column) is not a prefix and is not expressible.

Everything else — coverage, uniqueness enforcement, the value-keyed collision, staged builds, the scoped read, rewrite-file resolution — is unchanged, calling the ordered encoder. Storing NULL rows is the one coverage change: a NULL-bearing row is now maintained as a collision-exempt multi entry, so IS NULL is total over live rows. Movement invariance holds identically: order lives in the key, which flush and compaction do not touch.

Staged builds — multi-commit backfill

A backfill too large for one WriteBatch cannot be one commit, and the bounded-commit rule (Reclamation’s posture) is not negotiable. The staged protocol splits the build into a building→ready lifecycle built from the same three primitives as everything else here: writer-maintained coverage, the value-keyed collision, and bounded batches. No new race machinery.

The lifecycle. create_index(…, staged) commits the definition in building state — altered_table, schema_changed, exactly like the single-commit create. From that commit forward the full Coverage contract applies to every writer: inserts stage entries, deletes stage entry removals, entry-less registrations are refused, DuckLake writes are covered by the scoped read — a building index is maintained as if it were real, because by the time it flips ready it must already have been. Unique entries are value-keyed from the first commit; there is no second key form to convert later. What building withholds is the outward surface: index_lookup fails typed (IndexBuilding) — the coverage Goal is kept by refusal, the same way it is kept everywhere else — and a unique collision does not fail the writer (below).

Backfill batches. The builder covers the rows live at its current snapshot; everything committed after the definition is writer-covered by the paragraph above, so the two sets meet with no gap. A derivation pass walks live inline chunks and then external files in durable source order. Parquet is decoded as bounded Arrow batches and entries flow directly into the next BuildStep; the driver never assembles or sorts the table-wide entry set. Delete files and inline deletes are applied as each source is read. Each step ends at whichever BuildStep bound it reaches first (Two bounds on a step) and always carries at least one entry.

The build filter. Before its first pass, a build fills a bloom filter with every key the index already holds, by one ordered scan of the index’s unique-key range, so a resumed build and a deferred repair know what earlier passes and writers committed. Each staged key is added as it is derived. The filter is sized from the table’s row count at about a 0.1% false-positive rate, clamped to 64 MiB, and lives in memory for the duration of the call; a false positive costs one probe. Every full step’s unique entries thus commit at the cost of non-unique ones, plus one probe per real duplicate, stale key, or false positive.

Derivation runs beside its commits. A full step is handed to a committer that lands steps in order while derivation fills the next one, so a step’s durable write overlaps the reads and decoding behind it. The committer checks the derivation snapshot inside each closure exactly as before; a conflict ends the pass and the next derives afresh. A derivation failure is delivered to the committer behind the steps already handed off, so those still land before it surfaces.

The external leg reads ahead. Files are planned thirty-two at a time: the footer, the file’s read-column mapping, its inline file-deletes, and its delete files resolve concurrently, ahead of the position being consumed. Planning is wider than reading because it fetches only footers and delete files, which are small. Each row group of a planned file is a unit read on its own task, which decodes the group and encodes its entries to physical keys off the driving task, holding a fixed number of encoded batches ahead of the consumer. A window of eight units runs at once; each unit holds decoded rows, so the window is what bounds the build’s memory, and it does not widen with the machine. Encoding runs on blocking workers under one process-wide permit count — the machine’s core count, clamped to between four and thirty-two — which also bounds the encode futures a single file’s stream keeps in flight. Entries are consumed strictly in file-then-position order, so the source cursor is exactly what it was under a serial read, and a resume inside a row group reads that group from the cursor. A single large file therefore still parallelizes across its row groups; a file with one row group does not.

SQL-write upkeep compiles one projection plan per live index, deduplicates shared Arrow columns, and decodes each Parquet or inline batch once. A scalar stays borrowed from its Arrow array while the store-layer canonical builder writes its NULL flag, canonical bytes, escaping, terminator, and direction transform directly into the final key. No row-wide value vector or per-index value copy crosses the batch boundary. NULL presence is accumulated by the same builder and selects the multi-shaped unique-NULL entry. The builder then expands those canonical bytes in place into the final physical index key; the staged entry retains no intermediate canonical value or second payload allocation. For inline input, each (table, schema version) IPC schema is decoded once per commit and shared by all of its chunks. A chunk’s owning Bytes is sliced directly into Arrow’s immutable data buffer, avoiding a second copy of the body after it moves to a blocking decode worker.

Delete sources are grouped by physical target from their staged metadata before any object is opened. Each target resolves its own delete files, so independent additions and inline removals start beside delete discovery. A target’s footer and page index, and its read-column mapping, depend on nothing but the snapshot, so they load beside its delete files; only its row selection waits for the positions. A registered file’s footer likewise loads beside its column mapping and any same-commit deletes against it. Data-file additions and removals retain their bounded producer windows; nested delete-file reads share one commit-wide allowance rather than multiplying that bound per target.

Each step atomically advances a source cursor persisted in the definition. Inline progress identifies (schema_version, begin_snapshot, chunk_seq) and its next row offset, plus flags for a completed chunk and inline leg. The covered snapshot identifies the last committed step. The driver streams these immutable sources in key order, holding one body and projected Arrow batch, resolving tombstones through a bounded range iterator, and encoding one entry at a time into the step buffer. It caches only the current decoded schema.

Inline source order need not match row-id order. Streamed inline steps therefore leave the older row-id watermark unchanged: an older binary ignores the new protobuf field and safely replays the inline leg in its own row order. A build written by an older binary can resume using its row watermark until the first source checkpoint. The new cursor is optional, so old values remain readable and this extension does not require a format-version change.

The external leg retains its data-file id and physical-position cursor. Files are immutable and ids are monotonic, so resume does not depend on embedded row-id order. A replacement file receives a later id and is safe to re-derive; entries name stable row ids, so repeated puts are idempotent. Deferred repair seeds its file cursor at the preceding snapshot’s tail. Inline repair resumes its source checkpoint only if the current head is that checkpoint’s covered snapshot; otherwise it replays live inline sources, including updates that preserved a row id. Every cursor update is guarded by the derivation snapshot, so another builder or writer cannot move progress under a stale premise.

BuildStep bounds one step’s entry buffer, not all process memory. Derivation also retains the step being committed, the read-ahead window of units with their buffered encoded batches, one inline source chunk, schema projection, store iterator buffers (256 KiB of read-ahead with two fetches in flight per inline source iterator, per SST it is positioned in), and per-file deletion state. An individual stored Arrow chunk can be larger than a step; no path retains all inline chunks or all derived inline entries. Entry-buffer and inline body/decoded-array high-water telemetry are reported separately; array buffers can share body memory, so those byte counts must not be added as a heap estimate. Whole-operation allocator peak measurements include store caches and commit/WAL work as well as derivation. Intermediate steps classify inserted_into_table:<table_id>: the commit layer treats an append as benign and rejects a concurrent delete, schema alter, or drop. A replayed closure still checks the driver’s derivation snapshot before staging its entries. An intermediate cursor advance does not change the table schema: it mints its ordinary snapshot while retaining the current global schema version and writes no ducklake_schema_versions row. Only the initial definition publication and final ready flip advance schema history.

The delete race. A row live at one derivation pass can die before its step lands, and a stale entry for a dead row is corruption — for a unique index it manufactures false Constraints. Both tenses resolve into one mechanism: derivation from a fresh snapshot. Each pass reads its definition, inline rows, file registrations, schemas, and delete bookkeeping through one snapshot-isolated read session. Every step checks that snapshot inside its commit closure before staging entries; after a successful step, only its returned commit snapshot advances the expected value. Reading a newer head after acknowledgement must not adopt intervening writes into the premise. The driver conservatively re-derives after any other snapshot advance, including an unrelated append, rather than trying to prove it harmless.

• Past deletes (committed before the pass’s snapshot): excluded by construction — the scoped read applies the table’s delete bookkeeping, so a dead row produces no entry.
• Deletes after derivation but before the step opens: the in-closure snapshot check returns CommitConflict, so an already-committed deletion cannot become part of a stale batch’s premise.
• Concurrent deletes (racing an open step): the killing commit writes deleted_from_table, which conflicts with the step’s inserted_into_table classification, so the loser surfaces CommitConflict — never an internal closure re-run that would re-stage a stale batch. The driver answers a surfaced conflict by re-deriving at a fresh snapshot (which excludes the newly dead rows) and re-committing from the durable cursor. The retry boundary covers the entire pass, including flushes triggered by a full entry or byte buffer and the final ready flip.

Duplicates poison the build, not the writer. During building the entry set is incomplete, so an absent probe proves nothing and enforcement cannot be offered — but a violation a put does discover is real: the colliding entry belongs to a live row, because unique keys are value-keyed from day one. Every such collision — a backfill step finding a pre-existing duplicate, or a writer inserting a value another live row holds — stages a terminal poisoned flag on the definition and drops the colliding claim, so the live holder’s entry survives; the commit that found it lands normally, rows and all. One rule covers both discoverers, and it is the partial coverage that demands it: enforcement during a build depends on how far the backfill has run, so failing the finder would decide which party a duplicate falls on by timing. A poisoned build stops at its next step: the driver ends the definition into history (ordinary drop, Reclamation sweeps the range) and surfaces Constraint to the create_index caller — the create fails, exactly as its single-commit form would have.

Poisoning writes the definition key, so it conflicts with cursor advances — both re-run, and the flag is terminal, so every interleaving converges. Because the flag rides the commit’s ordinary entity diff, the current record and its history mirror are written together and the maintained projections fold it like any other definition change.

The ready flip. When the cursor reaches the end of the S₀ set and the definition is not poisoned, one final commit flips building→ready — altered_table, schema_changed, like the create: the flip changes what readers may do, so it must conflict with in-flight writes, whose re-runs then see ready and apply full enforcement (Constraint instead of poison). From the flip forward the index is indistinguishable from a single-commit build: same keys, same coverage, same guarantees. The before/after entry ranges are byte-identical to what a from-scratch build over the same live rows would produce — that equivalence is a test obligation.

Driving the build. The embedding API returns from create_index(staged) once the definition commits; the host advances the build with a build_index_step(index) verb — one bounded batch per call, returning the cursor position or terminal state — and loops at its own pace. The extension path’s CREATE INDEX … WITH (staged = true) drives the loop internally through autonomous commits, returning once the index is ready or the build has failed. A cancelled or crashed call leaves the definition building: re-issuing the same call resumes from the cursor, and DROP INDEX abandons the build. moraine_indexes exposes the state for progress: is_building for the binary question, and state for which of ready, building, maintaining, or poisoned it is. A caller gating writes on readiness needs the latter — is_building is true for a poisoned definition, which no build is advancing, so it reads identically to one mid-build. drop_index on a building index is an ordinary drop: the builder’s next step re-runs against the ended definition and stops.

The core driver requires a data-path store whenever the table has live registered files. It checks before creating or adopting a definition, again inside the definition’s commit closure, and at the start of every derivation pass. Missing-store refusal leaves an existing resumable build intact; empty tables and tables containing only inline rows need no data-path store.

The driver emits progress at info. A derivation-started event makes the otherwise quiet Parquet-read phase explicit; the matching derived event names the live entry total and the derivation and sort times. Every successfully durable step then reports the entries in that step, cumulative entries for the current invocation, the live-table total estimate, percentage, row and source cursors, final-step flag, and commit time. A resumed invocation starts its counter at zero but names its durable starting cursor. A conflicting step emits a warning with the last durable count before the driver re-derives. Attempted but non-durable work is never reported as completed.

Format. The minimum readable format is 9, which includes staged and deferred index state. Every supported reader understands these fields; creating, completing, or dropping an index needs no format-stamp write.

Extension path: SQL surface and the scoped read

moraine is DuckLake’s metadata catalog, not the catalog that owns user tables (RFC 0006). DuckLake rejects index DDL, but DuckDB offers failed binding to OperatorExtension. Moraine handles CREATE INDEX, CREATE UNIQUE INDEX, and DROP INDEX there for Moraine-backed lakes. A PlannerExtension post-bind callback handles DROP INDEX IF EXISTS, which can otherwise bind successfully without finding an index. Both paths use execution callbacks backed by the core build/drop engine; no DuckLake patch is added.

CREATE UNIQUE INDEX by_id ON lake.main.users(id);
CREATE INDEX IF NOT EXISTS by_region ON lake.main.users(region)
    WITH (staged = true, step_entries = 100000);
DROP INDEX IF EXISTS lake.main.by_region;

Native DDL requires autocommit and a writable lake. The existing build engine commits independently; rejecting explicit transactions prevents a SQL rollback from falsely appearing to undo index DDL. Binding and ordinary EXPLAIN do not mutate indexes. Native DDL returns no result rows. step_entries and step_bytes must be positive and bound each staged build step. Deferred maintenance is available only to non-unique indexes. IF NOT EXISTS tests the schema-level name and leaves an existing definition unchanged; repeating an interrupted staged create without that clause resumes its build. Use catalog.schema.index for DROP when a search path spans multiple schemas or catalogs; an unqualified Moraine index uses the current default schema.

Native indexes accept stored column references and the options staged, step_entries, step_bytes, maintenance, directions, and nulls. Expression and partial indexes are unsupported. DuckDB’s parser currently discards per-column ASC/DESC and NULL-placement clauses, so explicit ordering uses WITH (directions = '[desc, asc]', nulls = '[first, last]'). These string-encoded lists have one entry per indexed column; omitted options default to ascending / NULLS LAST. List elements must be non-null and name a valid direction or placement. PRIMARY KEY and table-level UNIQUE constraints remain unsupported.

Rebuild currently means dropping and recreating the definition. It temporarily removes query acceleration and uniqueness enforcement, and the recreated index needs a new verification pass for certified optimizations. An online rebuild with an atomic replacement is separate from native DDL and is not implemented.

The former moraine_index_create and moraine_index_drop SQL functions are removed. Callers use native DDL, which requires autocommit even where the old functions committed independently inside an explicit SQL transaction. The Rust creation and table-qualified lookup/drop APIs remain available. A legacy schema with duplicate index names must use that Rust API to remove the ambiguous definitions before issuing SQL DROP: resolve the table, call Transaction::index_by_name(table.id, name), and pass its id to drop_index.

The table-qualified SQL surface. Introspection, verification, and explicit lookup functions remain available:

Every function names its target by four leading positional strings — catalog, schema, table, index (moraine_indexes stops at the table) — written … below for brevity.

Function	Effect
moraine_index_lookup(…, v…)	table function: row ids for the equality key v… — one variadic value per indexed column, in the index’s column order (a single value for a single-column index); the count must equal the index width
moraine_index_in(…, keys)	table function: row ids for the union of complete equality keys in keys. A single-column index takes a list of scalar values; a composite index takes a list of row(...) values in index-column order. Duplicate keys are one predicate, a key containing NULL matches no row, and an empty list returns no rows
moraine_index_range(…, lower, upper, lower_inclusive, upper_inclusive, reverse := b)	table function: row ids for a value window. Each bound is a scalar (single-column index) or a row(...) tuple over the leading columns; a NULL bound is an open side (half-open). reverse serves the opposite of the index’s order
moraine_index_nulls(…, prefix…, reverse := b)	table function: row ids for an IS NULL query; the variadic prefix is the leading columns, a NULL arg meaning IS NULL and any other = value
moraine_index_verify(catalog, schema, table, index)	table function: recompute the index’s entries from the live rows and report the difference — stored, expected, missing, dead, mismatched, then certified_at (the snapshot the index now stands certified at, NULL when it does not). A read-write attach records the outcome (The certificate); a read-only one reports without writing. Reads every live data file of the table, so it costs what the build costs. A clean index reports stored = expected and zeros for the last three. Only a ready index can be verified: a build’s entries are incomplete by design
moraine_indexes(catalog, schema, table)	table function: index introspection — index_id, index_name, is_unique, is_building, state (ready|building|maintaining|poisoned), and certified_at (The certificate)

moraine_index_in binds keys as one constant list value (including a prepared-statement parameter), like the arguments of the other explicit lookup functions; it does not consume keys streamed from another relation. A DuckLake read joins on row_id alone, so UPDATE, compaction, inline flush, and delete semantics remain under DuckLake’s snapshot-aware scan.

A multi-column range bound is a tuple. Tuple windows require every named column to sort the same way; one byte range then spans them. With mixed directions no such range exists, so both bounds must name the same leading values and differ only in the last. Other shapes are refused.

Each resolves the store handle from the attached catalog and the table_id from ducklake_table, then drives the same core verbs as the embedding API. Native index DDL commits autonomously and races concurrent DuckLake commits through the ordinary altered_table conflict. It rejects enclosing explicit transactions.

The index read functions bind their arguments as constants, exactly as moraine_index_in binds keys, and resolve them against the snapshot the current DuckDB transaction pinned on the metadata catalog. They read; the statement that mutates is ordinary SQL joined to their result, so it transacts as any DuckLake statement does.

Coverage: intercept inline, read bulk. Small inserts DuckLake stages inline; their values cross the ABI as an Arrow body (RFC 0005), and moraine derives entries from them as embedding inline_insert does. Bulk data DuckLake writes to Parquet directly — those values never cross moraine’s boundary, so there is no “before” to intercept — and the committer instead reads the just-registered file, projecting only the indexed columns, the row positions, and the row-id column when the file carries one. Entry row ids follow DuckLake’s own resolution rule (source-verified in its reader): the file’s embedded row-id column if present — rewrite files from UPDATE and compaction preserve old ids there — else row_id_start + ordinal. Deletes are symmetric: a staged register_delete_file names positions; moraine reads those positions’ indexed values and row ids from the target file to name the entries to remove. Indexed columns are located in the file by field id through the column-mapping rules (RFC 0018). The prohibition on reading Parquet guards the scan path — merge-on-read, lineage, pushdown — not this raw-value projection.

Scoped reads resolve each immutable input independently: native Parquet field ids take precedence, externally registered files use their recorded name mapping, and inline chunks use the column identities and names at the chunk’s begin snapshot. Current catalog positions select logical columns only; they never select a physical column in an older schema. Unindexed nested children do not shift an indexed top-level field’s physical position. Files without field ids use historical names when no explicit mapping exists; if expired history prevents resolving an identity, the read fails. Hive partition mappings materialize their virtual columns from the file’s directory values, including percent decoding and partition-null rules.

Missing fields use initial_default, not the current insertion default. Before deriving keys, old physical values are converted to the indexed column’s current type with checked casts; an unsupported default or failed conversion returns a typed error. The same projection serves immediate and staged backfills, deferred repair, file registration, SQL deletes and updates, and delete-file removals. Projection bounds are checked before calling Arrow or Parquet APIs that assume valid positions.

A value is indexable only if its Parquet form and its inline Arrow form derive the same canonical bytes, so the two write paths collide as they must. That holds for the scalar types, strings, blobs, UUID (a 16-byte blob on both paths, once the inline body is Arrow-encoded losslessly), and the temporal types by their underlying integer count. It fails for a 128-bit integer: DuckDB writes HUGEINT to Parquet as a lossy double, so its data-file and inline forms disagree and distinct values could collide — CREATE INDEX on one is refused rather than built silently wrong.

Two placement consequences. The Parquet projection and the inline Arrow-body decode are core capabilities (arrow and parquet enter moraine) — entry derivation is catalog-domain logic, not shim marshalling (RFC 0001). And the core needs an object-store handle for data files: they live under DATA_PATH, not the catalog store. That path is fixed when the lake is created and does not reach the metadata attach on its own (DuckLake keeps its DATA_PATH and forwards only META_-prefixed options), so it is supplied once at creation via META_DATA_PATH and recorded in the global data_path metadata option at bootstrap — beside encrypted. From then on the recorded value is authoritative: the core serves it back as DuckLake’s ducklake_metadata data_path row (so a re-attach need not repeat it, and DuckLake refuses a DATA_PATH that disagrees), and the shim resolves the maintenance store from it, reusing the catalog store’s secret. A re-attach that supplies a conflicting META_DATA_PATH is refused rather than silently honoured. Data-file paths resolve against that store.

Re-derivation is idempotent. A registered file is not always new rows: rewrite files carry rows that already have entries. Multi entries re-derive as idempotent puts (the key includes the row id), and the unique check’s same-row-id no-op arm (Uniqueness enforcement) covers the rest — so DuckLake UPDATE and inline flush do not abort against their own existing entries. Compaction, whose files are all such rows, is skipped before the read rather than re-derived (Compaction derives nothing); idempotence is what makes the remaining overlap harmless, not what makes it affordable.

Uniqueness on the SQL write path. Enforcement hinges on one thing: the value-keyed put lands in the same atomic commit that adds the row (Uniqueness enforcement). Both paths do that — inline from the Arrow body, bulk from the scoped read — so the value’s provenance is irrelevant, provided both derive the same canonical bytes for a given value. That holds because the shim encodes the inline Arrow body losslessly, matching how DuckDB writes Parquet — a UUID, for one, is a 16-byte blob on both paths, not a blob in a data file and a string inline — so a value inserted inline and the same value written to a file collide as they must. Two further guarantees are load-bearing:

• A unique index’s scoped read is synchronous at commit. Deferring it would let a duplicate commit unchecked.
• A failed read aborts the commit. If the registered file cannot be read, the commit fails with a store error; the check is never skipped.

The Constraint message must avoid DuckLake’s four retry substrings ("conflict", "concurrent", "unique", "primary key" — RFC 0006): a unique violation is permanent, and retryable-looking text would spin DuckLake’s RunCommitLoop before surfacing. A concurrent collision is the opposite case — a genuine CommitConflict containing "conflict"; DuckLake retries (repeating the scoped read), the re-read finds the winner’s entry, and the permanent Constraint surfaces then. On a bulk violation the Parquet DuckLake already wrote is left orphaned for ordinary cleanup — space, not correctness.

Reads are explicit. DuckLake owns the planner, so nothing routes a predicate to an index. The extension path reads through moraine_index_lookup; the caller joins back to the table, whose scan DuckLake adjudicates against delete files. The optimizer rule above does not change that: it restates a join the caller already wrote, and never chooses an index. v1 scope: creation, uniqueness enforcement, and explicit equality, range, and NULL reads.

The upstream boundary is explicit. Moraine does not carry a downstream DuckLake binder or optimizer patch. If DuckLake defines native index metadata, the protobuf definition value’s reserved ducklake_index_id can map its stable identifier onto the existing index range; the reservation preserves that option but commits to no implementation. Native DDL, writer-supplied maintenance, and equality, comparison, or ORDER BY pushdown are upstream requests tracked in ../ducklake.md, not open work in this RFC.

Read-only attaches over an indexed store are unaffected.

Rewrite files: row-id resolution

The scoped read’s “embedded row-id column if present” rule (Coverage) is made concrete here. Source-verified in DuckLake: UPDATE (always), rewrite_data_files (always), and merge_adjacent_files (only when the merged files’ row-id ranges are not adjacent) append a trailing _ducklake_internal_row_id BIGINT column to the files they write, tagged with DuckDB’s reserved Parquet field id 2147483540 (MultiFileReader::ROW_ID_FIELD_ID); its catalog row carries row_id_start NULL. merge_adjacent_files and inline-data flush also append _ducklake_internal_snapshot_id (field id 2147483539), which index maintenance ignores. DuckLake’s reader resolves a row’s id as: the field-id column when the file carries one, else row_id_start + position, else a read error. Moraine’s scoped read applies the identical rule.

Column presence wins over row_id_start — the precedence is load-bearing, not a tiebreak. A flushed inline-data file carries embedded row ids and a non-NULL row_id_start (DuckLake records the file’s minimum embedded id there), and its ids may hold gaps: inline rows deleted before the flush are materialized out, but the survivors keep their original ids. Dense derivation against such a file writes entries under row ids the rows do not have — silent index corruption, no error raised. Any resolution that consults row_id_start first is therefore wrong by construction; the fallback order is fixed as column, then range, then refusal.

File-level row-ID statistics are derived metadata. The patched DuckLake writer records min/max under the same reserved field id for every new non-empty file and uses those values to prune the physical-file list for static and dynamic rowid filters. A missing row is “unknown” and keeps the file, so a file registered before the patch was installed reads correctly and is never pruned.

Every file-stat insert requires a snapshot, the reserved row-ID column included: a head-preserving maintenance batch carries unversioned state only. A repair tool for files that predate the writer would need the snapshot a reserved-stat insert once rode without.

Resolution lives inside the scoped read. The reader already fetches the file’s footer; discovering the field-id column there costs nothing and keeps the precedence rule in one place instead of at every call site. Callers state intent, two modes:

• DuckLake-parity — registration, delete-side maintenance, and index backfill. The caller passes the catalog row’s row_id_start verbatim (Option); the reader prefers the field-id column, falls back to the dense range, and refuses (Corruption — the catalog row and the file disagree) when neither exists. A NULL or negative embedded id is likewise Corruption.
• Ordinal — the extension-path registration helper, whose contract is positions for register_data_file to re-map onto a freshly allocated dense range. In this mode a file carrying the field-id column is refused: registering a rewrite file under new dense ids would fork its identity — readers honour the embedded column, the catalog would claim the dense range, and the index would follow the wrong one.

The delete side filters by position, not by pre-computed row id. A delete file names positions within its target; converting them to row ids before reading the target bakes in the dense assumption. Instead the killed positions ride verbatim to the target’s scoped read, which returns entries in file order — an entry is removed when its ordinal is named by a delete file or by an inline file-delete. DuckLake writes a physical file_row_number into ducklake_inlined_delete_<t>.row_id despite the column’s name, so both kinds name a position and one rule serves dense and per-row-id targets alike.

Maintenance stays derivation, never removal. Registering a rewrite file only re-derives entries that exist (the idempotent puts and the unique same-row-id no-op arm, Uniqueness enforcement) or adds entries for changed values (UPDATE: the paired delete file removes the old-value entries in the same commit). No register-side path stages an entry delete, so a rewrite cannot drop a surviving row’s entry — the property that makes derivation safe to run without knowing what a file holds. It is skipped in exactly one case, decided on the commit’s change set rather than the file’s shape: a commit that only compacts (Compaction derives nothing).

Indexed columns keep their positional location (Coverage): rewrite and flush outputs are written under the table’s current schema with the internal columns trailing, so table-column positions are undisturbed.

Embedding-API boundary. The verb surface has no way to register a per-row-id file — register_data_file allocates dense ranges, which is why its entries name rows by ordinal: the ids do not exist until the commit allocates them. Deletion never has that problem — the target is registered and its ids are known facts — so register_delete_file removals name rows by row id against every target, exactly the Coverage table’s (row_id, key values) contract: row_id_start + ordinal for a dense target, where moraine checks the id lies inside the target’s range (the same strength as an ordinal bounds check), and the embedded id for a per-row-id target, taken verbatim and trusted exactly as the entry’s values are — the writer read the target to learn its positions and values, and the row-id column sits in the same file. One shape, one staging path, no per-target rules. What stays out is a rewrite-registration verb: the embedding API cannot express a file that preserves row ids, indexed or not — that is absent compaction surface (RFC 0008 keeps compaction DuckLake-driven), not index maintenance, and would be its own RFC.

Format gate

An older moraine writer committing to an indexed table would maintain no entries. The sys/format check at open excludes those writers: this build accepts only format 9, which already includes the index subspace, staged builds, and deferred upkeep. New stores start at that format, and older stores must migrate before opening. Index commits no longer stamp the format independently. The index discriminant leaves the segment extractor (“first byte”) unchanged.

Reclamation

drop_index (and drop_table, which ends the table’s indexes with it) orphans the entry range. Entries are invisible the moment the definition ends, so reclamation is pure space hygiene: a bounded sweep deletes index/{index_id} in batches — never inside the dropping commit, whose batch must stay bounded.

RFC 0021 specifies and implements that sweep: Catalog::maintain discovers dead index ids by seeking through the index subspace (ids are monotonic and never reused, so an id absent from the live catalog is dead forever) and reclaims each range in head-preserving batches. It runs as one step of the maintenance pass. Batched scan-and-delete is the binding design. A SlateDB range delete could optimize the mechanism without changing its semantics; that upstream request is tracked in ../slatedb.md.

Verification

Nothing checks an index against the rows it covers. The entries are moraine’s own work on the extension path, and the predicate the pruning keeps is what makes a wrong entry cost a read rather than an answer — but a dead or missing entry is invisible until something trips over it. Production has found them by their cost: an index whose rebuild left 24.8 million dead entries swept them once per batch for hours before anyone noticed.

moraine_index_verify(catalog, schema, table, index) recomputes the entry set at the current snapshot through the same scoped reads the backfill uses — inline chunks, then every live data file, with the snapshot’s delete files applied — and diffs it against what the index holds:

count	meaning
stored	entries the index holds
expected	entries the live rows require
missing	an entry the rows require that the index does not hold
dead	an entry the index holds that no live row requires
mismatched	a unique entry under the right value naming another row

mismatched is separate because a unique key stores its row id as the value, so an entry can be present under the right value and still point somewhere else — neither missing nor dead, and the one case a key-only diff would call clean.

A read-write attach records certification after verification; a read-only attach reports counts and the certificate from the same pinned snapshot without writing. A read-write invocation may commit a new certificate snapshot. Verification costs as much as a build and holds the stored entry set in memory. A building index is refused because its entries are incomplete by design.

Three properties the counts give that nothing else does: a maintained index stays clean across insert, delete, update and compaction; a rebuild that loses entries is visible before a query pays for them; and the entry-source split above becomes testable rather than asserted, since a verifier pass is the last line an index test can assert.

The certificate

A pass through a read-write attach records what it found on the definition: a clean pass writes the snapshot it agreed at, and a pass that found any discrepancy clears an earlier agreement rather than leaving a stale one standing. moraine_indexes reports it as certified_at, NULL when absent. A read-only attach reports without writing.

This is not a fifth IndexState. Ready already means “serving lookups and enforcing uniqueness”, and whether something has checked the index is an orthogonal fact; a variant would force every existing match site to decide something it has no opinion on. It is a separate field, and the only state coupling is that a certificate requires Ready — a building or repairing index is short of the rows by design.

What withdraws it. Any write that changes the entry set: a staged build step, a rebuild, a deferred repair entering maintaining. A new definition starts without one. Ordinary maintained writes do not withdraw it, and that is the whole of what the certificate extends — trust in the maintenance path between the pass and now. Stated plainly: a certificate says at snapshot V the index matched the rows, and reading it at a later snapshot trusts every commit since V to have maintained the index exactly. That trust is bounded by how recently the verifier ran, so a deployment that wants a tighter bound runs it more often; it is not an argument the index is correct forever.

The race it closes. A pass reads at one snapshot and records at another, so the recording names the definition version the pass observed and is refused if the definition moved in between. A rebuild landing between a pass and its commit must not inherit the pass’s agreement.

What reads it. Positional DELETE requires a certified exact probe. Each optimizer probe reads at most 4,097 entries, with at most 32 equality probes in flight. A combined result above 4,096 candidates cancels pending probes and declines the optimization before row location; explicit lookup functions remain unbounded. The cap applies across equality keys, ranges, and NULL prefixes.

Ordinary selective scans retain their predicates and do not require a certificate. Verification is optional for index use, but required to omit predicate evaluation on the positional DELETE path.

Test obligations

Per RFC 0001 — store codecs get proptests, protocol claims get integration tests against real SlateDB on in-memory object_store:

• Encoding roundtrips + goldens. decode(encode(k)) == k for both entry kinds; golden vectors pin the index discriminant and the canonical encoding of every indexable type, including the float normalizations, NULL skip, and composite framing (("ab","c") ≠ ("a","bc")). The borrowed builder is differential-tested byte-for-byte against the former owned encoder across all scalar categories, directions, NULL orders, composite keys, NaNs, signed zero, and framing escape bytes. In-place physical finalization is compared with the owned Key::Index encoder under arbitrary values, index ids, unique shapes, NULLs, and row ids. Arrow extraction has the same differential coverage across every supported Arrow representation and overlapping projections; a multi-chunk commit proves every body is decoded once while its table-version schema is decoded once for the commit.
• Order preservation. For every indexable type, encode(x) < encode(y) iff x < y in the type’s SQL order (proptest); DESC reverses it, variable-length strings included ("ab" < "a"); a mixed (a ASC, b DESC) composite yields the declared order in one forward pass; NULLS FIRST/LAST place the null flag correctly under both directions.
• Comparison accessors. <, <=, >, >=, BETWEEN, and half-open bounds return exactly the matching live rows; a DESC index returns them high-value first; a leading-equality prefix plus a trailing range uses the index; a bare non-leading range is refused; equality stays a point-get on a unique index. moraine_index_range and a directions/nulls-carrying CREATE INDEX drive these end to end.
• Unique race. Two concurrent commits inserting the same unique value: exactly one lands; the other returns Constraint after its closure re-run — never two entries, never a lost insert.
• Benign distinct-value appends. Two concurrent appends of different values to one indexed table both land via the append-append path.
• Movement invariance. Insert inlined rows → flush → compact: lookups return the same rows throughout; the index range is byte-identical before and after flush and compaction.
• Located rows. File rows read back at their exact positions from dense and row-id-column files; inlined rows decode from their chunk; a row deleted at the snapshot is omitted; a column added after a file was written reads NULL; an older snapshot still serves a row deleted later, and a file the snapshot lacks is refused.
• Delete coverage. Store-resident delete (self-sufficient) and writer-supplied delete both remove entries; delete-then-reinsert of a unique value succeeds; a register_delete_file omitting entries on an indexed table is refused.
• Registration contract. Entry-less register_data_file on an indexed table → Constraint; with entries → covered lookups; ordinal→row-id mapping lands entries above the winner’s next_row_id under concurrent append retry.
• DDL interactions. create_index racing register_data_file on one table → CommitConflict for one side; drop_column/type-change on an indexed column refused; rename unaffected; backfill validates uniqueness (duplicate in existing rows aborts the create).
• Format gate. Open rejects stores below the minimum readable format until migration; index commits preserve the accepted format.
• Staged lifecycle. A staged build over a table too large for one batch, under concurrent inserts, deletes, and updates: lookups fail typed while building; after the flip, the index range is byte-identical to a from-scratch single-commit build over the same live rows. Intermediate steps serialize as inserted_into_table; publication commits remain altered_table.
• Staged delete races. A row deleted between S₀ and its batch is excluded via the delete bookkeeping; a row deleted concurrently with its batch collides on the entry key, the batch re-runs, and the entry is absent after both commits — for multi and unique kinds.
• Staged duplicate poisoning. A pre-existing duplicate discovered cross-batch poisons the build: the create surfaces Constraint, the definition ends, entries are reclaimed. A writer inserting a duplicate during building lands its rows — file and all — and poisons the index instead of failing; the same collision against a ready index still fails the writer, so the flip is what turns partial coverage into enforcement. A duplicate within one backfill step poisons it too, rather than failing the step.
• Staged resume and racing builders. A builder killed mid-build resumes from the persisted cursor with idempotent re-puts; two builders advancing one build serialize on the definition key, and a stale retry cannot regress the source cursor. A build cancelled with its cursor inside a row group resumes from that position and covers each row once.
• Point reads only. A unique probe is never a range scan; every probe resolution is a transactional point read under the concurrency window.
• Known-absent staging. A unique entry marked known absent stages its row id with no probe; two such claims of one value in a batch still collide. A build over fresh keys reports zero probes per step. A build resumed after a hand-committed step whose remaining rows duplicate a committed value still fails as a duplicate, which pins the filter’s rebuild from the index before any probe is skipped.
• Ordered read-ahead. Over several multi-row-group files, every row reaches the index exactly once and each committed step’s source cursor is strictly greater than the last; reads of different files and row groups are observed in flight at once, and a row-group read emits only its group at the group’s file ordinals.
• Ready-flip visibility. A write in flight across the flip re-runs (altered-table conflict) and commits under full enforcement — a duplicate in that write gets Constraint, not poison.
• Head-only lookups. index_lookup on snapshot_at(S) fails typed; on a pinned current snapshot it reflects that snapshot’s cut even as newer commits land.
• Scoped data-file read. A staged registration on an indexed table derives entries for exactly the indexed columns; a subsequent lookup returns the file’s rows; the read touches no non-indexed column. Golden file fixtures pin the reader against each indexable type. A staged register_delete_file removes exactly the named positions’ entries.
• Compaction skips derivation. A commit whose change set names only merge_adjacent or rewrite_delete leaves the index range untouched without reading the file it registers — pinned by registering a file that is not on the store at all, which a deriving commit could not commit. A change set mixing a compaction kind with any other still reads and derives.
• Rewrite idempotence. A rewrite file carrying a row-id column derives entries under the preserved ids; DuckLake compaction over an indexed table (unique included) leaves the index range byte-identical and never aborts on the rows’ own existing entries. An UPDATE-shaped commit (delete file plus per-row-id file with changed values) removes the old-value entries and lands the new-value entries in one commit; an unchanged indexed value survives its same-commit delete-then-re-add.
• Row-id precedence. A file carrying both the field-id column and a non-NULL row_id_start, with gaps in its embedded ids (the flushed shape), derives entries under the embedded ids — a golden fixture pins the precedence. A per-row-id catalog row over a file lacking the column fails Corruption; ordinal mode refuses a file that carries it.
• Rewrite delete side. A delete file targeting a per-row-id file removes exactly the named positions’ entries; an inline file-delete against one removes exactly the named row’s. Backfill over a table holding per-row-id files derives their entries under embedded ids. Embedding: register_delete_file removals name rows by id against any target — verbatim against a per-row-id file, range-checked against a dense one; an id outside a dense target’s range refuses with Constraint.
• SQL-path uniqueness. A staged registration whose file duplicates an existing unique value aborts with Constraint, message free of the four retry substrings — no retry storm; a non-duplicate registration lands and the next colliding one aborts.
• SQL surface. Native DDL and the introspection, verification, and lookup functions resolve the store handle and table from an attached catalog and drive the same core operations as the embedding API; CREATE INDEX backfills existing external files via the scoped read; a lookup joins back to the table under merge-on-read.
• E2E. DuckLake flows over non-indexed tables are unaffected end to end; a CREATE UNIQUE INDEX then a bulk INSERT that duplicates a unique value fails the INSERT without a retry storm (message-text contract), and one that does not duplicate lands and is found by moraine_index_lookup. Over an indexed table: UPDATE, then rewrite_data_files, then merge_adjacent_files (one adjacent merge, one not — dense and per-row-id outputs) all commit; lookups stay correct after each; a DELETE against the rewritten file removes its entries; CREATE INDEX on a table already holding rewrite files backfills them.
• File-located lookups. Each summary representation is chosen and intersected correctly — dense range, Roaring, and sorted vector — and the intersections are exact for both dense and sparse files. A duplicate physical row id across two current files returns both as candidates; an inlined row returns a NULL file id. An unreadable sparse file falls back to every requested row id remaining a candidate for it, proving the degradation is conservative rather than lossy. Over DuckLake: data_file_id projects, prunes statically and dynamically, and an indexed sparse-file lookup opens only the candidate Parquet files. Benchmarks report cache bytes, sparse-summary build time, located-lookup time, and Total Files Read warm and cold.

Alternatives considered

• Temporally versioned entries (begin/end, current/history-style). Buys index-accelerated time travel at the cost of read-modify-move on every row death, entry history joining RFC 0007’s GC surface, and a uniqueness check that filters dead versions instead of point-getting. A permanent hot-path tax to accelerate the path the keyspace treats as rare. Rejected.
• Derive-at-attach hybrid (persist external-file entries only, rebuild inline entries at attach). Attach cost grows with data, every lookup spans two structures, and the uniqueness check stops being a point-get. Rejected.
• A reverse map (index_id, row_id → key values) to make row-id-only deletes self-sufficient. Doubles entry storage and write amplification to spare deleting writers values they already read. Rejected; the writer-supplied contract keeps delete parity with registration.
• Location payloads (file id / chunk key) instead of row ids. One step shorter lookups; flush and compaction become index rewrites proportional to moved rows. Row lineage is the stabler identity. Rejected.
• Hashed fixed-width entry keys. Uniform key size, no cap — but collisions need verify-against-payload machinery and the order-compatible upgrade path dies. Rejected for v1; recorded as the oversized-value escape.
• Mark-stale on the extension write path (a DuckLake write flips the index to a stale flag). A stale unique index enforces nothing and says so only to callers who ask — silent degradation of the exact guarantee the feature exists to give. Rejected for the scoped read, which keeps DuckLake flows working and the index honest; stale-mode survives only as an unsettled option for non-unique indexes, where correctness is not at stake.
• Refusing the extension write path outright (this RFC’s first stance). Reading a registered file’s indexed columns is a bounded, merge-free projection — not the scan path the non-goal guards — so blanket refusal traded a real capability for a boundary that did not need defending. Superseded by the scoped read (Extension path).
• Modeling the index as a pseudo-DuckLake table (an invented ducklake_index served row-faithfully). Invents non-spec surface real DuckLake would never read and future versions could collide with. Native-and-invisible is the right shape. Rejected.
• Uniqueness by scan at commit (no persistent index; check by scanning the table’s rows). O(data) per commit against the index’s one point-get. The scoped read stays bounded to the one registered file precisely because the index covers the rest; dropping the index turns that into a whole-table scan. Rejected.
• Staged builds in multi form, converted at ready (build unique entries as (value, row_id) keys — faithful under duplicates — then validate and rewrite to value-only keys at the flip). Represents duplicates without poisoning, but the conversion is an O(entries) rewrite that itself needs staging, and the window where writers must maintain both key forms is a second protocol. Value-keyed-from-day-one plus the poison flag gets the same outcome with the machinery already on the page. Rejected.
• Blocking table writes for the build’s duration. Turns the build into one logical commit and deletes every race — by serializing a table for hours precisely when it is largest. The append-append Goal exists to forbid this shape. Rejected.
• Stale entries adjudicated at read (skip the delete-race machinery; let lookups filter dead rows like a scan does). Works for row location — candidates are already adjudicated by the consumer — but a unique index cannot carry stale entries: a dead row’s entry manufactures false Constraints at commit, where there is no adjudication step. Rejected.

Prior art: HelixDB on SlateDB

HelixDB (an OLTP graph-vector database) runs on the same substrate — stock SlateDB over object storage — making its index surface the closest available comparison. The engine is closed; what follows is read from its public Rust SDK (helix-db 2.0.6: IndexSpec, SourcePredicate) and its SlateDB fork, so the contract is observed and the on-disk key layout is not.

Near-stock SlateDB was enough. HelixDB/slatedb carries a handful of commits over upstream (reader snapshots, a multi-get batching point-gets) — no index primitives: no range-delete, no merge operator. The whole index family, uniqueness included, rides the same get / WriteBatch / prefix-scan surface this RFC assumes. A production index engine living without range-delete settles the Reclamation question: the batched sweep is a legitimate permanent design, not a workaround awaiting a SlateDB feature.

A wider taxonomy, the same equality core. IndexSpec spans equality, range (with a physical Asc/Desc direction), vector, and text. Only equality carries a unique flag — matching the decision here to key uniqueness on the value alone — and its “uniqueness for supported non-null values” doc confirms the NULL-exempt semantics, arrived at independently.

Range is equality plus committed order. RangeIndexDirection bakes the sort direction into the stored key, not applied at read time — exactly the shape this RFC adopts (Range and comparison queries): order-preserving bytes plus a committed order contract plus a per-column direction, realized by complementing the framed component. Independent convergence on the same design.

The pushdown boundary is drawn in the same place. HelixDB splits a restricted SourcePredicate (Eq/Neq/Gt/Between/StartsWith/And/ Or, used at source selection) from a general Predicate run as a scan-time filter: the index serves source selection, everything else filters during the scan. This RFC draws the same line one notch tighter — no range, so no Between/StartsWith on the fast path.

Where it diverges — and why. HelixDB manages indexes as runtime control-plane steps (create_index_if_not_exists) against a server that holds and authored every row; entries are the engine’s private business. moraine does not own the write path — a separate writer produces the Parquet — and that one fact drives both coverage models: the embedding writer supplies entries alongside the file it wrote (Coverage); DuckLake supplies nothing, so moraine derives them by the scoped read. HelixDB never meets the register-with-entries problem. The divergence is a property of the embedding, not a different answer to the same question.

Why equality-only, when HelixDB shows the substrate carries vector and text too. HelixDB models both over the same ordered KV surface: its HNSW persists vectors under (id, level) keys and the proximity graph as adjacency keyed (source, level, sink); its BM25 is an inverted index plus length/frequency tables. (Layouts read from its earlier LMDB engine; the modeling ports, since both are ordered KV stores with prefix scans.) So SlateDB could store these indexes; this RFC excludes them because of what they cost to read. An equality lookup is one point-get or one bounded prefix scan — fast even on a cold cache. An HNSW search is dozens of dependent point-gets down a graph, and on an LSM over object storage every hop that misses the block cache is an object-storage round trip: fast only while the whole graph stays cache-resident, seconds when it does not. Equality (and the range upgrade) fits RFC 0009’s read model; vector search does not, and that is the entire reason it is out. The boundary is read cost, not storability.

Automatic predicate coverage limits

Index selection keeps the 4 MiB probe gate, pinned-snapshot check, and transaction-local-insert fallback. Independent key lists expand to at most 4096 combinations. Full equality keys, non-unique equality prefixes, final comparison bounds, and NULL-bearing prefixes can supply candidates. A unique index’s incomplete non-null prefix declines: trailing NULL-bearing keys live in the separate multi-entry region and must not be silently omitted.

Explicit SQL lookup functions remain available for compatibility and benchmark comparisons. Ordinary SQL is the application-facing path; administrative index creation, verification, introspection, and dropping remain explicit operations.

The selective reader builds its metadata file list from resolved file IDs, including inline tables when a candidate has no file ID. It retains required predicates but does not execute optional pruning hints a second time. On the 524,288-row filter benchmark, the 192-key hole pattern’s warm median fell from roughly 56 ms to 11 ms with the candidate file list, versus 9 ms for the explicit lookup join. Benchmarks exercise ordinary predicates and retain the explicit join as a comparison, with exact result checks for every run.