HNSW Storage Mutation Contract

This document fixes the version-two logical page, insertion, recovery-state, and lock-order contract that PostgreSQL page/WAL adapters must implement. It is design input, not evidence that the current experimental access method is durable or ready to serve production queries.

Version-Two Page Envelope

The legacy prototype metapage calls itself version 1 while vector records are unversioned, native-endian repr(C) data. Version 2 never reinterprets those bytes. Zero, version 1, and future versions fail closed as rebuild-required.

All numeric version-2 payload fields use little-endian encoding. PostgreSQL retains its normal page header and line pointers; each pgContext page item starts with this 32-byte envelope:

Offset Width Field Contract
0 4 magic ASCII PGH2
4 2 format_version 2
6 1 page_kind meta 1, directory 2, node 3, adjacency 4, mutation descriptor 5
7 1 flags must be zero until assigned by a later version
8 2 header_bytes 32
10 6 reserved must encode as zero and decode as zero
16 8 generation published generation this item belongs to
24 8 mutation_id zero for published data; nonzero for pending work

Page/item roles after the envelope are:

Kind Required logical fields Lookup/use
Meta availability u8, root level u8, reserved u16, dimensions u32, next node id u64, structural published node count u64, tombstone count u64, entry node id u64 (u64::MAX means none), last-published mutation id u64 (zero means none), directory root page u64, descriptor-directory root page u64, pending count u16, pending capacity u16 (128), then 128 (mutation id u64, node id u64) slots where mutation id zero means empty Block zero only; reader-visible state and its publication identity are replaced last. Tombstone count never exceeds structural node count. The 2,048-byte reservation region is bounded and next node id is never inferred from published count.
Directory key kind u8 (node 1, adjacency 2, mutation descriptor 3, mutation entry 4), reserved [u8;7], generation u64, node or mutation id u64, layer or entry ordinal u16, reserved [u8;6], target page u64, target slot u16, reserved [u8;6], record revision u64 Node and adjacency lookup selects the greatest stored generation no newer than the published metapage generation. Descriptor keys use generation zero. The bounded directory also maps mutation id to its header and (mutation id, ordinal) to a complete entry. A lookup visits at most 8 directory pages; excess depth is rebuild-required.
Node node id u64, graph record token u64, record revision u64, heap block u32, heap offset u16, publication state u8, tombstone reason u8, tombstone epoch u64, layer count u8, reserved [u8;3], dimensions u32, then dimensions finite f32 values One incremental scoring payload. Heap offset is nonzero. Publication is unpublished 0, ready 1, or tombstoned 2; other values are rebuild-required. Tombstone reason is zero and epoch is zero unless state is tombstoned; v2 reason 1 means PostgreSQL VACUUM declared the TID dead to all supported snapshots. Tombstones retain vector/topology identity for traversal but are never answer candidates.
Adjacency node id u64, layer u16, reserved u16, neighbor count u32, record revision u64, then neighbor count node ids as u64 One complete bounded layer replacement. Partial neighbor-vector updates are forbidden.
Mutation descriptor Header: mutation id u64, node id u64, graph record token u64, descriptor revision u64, phase u8 (prepared 0, appended 1, outbound 2, rewire 3, mark-ready 4, ready-to-publish 5, published 6), reserved u8, outbound total/completed u16 each, rewire total/completed u16 each, reserved u16, then complete expected and target published states. Entry: kind u8 (outbound 1, rewire 2), has-expected-revision u8, ordinal u16, layer u16, neighbor count u16, target node u64, expected revision u64 (ignored when its flag is zero), then the complete bounded neighbor list. A fixed descriptor-directory root is created during relation initialization. Header and entry records may occupy multiple descriptor pages; the bounded directory addresses each entry without a scan. An entry is never a partial neighbor slice.

Both directory roots are initialized before the relation accepts insertions and their metapage locators do not swing during an insertion. Directory growth initializes unreachable pages first and links them through bounded data-page actions; a semantic mutation is replanned before locks if its final page set would exceed the Generic-WAL limit.

A complete published-state value contains generation u64, structural node count u64, tombstone count u64, has-entry u8, has-dimensions u8, format version u16, dimensions u32, entry node id u64, and last-published mutation id u64; absent optional values use their flags or the reserved zero mutation identity rather than stealing a valid node/revision value. Reserved bits and bytes must remain zero. Nonempty published state requires a nonzero last-published mutation identity, making an exact target-state replay distinguishable from a concurrent insert that chose the same root. Tombstone count is at most structural node count; their difference is the candidate-bearing count. Insert publication increments the structural count and preserves tombstone count. Tombstone publication preserves the structural count and increments tombstone count exactly once.

The durability codec child owns byte encoders/decoders, record-length checks, checksums, alignment tests, and corruption fuzzing. It may add validation but must not change these version-2 meanings without choosing a new format version.

The physical adapter’s bounded adjacency item codec carries a u32 node id, u32 layer, u32 neighbor count, four reserved zero bytes, then exactly that many u32 node ids. It rejects invalid layers, over-limit counts, reserved bytes, truncation, and trailing bytes before returning an owned layer.

Directory locators use a fixed 56-byte version-two item: key kind, generation, identity, layer/ordinal, target page/slot, and record revision, with every gap reserved as zero. The live insertion adapter will use these locators for versioned rewires and mutation descriptors.

Typed append returns the committed physical page and line-pointer location only after GenericXLogFinish, so a subsequent directory item can name an actual durable target rather than a speculative buffer address.

Readers process append-only adjacency revisions in physical order and retain the last complete (node, layer) item. This allows a later rewire to supersede an earlier complete layer without exposing a partial neighbor vector. If a crash leaves a node revision pointing at an absent later node record, recovery discards only those missing-node edges and falls back to exact scoring when the remaining topology is not restorable.

Test builds expose named physical failpoints before/after page initialization, append, rewiring, GenericXLogFinish, and metapage publication. Crash tests select these stable names; production builds compile the hooks out.

tests/heavy/hnsw_wal_crash_replay.sh performs an immediate PostgreSQL stop, restart, forced index plan, and exact-order oracle for each named boundary. Set PGRX_DATA_DIR to exercise PostgreSQL’s immediate-stop mode; the local developer fallback uses the configured pgrx stop/start lifecycle. The harness installs with pg_test and selects each hook through pgcontext.test_set_hnsw_physical_failpoint(text), an API absent from normal extension builds.

tests/heavy/hnsw_replica_promotion.sh uses a local replication role and slot, pg_basebackup -R, streaming catch-up, and pg_ctl promote; the promoted cluster then compares a forced HNSW order to the exact oracle. It removes its temporary replication role, slot, and pg_hba.conf rule during cleanup. The bounded before_append replay and standby/promotion paths are covered by the crash-recovery test suite; extended named-boundary coverage is planned. The widened fixture also exercises before_page_initialization by forcing a new typed data page.

scripts/run-pg17-recovery-report.sh --pg-major 17 --plan is the canonical, side-effect-free recovery manifest. Its --dry-run mode writes the same crash and standby rows without touching PostgreSQL; --approve is explicit, requires the primary pgrx data directory, and records complete approval only when every non-skippable row passes from a clean worktree.

HNSW indexes inherit PostgreSQL relation persistence: logged tables produce p indexes, unlogged tables produce u indexes, and temporary tables produce session-local t indexes. hnsw_relation_kinds.sh pins all three catalog values and a forced ordered HNSW lookup; only logged indexes participate in the WAL/standby evidence above.

Insertion And Publication

Node-id reservation advances a separate never-reused watermark under a standalone allocator lock on block zero. The update is an expected-watermark compare-and-swap and is idempotent by nonzero mutation id. A stale prepared reservation retries after releasing the lock. At most 128 pending mutation reservations are retained in the metapage’s fixed 2,048-byte region, so reservation does not allocate while locked. Mutation ids are monotone and never reused; their pending slot is released only after publication or explicit repair discard. An aborted or interrupted insertion may leave a hole; it never causes a node id to be reused and never increments the published node count by itself.

Order Semantic step Reader rule
1 Prepare all bounded encodings and expected revisions with no lock held. No reader-visible change.
2 Under the standalone allocator lock, reserve node id with expected watermark and persist the mutation-id mapping; then release. No reader-visible count/root change.
3 Append node as unpublished for the next generation. Ignore the node and any edge targeting it.
4 Write every complete outbound (node, layer) adjacency record. Continue ignoring the unpublished node.
5 Append complete next-generation adjacency revisions for existing nodes using expected current revisions. Never overwrite the published-generation record in place. Directory lookup at the old published generation still returns the old complete layer.
6 Mark the node ready after every required rewire succeeds. The old published generation/root remains authoritative.
7 Replace published metapage state last, comparing the complete expected reader state. Exact target-state replay for the same mutation is a no-op; any other state is a conflict. New count/root/generation become visible together.

The old root and its versioned node/adjacency lookup remain unchanged through step 5. Root publication rejects a missing, unpublished, wrong-generation, or corrupt node. Multiple mutation descriptors may coexist; there is no global assumption that only one insertion can be in flight. Old generations are reclaimed only by the later MVCC/VACUUM policy after no supported reader can use them.

MVCC, Tombstones, And Source Recheck

Ready means structurally complete, not visible to the active heap snapshot. An unpublished node is ignored for both traversal and answers. A ready node is a topology connector and candidate source only; a tombstone remains a connector but can never be returned. Consequently, a structurally published node left by an aborted transaction is harmless: a missing or invisible source row excludes it, and a later VACUUM callback may tombstone it.

HnswHeapTid { block u32, offset u16 }, graph record token, graph node ID, mutation ID, legacy algorithm point ID, and logical context_core::PointId are distinct identities. No TID-to-PointId cast exists. A collection query obtains its logical point mapping, ACL/RLS/predicate result, current source vector, and finite exact score from the authoritative PostgreSQL row under the statement snapshot. The ANN score is candidate-ordering input only and is never the final public score. A raw access-method scan likewise carries a physical TID only; its stored score is valid only while the VACUUM/TID-reuse invariant proves that the binding still names that indexed row version. Merely setting xs_recheckorderby is not a substitute because PostgreSQL requires recheck order values to be valid lower bounds.

TID reuse is fenced: before a reused (block, offset) can bind a new graph node, every older binding for that TID must have a published tombstone. The old node may remain in adjacency lists for routing, while only the fresh node can pass source recheck. Node IDs and mutation IDs are never reused.

A tombstone mutation binds mutation ID, node ID, graph record token, physical TID, expected node revision, previous complete published state, target generation, and target node revision. It proceeds in two reader-safe steps:

  1. Append the tombstoned node version and generation-aware locator using exact record-revision compare-and-replace. The previous published generation remains authoritative.
  2. Publish block-zero metadata alone, preserving structural node count/root and incrementing tombstone count once with the tombstone mutation as last_mutation_id.

Exact store and publication replay are idempotent. Changed node/record identity, revision, or complete published state is a typed conflict that releases locks and replans. An interrupted tombstone store is an unreachable next-generation orphan; a tombstoned entry point remains legal because it is traversal-only.

VACUUM uses a fixed-capacity two-phase protocol. With graph locks released, it copies at most 64 node/TID/revision identities, invokes IndexBulkDeleteCallback, and deduplicates callback-true TIDs. Callback false keeps the node ready; callback true is PostgreSQL’s dead-to-all-supported- snapshots authority. Only after the callback phase is sealed may the adapter prepare tombstone transitions, reacquire pages in canonical order, revalidate revisions, and later apply Generic WAL. Already-tombstoned nodes do not change counts. The batch flushes and checks interrupts before collecting more; there is no unbounded allocation. amvacuumcleanup never invokes the deletion callback or invents removals. tuples_removed counts newly published tombstones cumulatively, num_index_tuples counts candidate-bearing nodes, and estimated_count mirrors IndexVacuumInfo::estimated_count once the live adapter is implemented.

PostgreSQL Generic-WAL Units

Version 1 uses PostgreSQL Generic WAL; it does not define or require a custom resource manager or shared-preload library. PostgreSQL 17 permits at most four registered buffers in one Generic WAL record. The context-pg planner therefore stores 1..=4 unique page actions in fixed-capacity memory and requires their registration order to match strictly ascending lock order. Block-zero allocator and publication actions are always standalone.

Each data-page action also carries its exact logical write: node/adjacency id, layer, target generation, append-versus-revision mode, expected revision where applicable, descriptor expected/target revisions, and the directory keys being inserted or removed. Tombstone writes additionally bind graph record token and expected/target node revision. Node, adjacency, and tombstone locator writes are insert-only for the target generation. A rewire or tombstone plan whose record or locator action names the currently published generation is invalid before buffer acquisition; it cannot masquerade as a next-generation append.

One registered directory page may carry the two locator changes owned by the same atomic unit: append inserts the versioned node locator plus descriptor header locator, while a topology unit inserts the versioned adjacency locator plus immutable descriptor-entry locator. Both keys and their insert-only mode are part of the typed page action; they are not inferred by the codec.

The future physical adapter must modify only the shadow pages returned by GenericXLogRegisterBuffer, keep each buffer exclusively locked from before registration through GenericXLogFinish, use GENERIC_XLOG_FULL_IMAGE for a new page, and let GenericXLogFinish dirty pages and set LSNs. A failed plan is aborted before finish; successful finish applies every registered page in that unit. These requirements follow PostgreSQL’s Generic WAL contract.

HnswWalCriticalPlan is the enforced pre-finish typestate boundary. It consumes an already allocated semantic unit, revalidates the fixed 1..=4 page set and lock order, selects a static diagnostic without runtime formatting, and freezes the page actions into fixed-capacity storage. Its fallible staging closure is called exactly once per frozen page in lock order; any adapter error or named preparation failpoint returns before a finish permit exists, while Generic WAL can still be aborted normally. Only complete staging yields the linear HnswWalFinishPermit. That permit intentionally has no methods, formatting traits, callback, iterator, allocation, or Result surface. The later live adapter must add the sole completion path inside the same module immediately beside its direct GenericXLogFinish call. PostgreSQL performs the actual critical section internally in GenericXLogFinish; no Rust fallible work is allowed in or after that call before the permit is consumed.

Unit Registered page roles Published visibility after finish
Reserve node id block-zero allocator state only None. Expected watermark and mutation-id reservation advance together.
Initialize page relation extension serialization with no existing graph page held, followed by exactly one exclusively locked new nonzero directory, node, adjacency, or descriptor page as a full image None. The page remains unreachable.
Append unpublished node exactly one node page, exactly one descriptor-header page, and at most one locator page None. Node record and exact descriptor creation are one unit.
Write outbound layer exactly one adjacency page, one descriptor-header page, one immutable complete-entry page, and at most one locator page None. The entry payload and exact header CAS are bound to the same unit; layers are never combined into an unbounded record.
Replace neighbor layer exactly one next-generation adjacency page, one descriptor-header page, one immutable complete-entry page, and at most one locator page None. One complete expected-revision rewire and exact header CAS are a unit; multiple rewires remain an interruptible sequence without modifying old-generation adjacency.
Mark node ready exactly one node page and one descriptor-header page None. The ready record and exact header CAS are one unit; old metadata remains authoritative.
Publish root block zero only Complete expected-state compare-and-replace publishes generation, count, and root last and clears the metapage reservation slot.
Store tombstone exactly one node page and one generation-aware locator page None. The exact node/record identity and expected-to-target revision are stored for the target generation while the prior generation remains visible.
Publish tombstone block zero only Complete expected-state compare-and-replace preserves structural count/root, increments tombstone count once, and records the tombstone mutation identity.
Release/discard or descriptor cleanup block-zero allocator alone, or descriptor plus locator data pages in a separate unit None. Stale descriptor records after successful publication are harmless and cleanup is idempotent.

Every progress unit carries either descriptor creation or an exact expected-header-to-target-header revision transition. Outbound and rewire units also carry the immutable complete descriptor entry they persist. Completion is exposed to the state machine only after the future physical adapter reports a successful GenericXLogFinish.

If append, layer, descriptor, or locator placement would require five pages, the planner rejects it before lock acquisition. Page initialization and directory-link preparation may be split into deterministic unreachable-page units, but a node append or complete layer replacement is never truncated or silently divided. The insertion state advances only after the corresponding GenericXLogFinish succeeds.

Prefix And Recovery Classification

Applied prefix Persistent interpretation Required action
Prepared only no page change ready
Unpublished node only structurally ignorable orphan repair append or discard
Some outbound layers unpublished node remains ignorable repair-required: resume/discard outbound work
Some next-generation rewires old-generation directory entries and complete layers remain authoritative repair-required: resume revision-checked rewires or discard the unpublished generation
Ready node, old metapage old root/count/generation remain visible repair-required: validate then publish or discard
New metapage published insertion complete ready
Tombstone node version stored, old metapage harmless unreachable orphan; old generation and answer eligibility remain authoritative remain ready on the old generation; a later callback/reclamation pass may supersede or discard the orphan
Tombstone metapage published old node remains traversal-only; structural count is unchanged ready; callback replay does not double-count
Unsupported version/kind, missing descriptor, invalid published metadata/root, or corrupt required published page no trustworthy repair prefix rebuild-required from PostgreSQL source of truth

Discoverable insertion-descriptor repair-required states freeze new graph writes. An unreachable tombstone orphan has no pending-marker meaning and does not freeze writes. Readers may use only the previously published generation after validating it. Rebuild-required fails closed. These states never assume that transaction rollback removes physical index remnants.

Lock Protocol

  1. Allocation/encoding/validation completes before lock acquisition.
  2. Node-id reservation takes the allocator lock on block zero alone, compares and advances the persisted watermark, records the nonzero mutation id, and releases before any extension/data action.
  3. Relation extension is a standalone action with no graph buffer lock held.
  4. Existing directory/node/adjacency/descriptor pages are acquired by strictly ascending nonzero page id, with no duplicates, and released in reverse order. A semantic lock plan may inspect at most 8 pages, but one PG17 Generic WAL unit registers and mutates at most 4.
  5. Metapage publication locks block zero alone after all data actions. The metapage lock is never held while extending or acquiring a data page.
  6. If a target set, allocator watermark, complete published state, or record revision changes, release locks and replan; never upgrade in place.
  7. No SPI, heap callback, formatting, allocation, or user-defined code runs while these locks are held.
  8. VACUUM copies a bounded identity batch, releases every graph lock, invokes the deletion callback, seals the callback phase, and only then reacquires pages for revision validation and WAL. Callback false and long-snapshot visibility never create tombstones.

The typed unit model fixes action boundaries but does not emit WAL. Physical codecs, live GenericXLog* calls, failpoint-driven crash replay, standby correctness, live callback consumption, forced TID-reuse/HOT/savepoint/long- snapshot coverage, accurate bloat diagnostics, relation-kind behavior, and proof that current callbacks obey this protocol remain later gates.