Struct Graph 

pub struct Graph {
    pub redge: bool,
    /* private fields */
}

Fields

redge: bool

Mirror 0x04 keys so in_edges is a seek, not a scan of every edge. SACRIFICE (Law 4): one extra key per edge (+57% storage measured for marker edges in a prior build). Off = in_edges unsupported.

Implementations

impl Graph

pub fn new(store: Store) -> Result<Graph>

pub fn store(&mut self) -> &mut Store

pub fn store_ref(&self) -> &Store

pub fn commit(&mut self) -> Result<()>

Persist the allocator then commit. The counter rides the same commit as the data it numbers, so a replayed crash can never hand out an id twice.

pub fn checkpoint(&mut self) -> Result<()>

pub fn set_nav_fold_interval(&mut self, every: u64)

Tune how often fold_nav checkpoints (WAL disk bound; see nav.rs).

pub fn add_node( &mut self, ext: Option<&[u8]>, label: u64, props: &[u8], ) -> Result<u64>

Dense sequential id: the id policy IS the clustering policy (GRAPH.md lever 1). ext is the caller’s uuid/slug, resolved later by [resolve]; stored WITH the id so a hash collision is detected, not silently wrong.

pub fn resolve(&self, ext: &[u8]) -> Result<Option<u64>>

External uuid/slug -> id. One point read, paid at query entry, never per hop.

pub fn get_node(&self, id: u64) -> Result<Option<(u64, Vec<u8>)>>

pub fn add_edge( &mut self, ctx: u64, src: u64, ty: u64, dst: u64, props: &[u8], ) -> Result<()>

ctx = perspective / named graph; 0 = the base graph. Edge identity is the full key, so re-asserting within a ctx overwrites (set semantics) and two ctxs never collide.

This is the KERNEL key-value graph (keys::edge), matched here and in CONTRACT.md:518 and kernel/tests/graph_ctx.rs. It is a separate layer from the typed-collections 0x71/0x72 graph in src/index/graph/mod.rs: that layer’s element identity is decided by docs/GRAPH_CONTRACT.md §2.3 (PENDING, see EdgeKey’s doc comment), not by this one. Do not read this set-semantics claim as describing the Phase-2/3 collections graph.

pub fn out_edges( &self, ctx: u64, src: u64, ty: Option<u64>, ) -> Result<EdgeIter<'_>>

Out-edges, streamed: one seek then sequential. ty narrows the RANGE (ty sits between src and dst in the key), it does not filter.

pub fn in_edges( &self, ctx: u64, dst: u64, ty: Option<u64>, ) -> Result<EdgeIter<'_>>

pub fn nodes_with_label(&self, l: u64) -> Result<LabelIter<'_>>

Every node of a label, streamed off the 0x02 range.

pub fn set_prop(&mut self, prop: u64, value: u64, id: u64) -> Result<()>

Index one property value for a node. 0x0A | prop | value | id.

The caller chooses WHICH properties to index and encodes values with the order-preserving encoders in keys – this is CREATE INDEX as a write discipline rather than a schema. Blind write, like everything else.

pub fn update_prop( &mut self, prop: u64, old: u64, new: u64, id: u64, ) -> Result<()>

Change an indexed value. The caller supplies the OLD encoding, so the stale entry is retracted without a read – supplying it wrongly leaves a stale index entry pointing at this node (Law 4: the price of keeping writes blind; a scan re-checking the record would mask it, and 2b keeps index entries authoritative instead).

pub fn prop_range(&self, prop: u64, lo: u64, hi: u64) -> Result<PropIter<'_>>

All ids whose prop value lies in [lo, hi], streamed in value order.

pub fn prop_eq(&self, prop: u64, value: u64) -> Result<PropIter<'_>>

Equality on an indexed value: the (prop, value) prefix.

pub fn count_label(&self, l: u64) -> Result<usize>

Count a label’s members without allocating per entry.

pub fn count_prop_range(&self, prop: u64, lo: u64, hi: u64) -> Result<usize>

Count ids whose prop value lies in [lo, hi], zero allocations.

pub fn vec_seed(dim: u64) -> u64

The rotation seed a field of width dim gets at its first vector. Mixed from the dim so it is deterministic without being one constant everywhere (a rotation bug identical across stores would otherwise be invisible to cross-store comparison).

pub fn vec_meta(&self, field: u64) -> Option<VecMeta>

This field’s recipe, or None until its first vector arrives.

pub fn set_vec_meta(&mut self, field: u64, m: VecMeta) -> Result<()>

Install a precomputed vector recipe/high-water row. Bulk import uses the same metadata path as live writes after generating dock rows with vec_dock_rows.

pub fn clear_nav(&mut self, field: u64) -> Result<()>

Drop the derived Vamana graph while preserving the vectors and their scan-tier fingerprints. DROP INDEX removes an access path, not the values stored in the table; a later build starts again at watermark 0.

pub fn set_vec(&mut self, field: u64, id: u64, v: &[f32]) -> Result<()>

Store a node’s embedding under field. The FIRST vector written to a field fixes THAT FIELD’s dimension and recipe; every later write to it must match. A 1536-dim row landing in a 768-dim field is corruption at birth, refused here rather than discovered as a garbage distance later – and a 768-dim field is no longer the store’s business, so a second field of a different width is not a conflict at all.

pub fn delete_vec(&mut self, field: u64, id: u64) -> Result<bool>

Remove a vector AND its fingerprint. Both deletes ride the same commit: replay after a crash removes both or neither.

pub fn vec_dock_rows( enc: &Encoder, field: u64, id: u64, v: &[f32], ) -> [(Vec<u8>, Vec<u8>); 2]

The dock helper (2g.2): the two rows a bulk load must emit per vector, so no caller can create unsearchable vectors by forgetting the fingerprint. Feed the flattened pairs to Store::bulk_load. enc must be the encoder of field’s recipe – see Graph::vec_meta_row, which emits the row that records it.

pub fn vec_meta_row(field: u64, m: VecMeta) -> (Vec<u8>, Vec<u8>)

The recipe row a bulk load must emit beside its dock rows. Without it the codes exist and nothing can read them.

pub fn get_vec(&self, field: u64, id: u64) -> Result<Option<Vec<f32>>>

pub fn vec_distance( &self, field: u64, id: u64, query: &[f32], metric: Metric, ) -> Result<Option<f32>>

Distance to one stored vector. The scan callback borrows the record’s bytes from the pinned leaf (or the iterator’s one overflow buffer), and distance decodes f32 lanes directly from that slice (D23).

pub fn vec_dim(&self, field: u64) -> u64

A field’s width, 0 when it holds no vectors yet.

pub fn vec_bits_pub(&self, field: u64) -> usize

pub fn rescore( &self, field: u64, candidates: &[u64], query: &[f32], metric: Metric, k: usize, ) -> Result<Vec<(u64, f32)>>

Rank candidates by distance to query, best k first.

This IS the vector story (D20): traversal/labels/props FIND candidates, this ranks them. Heap holds k entries, never the candidate count; each candidate costs one point read. A missing vector skips the candidate rather than failing the query – RCA nodes without embeddings are normal, not errors.

pub fn rescore_all( &self, field: u64, query: &[f32], metric: Metric, k: usize, ) -> Result<Vec<(u64, f32)>>

Exact whole-field rescore with a k-bounded heap. Vector rows are one contiguous prefix, so this is one sequential cursor and retains neither the vectors nor the candidate set (D23, Law 1).

pub fn rescore_sorted( &self, field: u64, candidates: &[u64], query: &[f32], metric: Metric, k: usize, ) -> Result<Vec<(u64, f32)>>

Rescore an id-sorted candidate slice with one sequential vector cursor. The caller’s candidate slice is the query’s existing working set; this method adds only the k-entry heap and one cursor (D23).

pub fn distances_sorted( &self, field: u64, candidates: &[u64], query: &[f32], metric: Metric, ) -> Result<Vec<(u64, f32)>>

Score an id-sorted slice in one cursor, for expressions that genuinely need one score per output candidate rather than top-k.

pub fn nearest( &self, field: u64, q: &[f32], k: usize, metric: Metric, oversample: usize, ) -> Result<Vec<(u64, f32)>>

Vector-first search (2g): the nearest k ids to q across the WHOLE store, no prior candidate set. Two stages: (1) scan the fingerprint keyspace, scoring every code against the pre-rotated query – a bounded heap keeps only k * oversample candidates; (2) exact rescore (D23) of those candidates against the full f32 rows. The approximation can therefore only ever MISS a true neighbour, never misrank one it found; recall is measured, not assumed. RAM: the heap and one rotated query – never the store (Law 1).

pub fn nearest_par( &self, field: u64, q: &[f32], k: usize, metric: Metric, oversample: usize, threads: usize, ) -> Result<Vec<(u64, f32)>>

nearest, fanned across threads snapshot readers (2g.2): the code keyspace is split into contiguous id ranges (ids are dense, D13); each thread opens its OWN read-only snapshot (Law 6 machinery – no locks, no shared pool) and scans its slice into a bounded heap; the merged survivors are exact-rescored here. Visibility: the last PUBLISHED generation (snapshot semantics), where single-threaded nearest sees the writer’s own uncheckpointed tail too.

pub fn parallel_searcher( &self, field: u64, threads: usize, ) -> Result<ParallelSearcher>

Build a reusable parallel searcher over the CURRENT published generation. Readers are opened once and reused across queries – opening per query re-pays pool warmup every time (measured: slower than serial). Rebuild after a checkpoint if freshness matters.

pub fn insert_geo_new(&mut self, field: u64, id: u64, g: &Geom) -> Result<()>

Initial-build fast path. The caller has established that this field has no trusted old index, so there is nothing to read, verify, or delete: these are ordinary blind kernel writes (D10) and retain one geometry.

pub fn insert_geo_postings_new( &mut self, field: u64, id: u64, g: &Geom, ) -> Result<()>

SQL rows already own the exact GeoJSON payload. Its spatial index only needs Hilbert postings + outward bbox; duplicating the geometry would add a second write and a second durable copy for no read-path benefit.

pub fn geo_posting_rows( field: u64, id: u64, g: &Geom, ) -> Result<Vec<(Vec<u8>, Vec<u8>)>>

Pure build-side lowering for a SQL spatial index. CREATE INDEX can sort and pack these rows without invoking the live one-key-at-a-time maintenance path; values are the same outward-rounded boxes queried by geo_candidates.

pub fn replace_geo_postings( &mut self, field: u64, id: u64, old: Option<&Geom>, new: Option<&Geom>, ) -> Result<()>

Maintain a posting-only SQL spatial index. The old geometry comes from the row-change record, so no private copy or read-before-write is needed.

pub fn set_geo(&mut self, field: u64, id: u64, g: &Geom) -> Result<()>

Index or replace a geometry for (field, id) (2i, D31). Replacement writes and independently verifies the new rows before stale old postings are removed (Law 3).

pub fn clear_unpublished_geo(&mut self, field: u64) -> Result<()>

Remove debris from an index build that never published its registry. No query can trust this field while unpublished, so this drops no old usable state; a subsequent build starts from an unambiguous empty keyspace.

pub fn delete_geo(&mut self, field: u64, id: u64) -> Result<bool>

Remove a geometry and its postings; needs nothing from the caller (the stored geometry row supplies the old cells).

pub fn get_geo(&self, field: u64, id: u64) -> Result<Option<Geom>>

pub fn st_distance( &self, field: u64, id: u64, lat: f64, lon: f64, ) -> Result<Option<f64>>

Exact geodesic distance in METRES from (lat, lon) to the geometry of (field, id) – the ST_Distance atom. Point geometries are exact Vincenty; polygons are 0 when the point is inside, else the vertex-minimum (the e1 deviation, named in the contract); lines and multis are vertex-minimum.

pub fn within_radius( &self, field: u64, lat: f64, lon: f64, meters: f64, k: usize, ) -> Result<Vec<(u64, f64)>>

ST_DWithin + ordering: ids within meters of (lat, lon), nearest first, at most k. Point candidates answer from the posting alone (degenerate bbox = the point – zero payload reads); others read their geometry once.

pub fn in_bbox( &self, field: u64, xmin: f64, xmax: f64, ymin: f64, ymax: f64, ) -> Result<Vec<u64>>

Ids whose geometry bbox intersects the (lon/lat) box. Exact per the PostGIS && operator semantics: a BOX test, deliberately (their recheck=false posture); geometry-exact predicates layer above.

pub fn in_bbox_with_boxes( &self, field: u64, xmin: f64, xmax: f64, ymin: f64, ymax: f64, ) -> Result<Vec<(u64, BoxF)>>

SQL’s exact radius tier needs the outward bbox carried by each posting. Keep that metadata beside the id instead of discarding it and then reopening the posting (or the JSON row) merely to recover the same box.

pub fn for_each_bbox_candidate( &self, field: u64, xmin: f64, xmax: f64, ymin: f64, ymax: f64, visit: impl FnMut(u64, BoxF) -> Result<bool>, ) -> Result<()>

Stream each logical bbox candidate once. Multi-cell geometries choose the lowest query-covered posting that actually exists; checking at most the write-time MAX_CELLS alternatives avoids a candidate-sized dedup set.

pub fn knn_geo( &self, field: u64, lat: f64, lon: f64, k: usize, ) -> Result<Vec<(u64, f64)>>

k nearest geometries to (lat, lon): expanding-radius search – start at one fine cell’s span, double until k found (or the world is covered), then exact-rank. Same narrow-then-exact shape as vectors; cost bounded by the ring that satisfies k.

pub fn contains_point(&self, field: u64, lat: f64, lon: f64) -> Result<Vec<u64>>

Ids of polygons containing the point – ST_Contains(geom, point).

pub fn perspective(&self, ctx: u64) -> Result<EdgeIter<'_>>

Sorted-frontier BFS (GRAPH.md lever 2): each wave is sorted, so its edge-range lookups arrive in key order and walk the tree as one ordered sweep – frontier nodes sharing a leaf pin it once.

Returns nodes in the order first reached. SACRIFICE (Law 4): within a wave that order is key order, not insertion order; and seen grows with the reachable set – inherent to never revisiting. The contract’s “perspective subgraph”: every edge of one ctx, one contiguous range, cost ∝ that KG and never ∝ the store.

pub fn bfs( &self, ctx: u64, from: u64, ty: Option<u64>, depth: usize, ) -> Result<Vec<u64>>

impl Graph

pub fn clear_text(&mut self, field: u64) -> Result<()>

Remove every posting, norm and statistics row owned by one text field. A rebuild starts from an empty corpus; otherwise its document counters and folded terms describe both the old and new contents.

pub fn index_text(&mut self, field: u64, docid: u64, text: &str) -> Result<()>

Index text for (field, docid), blind writes only: one head row per distinct term, the norm row, and the head meta counters. Cost O(distinct terms) – never touches other documents (Law 2). Re-indexing the same (field, doc) must be preceded by delete_text.

pub fn index_text_build( &mut self, field: u64, docid: u64, text: &str, ) -> Result<()>

Backfill variant: corpus/document metadata and postings are still complete after every row, but repeated term-count rewrites are deferred to one bounded external aggregation in finish_text_build.

pub fn index_text_build_cached( &mut self, field: u64, docid: u64, text: &str, cache: &mut TextBuildCache, ) -> Result<()>

pub fn index_text_build_accum( &mut self, field: u64, docid: u64, text: &str, accumulator: &mut TextBuildAccumulator, ) -> Result<()>

pub fn begin_text_build(&mut self, field: u64) -> Result<()>

pub fn prepare_text_packed( field: u64, docs: &mut SortedRuns, scratch: &Path, ) -> Result<PackedTextCandidate>

Build a fresh text field directly as one immutable segment. The input is a replayable external sort of (docid_be, utf8_text) records. No row-per-posting head is ever installed: term/doc records are grouped into 128-document values before their range reaches graft_sorted_range. Live writes after publication continue to use segment zero unchanged.

pub fn prepare_text_packed_with_workers( field: u64, docs: &mut SortedRuns, scratch: &Path, worker_limit: usize, ) -> Result<PackedTextCandidate>

pub fn publish_text_packed( &mut self, candidate: PackedTextCandidate, scratch: &Path, ) -> Result<()>

Graft one privately built candidate in the caller’s deterministic single-writer order, then publish and independently verify it.

pub fn build_text_packed( &mut self, field: u64, docs: &mut SortedRuns, scratch: &Path, ) -> Result<()>

pub fn clone_packed_text( &mut self, source: u64, target: u64, scratch: &Path, ) -> Result<bool>

Copy a quiescent packed initial segment to another physical field id. This is how a BM25 build and a later SEARCH build over the same source text share tokenisation without sharing physical indexes. A field with any live head or merge history is refused so CREATE INDEX falls back to its ordinary source scan rather than copying a mutable shape.

pub fn finish_text_build(&mut self, field: u64) -> Result<()>

Finish an initial backfill by grouping compact (term id, exact word) counts outside the database. The accumulator owns 8 MiB regardless of corpus size and spills runs to scratch; only repeated terms need a second dictionary write because one-document terms already hold 1.

pub fn finish_text_build_accum( &mut self, field: u64, accumulator: TextBuildAccumulator, ) -> Result<()>

pub fn replace_text( &mut self, field: u64, docid: u64, _old_text: Option<&str>, new_text: &str, ) -> Result<()>

Replace one doc’s text (the UPDATE path). The head is the mutable tier, so the old HEAD rows are removed physically – dead-marking cannot express “these terms changed” – while folded copies in segments are dead-marked as usual and dropped at the next fold. (Dead-mark-only replacement resurrected the doc’s old head rows: “stale term still matches”, caught by the ported e1 suite.)

pub fn delete_text(&mut self, field: u64, docid: u64) -> Result<bool>

The deletion discipline (alive/dead bitmap, one value per segment): mark docid dead in the metadata row that owns its corpus counts. Postings are NOT touched – folds drop dead docs physically (Law 3 shape).

pub fn text_match_count(&self, field: u64, query: &str) -> Result<Option<u64>>

Count the union of exact query-term postings with one bounded block per active segment and term. This is the COUNT counterpart of ranked top-k: it never owns the matching document set.

pub fn text_match_doc_limit( &self, field: u64, query: &str, min_score: f64, limit: usize, ) -> Result<Option<Vec<(u64, f64)>>>

First limit BM25 matches in document-id order. Collection membership uses that same order, so an unordered SQL filter with OFFSET/LIMIT can stop its posting merge without changing which rows the old collection scan returned. Scores are computed while the term heads are resident.

pub fn text_postings( &self, field: u64, term: &str, ) -> Result<Vec<(u64, u64, u64)>>

All (docid, tf) postings for one exact term in field, across the head rows and every folded segment, minus dead docs. O(matches).

pub fn text_live_stats(&self, field: u64) -> Result<(u64, u64)>

Incremental live corpus counters used by BM25. This is a point read.

pub fn text_recount_stats(&self, field: u64) -> Result<(u64, u64)>

Slow diagnostic oracle: recount current per-document norm rows from scratch. Production scoring never calls it.

pub fn text_recount_term_doc_freq(&self, field: u64, term: &str) -> Result<u64>

Slow diagnostic oracle for one word’s live-document count. It scans per-document norms from scratch; production ranking uses the dictionary point row maintained by writes instead.

pub fn text_term_doc_freq(&self, field: u64, term: &str) -> Result<Option<u64>>

pub fn text_score_candidates( &self, field: u64, query: &str, cands: &[u64], ) -> Result<Vec<f32>>

BM25 for an already chosen candidate slice. Current-format stores do one field-stat point read, one term-frequency point read per distinct query term, and one norm point read per candidate. No posting extent is opened, so ten candidates cost ten document reads whether the term occurs in one hundred or ten million documents.

pub fn text_search( &self, field: u64, query: &str, k: usize, ) -> Result<Vec<(u64, f64)>>

BM25 top-k for a multi-term query in one field. Current stores merge packed posting cursors in document order and retain only a k-entry heap. Each cursor owns at most one decoded 128-document block. Legacy stores without maintained term statistics use the materialising compatibility implementation below until they are rebuilt.

pub fn fold_text(&mut self, field: u64) -> Result<()>

Fold the mutable head, then run size-tiered levels. At most seven segments remain at any level: the eighth is k-way merged into the next level. Every candidate is checkpointed and independently reopened and counted before the one-row active manifest can publish it.

pub fn text_prefix_terms( &self, field: u64, prefix: &str, limit: usize, ) -> Result<Vec<String>>

All terms of field starting with prefix, clipped to the limit most frequent (Manticore’s expansion rule: the rare tail of an expansion is mostly misspellings; keep the popular head).

pub fn text_fuzzy_terms( &self, field: u64, word: &str, max_edits: u32, limit: usize, ) -> Result<Vec<(String, u32)>>

Terms of field within max_edits (Levenshtein) of word – the typo walk. Terms are visited in sorted order per source; a full DP row per term with shared-prefix reuse is O(|term| * |word|) worst case but the row’s min bound prunes: when every cell of the row exceeds max_edits the whole SUBTREE of terms sharing that prefix is dead, and the walk seeks past it (restart scan at prefix-successor) instead of visiting each term (typesense’s trie-DP on our sorted keys; caps: typos by length 0/<5, 1/<9, 2 else).

pub fn text_search_instant( &self, field: u64, query: &str, k: usize, ) -> Result<Vec<(u64, f64)>>

Instant search (2h, the as-you-type shape): every token exact-or-typo expanded, the LAST token also prefix-expanded, documents must match ALL tokens (AND), ranked by (fewest edits used, then BM25 over the matched expansions). Typo budget by token length: 0 under 5 chars, 1 under 9, else 2.

pub fn text_search_instant_typo( &self, field: u64, query: &str, k: usize, forced_edits: Option<u32>, ) -> Result<Vec<(u64, f64)>>

The instant walk with the edit budget FORCED (SQL’s typo => n): the length ladder is a default, not a floor – a 4-char token gets 0 edits by default, so “warz” can only reach “wars” when the caller raises it.

pub fn text_segments(&self, field: u64) -> Result<Vec<u32>>

Every segment id present for field (0 = head, if it has meta).

impl Graph

pub fn hybrid_score( &self, cands: &[u64], expr: &ScoreExpr, k: usize, externs: &[&[f32]], ) -> Result<Vec<(u64, f32)>>

Rank cands by expr, descending, top k. Ties break on id ascending (deterministic under snapshots). externs supplies the Extern(i) columns; each must be cands.len() long.

impl Graph

pub fn nav_walk_diag( &self, field: u64, q: &[f32], ef: usize, ) -> Result<(Vec<u64>, HashSet<u64>)>

Diagnostic walk: like the query path, but also returns every id the beam VISITED (estimated), not only the ef it kept. Separates “the walk never reached the region” from “reached it but ranked it out”.

pub fn fold_nav(&mut self, field: u64) -> Result<u64>

Fold: wire the increasing-id tail plus explicit out-of-order pending ids into the graph, in id order. Cost ∝ new vectors, not the field.

pub fn nearest_nav( &self, field: u64, q: &[f32], k: usize, metric: Metric, oversample: usize, ) -> Result<Vec<(u64, f32)>>

Graph-accelerated nearest: beam walk over the graph, scan tier for the increasing-id head and explicit out-of-order pending set, then exact rescore over the union. Falls back to pure scan when no graph exists.