perf(vector): migrate to InternalId = u32 throughout vector index + search

[mosuka]

Cross-cutting data-structure rewrite tracked under #537.

Current state

Doc IDs flow through the vector index as u64:

• HnswGraph::id_to_index: AHashMap<u64, usize> and nodes: Vec<Vec<Vec<u64>>> (vector/index/hnsw/graph.rs:21,27).
• ConcurrentHnswGraph::nodes: HashMap<u64, Vec<RwLock<Vec<u64>>>> (vector/index/hnsw/writer.rs:40-41).
• Candidate / ResultCandidate carry id: u64.
• IVF inverted lists hold Vec<(u64, String, Vector)>.

A single vector segment is capped at u32 entries elsewhere (IVF / Flat headers use vector_count: u32); the u64 is unnecessary inside the index.

Proposed direction

• Define InternalId(u32) with TryFrom<u64> at the segment boundary.
• HNSW neighbour lists: Vec<u32> (50% saving vs Vec<u64>).
• IVF inverted list ids: Vec<u32>.
• Pair with the CSR HNSW migration (perf(vector/index): Round-3 roadmap — Qdrant/LanceDB parity #535 children) so the neighbour arena is a single contiguous Vec<u32>.
• Keep external u64 doc id at the searcher result boundary.

Acceptance

• HNSW graph RAM drops by ~50% on the neighbour arrays.
• Candidate heap packed format (X-04) becomes natural.

References

• Lucene uses int ordinals throughout vector index.
• Qdrant uses u32 PointOffset.

Task list (2026-07-10 restart, full-scope route)

Context: sub-issue #709 (in-memory-only HnswGraph narrowing) was measured mixed and closed wontfix (2026-05-26). Its post-mortem concluded the remaining scope only has a chance as a bundled full-stack change (writer + searcher + IVF + on-disk format together), or as a cleanup without a perf gate. Since then, store-level VectorStore::search benchmarks (±0.06–3.5% same-code spread) give far better measurement than the raw HNSW benches #709 had to use (±6–19%).

Phase 0: Investigation & opportunity-ceiling gate

• Full ID dataflow map (graph / writer / searcher / IVF / flat / quantized / store) with file:line, classified as in-memory build / in-memory search / on-disk / API boundary
• On-disk format inventory: every site serializing ids, versioning/compat mechanisms, merge path
• Public API & bindings boundary check (no u32 leak; interaction with the shared u64 RoaringTreemap deletion bitmap)
• Capacity invariants (u32 segment caps, id monotonicity, segment-local vs global ids)
• Opportunity ceiling: RAM accounting at n=10k/100k/1M with fire-condition line-level evidence; explain how full scope differs from perf(vector/hnsw): narrow HnswGraph internal neighbour lists from u64 to u32 (in-memory only) (sub-issue of #686) #709's failure mode
• GO/NO-GO recommendation: perf-gated route vs no-gate cleanup route
• Post investigation summary as an issue comment

Phase 1: Implementation plan

• Scope/split decision: one core PR (~1,100 LOC, HNSW-confined) tracked in sub-issue perf(vector/hnsw): segment-local u32 ordinal graph + LVS1 v2 format (sub-issue of #686) #853; this issue stays the umbrella (follow-up candidates: permanent ahash swap, IVF/Flat cleanup, CSR flattening)
• Post plan as an issue comment

Phase 2+: Implementation

• Core PR: perf(vector/hnsw): segment-local u32 ordinal graph + LVS1 v2 format (sub-issue of #686) #853 done — PR perf(vector/hnsw): segment-local u32 ordinal graph + LVS1 v2 format (#853) #854 merged (main 2bd48afb): Deletion Search −56/−61%, sparse-id case −86%, multi-field −7%

[mosuka]

Splitting into sub-issues per CLAUDE.md sizing rules

This umbrella covers a cross-cutting type change touching HNSW (graph + writer), IVF, and the on-disk format — well over the "800 lines / multi-layer" threshold for a single PR. Split into four sub-issues so each lands with a focused review:

Sub-issue	Scope	Status
#709	HnswGraph in-memory Vec<u32> neighbour lists with serde compat shim (wire format unchanged)	OPEN — starting now
(b)	ConcurrentHnswGraph writer-side u32 narrowing	(file when (a) lands)
(c)	IVF inverted lists Vec<(u64, String, Vector)> u32 narrowing	(file when (b) lands)
(d)	On-disk format bump (drop the serde compat shim, full u32 wire)	(file when (b)/(c) land — needs format version bump)

Each sub-issue includes its own Phase 0 bench gate. (b)/(c)/(d) are deliberately not opened upfront — they will be filed when their predecessors land and the actual implementation plan can be written against current code rather than against a guess. This umbrella stays OPEN as the tracker.

[mosuka]

Phase 0 investigation report (full-scope restart)

Method: three parallel code sweeps (in-memory ID dataflow / on-disk serialization / API & bindings boundary), with the load-bearing hot-path claims re-verified by hand at line level. Full raw inventories are kept locally; the essentials:

Current structure

1. Ids are global, monotonic, never reused u64 — single allocator store/log.rs:447 (fetch_add, starts at 1), shared by lexical AND vector (engine.rs:331→349/352). Two consequences: (a) documents without vectors still consume ids, so max_doc_id ≫ vector count on mixed corpora; (b) the lexical standalone path has a shard-prefixed scheme setting the upper 16 bits (util/id.rs:31), so a global u64→u32 cast is unsound — a segment-local u32 ordinal with an ordinal → u64 table is the only viable design (same shape as Lucene's segment-local ords / Qdrant's u32 PointOffset).
2. The ordinal machinery already exists but is unused where it matters: HnswGraph has id_to_index: AHashMap<u64,usize> / index_to_id: Vec<u64> (graph.rs:21/24), yet adjacency lists store external u64 doc_ids (graph.rs:27) and every hop does a hash probe (get_neighbors(doc_id)). The four quantized pools key records by HashMap<u64,u32> (std SipHash); the position value side is already a u32 ordinal.
3. On-disk is u64 everywhere; compat tooling exists: single shared bump point LVS1 version: u16 (format.rs:70, read gate :307-313) covers HNSW/IVF/Flat; .delmap has a v1–v4 version-dispatch precedent. Merge copies ids verbatim, and HNSW records are written sorted by doc_id (writer.rs:1252), so "record order = ordinal" falls out naturally for a v2 format. entry_point uses a u64::MAX sentinel → becomes u32::MAX (safe: counts are u32-capped already in IVF/Flat headers).
4. No u32 can leak: all five language bindings, gRPC, CLI, MCP consume Engine::SearchResult { id: String } only; the internal u64 never crosses FFI. laurus::vector:: u64 signatures (VectorHit.doc_id etc.) stay unchanged — ordinals remain segment-internal. No public-API signature change required.

Opportunity ceiling (fire conditions verified by hand)

Why #709 failed but full scope can win: #709 only narrowed widths — the hash probes stayed, so only cache placement moved (= codegen noise). Full ordinalization removes the hash probes from the hot loop:

#	Fire condition	Today	With ordinals
1	field_idx.get(&doc_id) per distance calc (searcher.rs:119/131/144, std HashMap = SipHash)	1 probe per newly-visited neighbour = hundreds–2k per query × ~15–30ns	array index (~1–2ns)
2	get_neighbors(curr.id) hash probe per hop (graph.rs:117)	tens–hundreds per query	nodes[ord] direct
3	visited bitmap BitVec::from_elem(max_doc_id+1) per query (searcher.rs:703)	alloc+memset sized by the GLOBAL id space (inflates with churn / mixed corpora — the premise of #647)	sized by segment node count
4	u64 adjacency + 16-byte Candidate	cache density	halved (secondary effect only — #709 proved width alone is noise)

Ceiling: against the measured store-level baseline (del0pct = 83.0µs/query, n=10k int8, #848 bench), item 1 alone is ~7.5–45µs ≈ ~9–30% of the query, far above the store-level bench noise floor (±0.06–3.5%). Corroboration: the #685 gating profile already attributed 3.5% to SipHash on u64 doc-ids in a flat scan (traversal has a higher probe-to-work ratio). RAM: adjacency ~halves (n=100k: ~32MB → ~16MB) plus map shrinkage, matching this issue's ~50% estimate.

Honest caveats: (a) the estimate gets a mandatory 30-minute prototype gate before implementation — swapping the pool maps to ahash and measuring once bounds the real hash cost from below (ordinal gain ≥ ahash gain); (b) fresh-index fixtures can't show item 3 — one churned fixture (e.g. 100k ids consumed, 10k live) will be added; (c) cross-segment aggregation, deletion bitmaps (shared u64 RoaringTreemap), filters and result emission stay u64 — translation only at entry (filter/entry_point) and at admission (index_to_id[ord], ≈ ef times per query, the cheap fire condition per the #625 lesson).

Recommendation

GO on the full-scope, perf-gated route, structured as staged PRs (graph+writers+on-disk v2 → searcher+pools ordinal path → IVF/Flat cleanup), with the perf gate evaluated on the store-level benches at the final stage and intermediate PRs gated on correctness + no-regression. Estimated 2000–3500 lines total → will be split into sub-issues at the plan phase. If the prototype gate shows the hash cost is not real, this degrades early to a no-gate cleanup or a NO-GO before any large implementation spend.

Next: implementation plan (scope split, prototype-gate design, churned fixture spec, v1→v2 read-compat test plan) posted here after approval.

[mosuka]

Phase 1: approved implementation plan

Pre-implementation abort gates

• Phase 0a: A/A null-pair runs of the gate benches on the unchanged binary to size the session noise band.
• Phase 0b (throwaway branch, never merged): swap the pool/searcher/prefetch HashMap<u64, u32/usize> maps to ahash and run the gate benches once per side. Decision rule: ≥ ~3% on HNSW Graph Search/top10/50000 → proceed; ~0% → downgrade to a no-gate cleanup or NO-GO (lower-bound measurement: ordinal gain ≥ ahash gain, since ordinals remove the probe entirely).

v2 graph block (LVS1 version = 2, HNSW only)

has_graph u8 / entry_point u32 ordinal (u32::MAX = None) / max_level u32 /
node_count u32 / per node (ord = 0.. implicit, per-node doc_id DROPPED):
  layer_count u32; per layer: neighbor_count u32 + neighbor ordinals u32 × count

• Ordinal = rank in the ascending, deduplicated record doc_id sequence (derivable for both versions; records are already written doc_id-sorted).
• Flat/IVF keep stamping v1 (no gratuitous downgrade break); the read gate accepts 1..=2.
• Write-time guards: node_count >= u32::MAX errors (sentinel collision); graph node set ≠ unique record id set errors.
• Side effect: the graph block shrinks ~2x on disk.

Core PR (one PR, ~1,100 LOC, confined to laurus/src/vector/index/hnsw/ + format.rs)

1. format.rs: VERSION_ORDINAL_GRAPH = 2, MAX_SUPPORTED_VERSION, with_version(); read gate becomes a range check. CURRENT_VERSION = 1 stays the default stamp.
2. graph.rs: new reader-side OrdinalHnswGraph { entry_point: Option<u32>, max_level, doc_ids: Arc<[u64]>, nodes: Vec<Vec<Vec<u32>>> } with validated from_parts, #[inline] doc_id(ord) / neighbors(ord, level). The writer-side HnswGraph stays untouched — active-segment search is a flat scan, so build internals never need ordinals.
3. reader.rs: graph: Option<Arc<OrdinalHnswGraph>>; version-dispatched graph parse (v1 = legacy parse + rank translation with warn-and-drop for dangling ids; v2 = direct HashMap-free build + validation); new ord_to_pos: HashMap<String, Option<Arc<[u32]>>> — None (identity) iff single-field and no duplicate doc_ids, table only for legacy multi-field segments (missing = u32::MAX → f32::MAX, preserving perf(vector/search): VectorSearchParams.fields (field selector) ignored — no per-field routing #676 semantics).
4. searcher.rs: frontier Candidate { ord: u32, distance: f32 } (8 bytes); ResultCandidate stays u64 (translate at push via graph.doc_id(ord)), so rerank, the perf(vector/search): cardinality-driven mode selection for filtered HNSW (follow-up of #645) #738 brute-force mode, and result assembly are untouched; distance_ord() (no probe) / distance_doc() (cold paths) split; visited BitVec(node_count) instead of max_doc_id + 1; neighbor expansion via direct Vec index; quantized prefetch becomes base + pos * stride (no map). The perf(vector/search): no filter-aware HNSW graph traversal — allowed_ids is post-filter only #645 pristine/bookkeeping codegen split is preserved exactly.
5. writer.rs: build internals / ConcurrentHnswGraph / append path unchanged; write() stamps v2 and emits ordinals from the sort it already performs; load() reads both versions (writer stays doc_id-keyed in memory).
6. Tests (~250 LOC): hand-built v1 fixture read test (delmap-v3 precedent — none exists today), v1→append→v2 upgrade, footerless v1, v2 corruption cases (out-of-range ordinal, node_count mismatch), multi-field ord_to_pos, empty graph, determinism-test type adaptation.

Out of scope (follow-ups): permanent ahash swap, CSR flattening, pool field_index replacement, IVF/Flat ordinals.

Verification

• fmt / clippy (--all-targets --features embeddings-all, plus clippy 1.97 parity) / tests / cargo check -p laurus-wasm --target wasm32-unknown-unknown / --features pq-fastscan.
• Gate benches: HNSW Graph Search/top10/{1k,5k,50k}, HNSW ef_search/*, Deletion Search/del{0,10}pct, HNSW Multi-field Search (regression guard for the non-identity ord_to_pos path), HNSW Fallback (must be neutral), SIFT rerank if the fixture is present.
• New sparse-id bench case (doc_id = 50M + i*37, simulating a churned store): v1 allocates+zeroes a ~6.4MB visited bitmap per query vs ~6.3KB with ordinals — this is where the structural win shows (dense fixtures cannot show it).
• Pass criteria: ≥3% on dense 50k, ≥20% on sparse, ≤1% regression elsewhere (especially multi-field / fallback); deltas below the A/A spread are noise; SIFT top-k sets must be identical pre/post (pure representation change).

Tracked in the sub-issue for the core PR; this issue (#686) remains the umbrella.

[mosuka]

Umbrella status after #853 / PR #854 (merged)

The core of this issue is delivered: the HNSW read side is ordinal-addressed (u32), the LVS1 v2 graph block ships with full v1 read compatibility, and the acceptance criteria are met — graph RAM on the id-carrying structures roughly halves, the graph block halves on disk, and the packed 8-byte candidate format (X-04) landed in the searcher. Measured on the store-level benches: −56/−61% on Deletion Search, −86% on the churn-shaped sparse-id case.

What was deliberately NOT done, with rationale:

• IVF/Flat ordinalization: their id is 4 bytes inside a tuple dominated by a 24-byte String + heap Vector; no measurable ceiling. Recommend leaving as-is (the per-segment field-name dictionary, perf(vector/index): tighten on-disk record by promoting field_name to a per-segment dictionary #633, is the right lever for those tuples).
• Writer/build-side narrowing: the active-segment search is a flat scan (no graph traversal), so build internals stay doc_id-keyed by design — ordinals materialize at serialization.
• Small follow-up candidate: the Flat/IVF searchers still pay a per-candidate SipHash probe via field_position_index — a one-line ahash swap of the pool maps measured −30% on the HNSW path in the Phase 0b prototype and would be a cheap, bounded win there.
• The mmap/OnDemand 50k bench class could not resolve ±20% on the bench host (evidence in perf(vector/hnsw): segment-local u32 ordinal graph + LVS1 v2 format (sub-issue of #686) #853); flagged for observation, no action.

Given the above, this umbrella looks complete in substance.

[mosuka]

Closing as completed: the core migration shipped in #853 / PR #854 (merged as 2bd48af) — ordinal-addressed HNSW read side, LVS1 v2 graph block with full v1 read compatibility, and the measured wins recorded above (Deletion Search −56/−61%, sparse-id case −86%). The deliberately-skipped parts and small follow-up candidates are documented in the status comment above; they can be filed as individual issues if and when they become worthwhile.