# Memory Model

The engine is designed around cache-friendly owned arrays during build and
read-only mapped fixed-width arrays after persistence. PostgreSQL backends do
not share Rust heap memory or mapped snapshots. After auto-load, each backend
copies the artifact into an anonymous read-only mapping before typed views are
created. Format v6 keeps both CSR directions, filter values and dictionaries,
and relationship identities in that mapping; mutable changes remain compact
backend-local overlays.
This mapping is for rebuildable graph artifacts only; PostgreSQL still owns
authoritative table storage, WAL, MVCC, durability, and crash recovery.

## Backend Ownership

<SharedMemoryDiagram>
  <SharedMemoryBackends title="Engine struct">
    - `node_store` -> Arc-owned mmap ranges
    - `edge_store` and `reverse_edge_store` -> Arc-owned mmap ranges
    - `resolution_store` -> mmap section
    - `filter_index` -> mmap base plus sparse deltas
    - `relationship_identities` -> mmap base plus suffix overlay
    - `_mmap handle`
  </SharedMemoryBackends>
  <SharedMemoryTarget title="Backend-local snapshot">
    - anonymous read-only mapped pages
  </SharedMemoryTarget>
  <SharedMemoryHeap title="Per-backend heap after load">
    - **FilterIndex deltas** — sparse post-load mutations
    - **edge_type_registry** — bounded decoded labels
    - **relationship identity suffix** — identities added after load
    - **resolution_delta** — indexed post-load sync inserts
    - **edge_buffer** — post-load sync edge overlays
    - **tenant_membership** — backend-local state
    - **projection_snapshot** — decoded immutable durable segment maps pinned per generation
  </SharedMemoryHeap>
</SharedMemoryDiagram>

<Callout type="info">
The base graph is copied once into each loading backend's anonymous
read-only mapping, not expanded into per-field heap collections. Node arrays,
forward and inbound CSR arrays, relationship-ID sidecars, primary-key bytes,
resolution bytes, filter values and dictionaries, and relationship identities
view that mapping. Each backend still has a private virtual mapping; resident
pages are accounted as private mapped/page-cache-backed bytes rather than
described as shared extension memory.
</Callout>

## Runtime Resource Governors

Graph-owned transient allocations use a statement-local governor with typed
byte, row, work, disk, and elapsed units. A query or maintenance governor first
subtracts the selected engine's estimated backend-private residency from
`graph.memory_limit_mb`, then applies the narrower operation-specific workspace
cap. Major vectors and maps reserve against the governor before growth.

Traversal and query loops consume work at runtime and regularly check both
PostgreSQL interrupts and the optional graph elapsed breaker. One query
governor remains active across execution results, paging, sorting, output-row
construction, and hydration, so a subsequent phase cannot reuse memory still held by
an earlier phase. Load validates artifact and projection-file sizes before
decode. Sync retains accounting from catalog and payload preflight through
normalization, artifact staging, candidate validation, and governed manifest
publication. Compaction charges relevant source ranges, high-degree scratch,
output construction, and manifest publication while retaining the previous
generation on rejection.
Dropping the governor publishes a backend-local peak snapshot used by
`graph.resource_status()`.

The governor covers graph-owned Rust allocations. PostgreSQL executor memory,
client result buffering, and unrelated extension allocations remain governed by
PostgreSQL facilities such as `statement_timeout`, `work_mem`, role limits, and
connection admission.

## NodeStore

`NodeStore` uses a struct-of-arrays layout:

<StructDiagram title="NodeStore" fields={[
  { name: 'is_active', type: 'BitVec or [u8]', desc: 'packed tombstone bits; hot path' },
  { name: 'table_oids', type: 'Vec<u32> or [u32]', desc: 'source table OID by node index' },
  { name: 'primary_keys', type: 'Vec<String> or offsets+bytes', desc: 'source primary key by node index' }
]} />

Owned mode supports mutation. Mmap mode is read-only and uses validated byte
ranges whose store retains shared ownership of the mapping. In the persisted
format, active bits, table OIDs, primary-key offsets, and primary-key bytes are
all mmap-backed.

## EdgeStore

`EdgeStore` uses compressed sparse row:

<StructDiagram title="EdgeStore" fields={[
  { name: 'edge_offsets', type: 'Vec<u32> or [u32]', desc: 'length node_count + 1; offsets into target arrays' },
  { name: 'targets', type: 'Vec<u32> or [u32]', desc: 'neighbor node indices' },
  { name: 'type_ids', type: 'Vec<u8> or [u8]', desc: 'parallel edge label IDs' },
  { name: 'weights', type: 'Vec<u32> or [u32]', desc: 'optional parallel edge weights' },
  { name: 'relationship_ids', type: 'Vec<u32> or [u32]', desc: 'parallel source identity IDs' }
]} />

CSR neighbor lookup:

```text
node i neighbors = targets[edge_offsets[i]..edge_offsets[i + 1]]
node i labels    = type_ids[edge_offsets[i]..edge_offsets[i + 1]]
node i weights   = weights[edge_offsets[i]..edge_offsets[i + 1]]
```

CSR invariants:

| Invariant | Enforced by |
|---|---|
| `edge_offsets.len() == node_count + 1` | Builders and loader validation |
| `edge_offsets[0] == 0` | Loader validation |
| Offsets are monotonic | Loader validation |
| Final offset equals `edge_count` | Loader validation |
| Targets are less than `node_count` | Builders and loader validation |
| `type_ids.len() == targets.len()` | Builders and section sizes |
| `weights` empty or length `edge_count` | Builders and loader validation |

## Loaded Artifact Memory Split

| Structure | After `load_graph_file()` |
|---|---|
| `NodeStore.is_active` | mmap-backed |
| `NodeStore.table_oids` | mmap-backed |
| `NodeStore.primary_key_offsets` and bytes | mmap-backed |
| Forward `EdgeStore.edge_offsets` | mmap-backed |
| Forward `EdgeStore.targets` | mmap-backed |
| Forward `EdgeStore.type_ids` | mmap-backed |
| Forward `EdgeStore.weights` | mmap-backed when present |
| Forward `EdgeStore.relationship_ids` | mmap-backed |
| Inbound `EdgeStore` parallel arrays and relationship IDs | mmap-backed |
| `ResolutionIndex` | mmap-backed section |
| `FilterIndex` immutable values and text dictionaries | mmap-backed; sparse mutations stay in heap deltas |
| `edge_type_registry` | bounded labels decoded into backend heap |
| Relationship identity descriptors and source keys | mmap-backed; post-load identities use an owned suffix |
| Sync overlays | backend-local heap |

## FilterIndex Storage

`FilterIndex` stores registered traversal filter columns by internal `node_idx`.
It chooses dense or sparse storage based on build-time populated count.

```text
FilterIndex
  columns[]
  storage[]
    Dense values + present bitmap
    SparseBool true/false/present bitmaps
    SparseLookup value -> bitmap
    SparseOrdered sorted (node_idx, value)
  text dictionaries[]
```

Sparse threshold:

```text
populated_count * 100 < node_count * 15
```

That is, under 15 percent populated uses sparse storage.

## ResolutionIndex

The resolution index maps:

```text
(table_oid, primary_key) -> node_idx
```

Build mode accumulates compact entries. Finalization serializes a sorted array.
Mmap mode performs binary search directly over the persisted bytes.

## Memory Estimate

`Engine::estimated_memory_used_mb()` estimates:

```text
nodes * (active bit + table_oid + average primary key)
+ forward CSR arrays
+ inbound CSR arrays
+ schema-direction flags
+ resolution index
+ bounded FilterIndex and relationship-identity overlay heap
+ edge overlay buffer
```

`graph.estimate()` and build preflight use a separate conservative estimate
from PostgreSQL row estimates before allocating the engine.

When the engine is loaded from a `.pggraph` file, the anonymous artifact
snapshot and its resident page-cache-backed bytes are counted as
backend-private mapped memory. Filter and relationship-identity deltas, the
registry, and other overlays are additional backend-private heap allocations.
The public shared-memory profile columns remain for 1.x compatibility and
currently report zero.

## Mmap Materialization For Sync

Mmap-backed stores are immutable. When sync needs to mutate nodes, the engine
materializes the mmap node store into owned arrays:

<PipelineDiagram>
  <PipelineStep title="mmap NodeStore" />
  <PipelineStep arrowLabel="first node mutation" title="owned NodeStore copy" />
</PipelineDiagram>

Edge mutations do not rewrite CSR. They live in `edge_buffer` overlays until a
maintenance rebuild.

## Mapped Layout Safety Boundary

The loader copies the artifact into an anonymous mapping, makes it read-only,
and validates the complete snapshot before creating mapped stores. A private
owning artifact retains that mapping in `Arc<Mmap>` and is the
production construction boundary for node and edge views. Each view owns an
`Arc` clone, so field order, engine replacement, or dropping the loader's local
handle cannot invalidate a safe store method.

| Type | Validation |
|---|---|
| `ValidatedGraphLayout` | section descriptors, ordering, bounds, sizes, alignment, both CRCs, both CSR directions, target bounds, primary-key offsets, filters, dictionaries, identities, and UTF-8 |
| `MmapNodeArrays::new_for_artifact` | owning byte ranges, active byte count, `u32`/`u64` alignment, complete primary-key offsets, terminal byte count, UTF-8 boundaries, and native endian policy |
| `MmapEdgeArrays::new_for_artifact` | owning byte ranges, optional weights, relationship IDs, `u32` alignment, monotonic CSR offsets, terminal edge count, target bounds, schema-direction flags, and native endian policy |

The persisted format is little-endian. Native typed views over the snapshot are
therefore enabled only on little-endian targets; other targets receive an
incompatible-version error with rebuild guidance. The remaining unsafe blocks
only form typed slices from already validated, aligned ranges and carry local
`// SAFETY:` proofs. Safe accessors check node indexes and CSR offsets locally,
returning empty or absent results for out-of-range requests.
