cozo prior art for the shared storage substrate: MVCC key encoding, capability-typed storage trait, disk-native index reference

[forkwright]

Finding

cozodb/cozo (MPL-2.0) is a working implementation of the architecture pinax and heurema are both building from zero code: a swappable-backend storage trait carrying MVCC time-travel semantics (pinax's stated scope — MVCC, per-page encryption, changelog-as-primitive), with a disk-native vector index built directly on that same trait (heurema's HnswIndex, currently a stub returning NotYetImplemented). Three verified patterns extend pinax's existing candidate lineage in STORAGE.md § Sovereign SQL engine reference map (turso, redb, fjall, sled, cr-sqlite; cross-repo planning at forkwright/kanon#407) with a sixth source. Two land directly in pinax's storage/MVCC layer; the third is heurema's forward reference to that same trait, read now because heurema's index will sit on whatever capability shape pinax's ground-floor design settles on — pricing that dependency in before either repo has a line of code is cheaper than retrofitting it after.

A fourth cozo-derived pattern surfaced in the same pass — a mislabeled FTS scoring formula (fts/indexing.rs:231-246) — but it is a pure algorithm-correctness finding with no storage or index-substrate dependency. It is out of scope here and noted once, below, rather than given full treatment.

One further note on scope: a fifth cozo pattern exists in the source material (cozo's join-ordering pass does no cost-based reordering at all — join order is source order) but it is routed to aletheia/krites, not pinax or heurema, and is excluded from this issue on that basis.

Candidate table

Repo	Licence	Extract for	Disqualifiers
cozodb/cozo	MPL-2.0	MVCC "as of time T" key encoding, O(entities touched) not O(history stored) (cozo-core/src/data/value.rs:99-136, cozo-core/src/data/tuple.rs:54-84); narrow swappable-storage-trait shape (cozo-core/src/storage/mod.rs:30-51); disk-native HNSW-on-KV-rows with MVCC canary-key conflict detection, read as heurema's forward reference (cozo-core/src/runtime/hnsw.rs:539-678)	Time-travel gating mechanism for the sled/tikv backends is not identified in this evidence (cozo-core/Cargo.toml:50-60 documents the limitation, not the cause); the capability-check-via-panic shape (storage/mod.rs:71-91) is explicitly rejected below, not extracted; no encryption analog exists anywhere in the crate (zero hits for "encrypt" across cozo-core/src); citations are recorded as path:line without a pinned commit SHA — see Desired correction

Patterns

P1 — Time-travel as a pure key-encoding convention

What: Validity timestamps are stored as ValidityTs(Reverse<i64>) so that within one entity's key range, the newest version sorts first in the store's native ascending byte order — no secondary index needed. check_key_for_validity does the range-scan work for a query "as of time T": if the version at the current key is newer than T, it computes the exact next key to seek to, jumping past every remaining newer version of that entity in one step (not a linear skip); if the version at-or-before T is a retraction, it returns a seek key past the entity entirely; otherwise it returns the tuple as the answer. This makes "the database as of time T" cost O(number of distinct entities touched), not O(total historical versions stored) — achieved with one encoding rule plus a scan helper, not a specialized MVCC storage engine.

Evidence: cozo-core/src/data/value.rs:99-136 (Validity/ValidityTs, Reverse-ordered timestamp); cozo-core/src/data/tuple.rs:54-84 (check_key_for_validity, all three branches)

Verdict: adopt-later. Trigger: pinax's first commit against the MVCC / changelog-as-primitive module — the encoding is the ground-floor decision for that module, not a follow-up to it.

Disqualifiers: cozo's own feature matrix contradicts a naive "fully storage-agnostic" reading of this encoding: sled and tikv are explicitly documented as not supporting time travel ("The Sled engine does not support time travel" / "The TiKV engine does not support time travel", cozo-core/Cargo.toml:50-60), even though the encoding scheme itself is engine-agnostic on its face. The actual gating mechanism — most likely a RocksDB-specific compaction filter for garbage-collecting old versions, absent for sled/tikv — is not identified in the cited evidence. Verify the real reason for that gap before assuming the scheme ports to every backend pinax might target; portability should not be taken on faith from the encoding code alone.

P2 — Narrow swappable-storage trait, adopted; capability-check-via-panic, rejected in the same pass

What: Storage<'s>/StoreTx<'s> give a minimal, well-factored interface that five different engines (mem, two generations of RocksDB, SQLite, sled, TiKV) implement against — a five-method core surface is a sound shape for a swappable-backend trait on its own. But capability gaps within that trait are handled as default methods that panic: par_put/par_del default to panic!("par_put is not supported") / panic!("par_del is not supported"), and the only guard is a separate supports_par_put() -> bool method the caller is trusted to check first. Get the check-then-call order wrong anywhere in the codebase and it is an unrecoverable crash instead of a compile error or a graceful Result. The same pattern recurs one level up: sled and tikv are marked "highly experimental" and explicitly lack time-travel support — a second capability gap expressed purely in a doc comment, not the type system.

Evidence: cozo-core/src/storage/mod.rs:30-51 (Storage trait, 5-method surface); :71-91 (StoreTx put/supports_par_put/par_put/del/par_del — the bool-then-panic pattern); cozo-core/Cargo.toml:50-60 (sled/tikv marked highly experimental, explicitly missing time-travel support)

Verdict: adopt-now, for the narrow-trait-over-swappable-backends shape, as a direct input to pinax's first storage-trait cut — pinax has zero code, so this is the ground floor. non-adopt, in the same pass, for the panic-behind-a-bool-flag capability check: land the rejection as a stated "do not repeat" alongside the adoption, not as later cleanup once callers already exist that could get the check-then-call order wrong.

Disqualifiers: covers only the swappable-KV-plus-MVCC half of pinax's stated scope. pinax's other named requirement, per-page encryption, has no analog anywhere in cozo — a case-insensitive search for "encrypt" across cozo-core/src returns zero matches. This pattern does not validate or inform pinax's encryption design; that half of pinax has no reference material in this repo.

P3 — Disk-native HNSW on the same storage substrate (heurema forward reference)

What: hnsw.rs implements HNSW directly on top of the generic Storage/StoreTx trait rather than as an in-memory library: each proximity-graph edge is a (level, from_key, ..., to_key) row, read via prefix scan and greedy-searched per layer with a priority queue and an ef-bounded result set. Insertion writes a second, separate "canary key" alongside the real entry-point pointer specifically to detect the race where two concurrent inserts could each believe they own the new global entry point, which would silently leave part of the graph unreachable — a real MVCC-safety mechanism, not decoration. Deletion walks every layer removing the node's edges and repairs neighbor degree counters, but does not attempt to reconnect neighbors that lose their only remaining path; the code states the tradeoff directly rather than hiding it: "this still has some probability of disconnecting the graph. Should we accept that as a consequence of the probabilistic nature of the algorithm?" It ships with that question unanswered.

Evidence: cozo-core/src/runtime/hnsw.rs:539-587 (hnsw_search_level); :630-678 (hnsw_put_fresh_at_levels, canary-key conflict detection); :785-786 (verbatim self-admitted disconnection remark)

Verdict: adopt-later. Trigger: heurema's HnswIndex stub moving off NotYetImplemented. At that point, resolve the delete-time disconnection question as an explicit acceptance test or a repair-on-delete design choice — not inherited silently as a carried-over code comment. This pattern is read alongside P1/P2, not in a separate issue, because it is a consumer of exactly the storage-trait shape P2 settles for pinax: an index built disk-native on a shared MVCC store needs the same capability-typing P2 asks pinax to land at its ground floor, so the two are one design conversation, not two.

Disqualifiers: heurema currently has zero code for this index, so there is nothing to compare cozo's approach against yet — this pattern is asserted from cozo alone. If heurema's HNSW requirements end up favoring an off-the-shelf in-memory library (hnswlib/faiss-style) over a disk-native transactional index, this entire pattern is moot — that is a scope decision outside what this pattern can settle.

Out of scope, noted once: FTS scoring formula

cozo's default "tf_idf" score (cozo-core/src/fts/indexing.rs:231-246, default at data/program.rs:1297) combines the Okapi BM25 IDF term with a raw, unsaturated term-frequency count and no document-length normalization — neither real TF-IDF nor real BM25, and misnamed after the wrong one. It is a genuine finding relevant to heurema's own Bm25Index stub, but it is a scoring-math correctness question with no storage or index-substrate dependency, so it does not belong in this issue. It needs its own heurema issue, verdict non-adopt (reimplement Okapi BM25 correctly, with k1/b/avgdl, as its own option). A verifier correction already exists for it — commented-out k1/b fields adjacent to the FTS struct (data/program.rs:1006-1007) show the real parameters were scaffolded and abandoned rather than never considered — carry that correction into whichever issue takes the finding up.

Why this matters

Both pinax and heurema are zero code, which means every shape chosen in the first commit is a shape every later consumer inherits without a chance to object. Two of the three patterns above are priced now for exactly that reason. The reverse-timestamp encoding (P1) is the difference between "as of time T" costing O(entities touched) and O(history stored), and it is a key-encoding convention, not a storage-engine feature — it does not need to wait on any other design decision to land. The capability-typing question (P2) is cheap to settle on a trait with no callers yet and expensive to retrofit once heurema's HNSW module, or a future FTS or LSH index, is calling into it: cozo chose the panic-behind-a-bool shape once, and every one of its five storage backends has carried the discipline of checking supports_par_put() before calling par_put() — invisibly, by convention, ever since. A typed capability check turns "does this backend support parallel writes / time travel" into a fact the compiler enforces; a panic behind a bool turns it into a fact every future caller has to already know.

Desired correction

• Land the reverse-timestamp-suffix-plus-seek-skip key-encoding convention (P1) as pinax's MVCC "as of time T" scan primitive, at the changelog-as-primitive module's first commit — as its own encoding decision, not derived from cozo's DataValue/Tuple types.
• Land the narrow swappable-storage-trait shape (P2) as pinax's first storage-trait cut, with capability gaps expressed as a typed fact — an enum-of-capabilities, or an Option<&dyn Capability> associated item, checkable at compile time — never as a default method whose only guard is a bool the caller must remember to call first. Record the panic-behind-a-bool shape as the explicitly rejected alternative in the same design note.
• Carry the disk-native-HNSW-on-KV-rows-plus-MVCC-canary-key architecture (P3) into heurema's design notes for its HNSW module, cross-referenced against the capability shape pinax's P2 correction lands. When HnswIndex leaves NotYetImplemented, resolve the delete-time graph-disconnection question as a stated, tested contract instead of an inherited silence.
• File the FTS scoring-formula finding (cozo-core/src/fts/indexing.rs:231-246) as its own heurema issue, carrying the verifier's k1/b correction noted above; it does not belong in this one.
• Pin cozodb/cozo to a commit SHA before the citations in this issue are treated as stable — they are recorded as path:line only, and PRIOR-ART.md requires owner/repo@<sha> for exactly the reason that upstream moves and an unpinned citation is unresolvable within weeks.
• Add cozodb/cozo as a sixth row to STORAGE.md § Sovereign SQL engine reference map, using the candidate-table row above, once the SHA is pinned.

Done when: pinax's first storage-trait and MVCC-encoding commits explicitly cite or reject P1 and P2 in their design notes; heurema's HNSW design notes cite P3, including a stated resolution of the delete-disconnection question, before HnswIndex leaves NotYetImplemented; the FTS scoring finding has its own filed heurema issue; and the cozodb/cozo row lands in STORAGE.md § Sovereign SQL engine reference map with a pinned commit SHA.

Provenance

Read path only, per PRIOR-ART.md: every pattern here is a design prior read from cozodb/cozo (MPL-2.0) for its architecture. Nothing is copied — what lands in pinax or heurema is written from scratch, and this issue is the owed attribution of the idea, not a licence obligation. The candidate pool this pattern set was drawn from passed through an adversarial verifier that re-opened every cited path:line against the source and refuted roughly a quarter of all candidates it examined; the patterns above survived that pass. Citations are recorded as path:line without a pinned commit SHA, which is itself flagged above as a correction owed before this issue is closed.