Building a Persistent, Quantized, Deletable HNSW in Rust — No hnsw_rs, No faiss, No BSL
The persistent PQ-HNSW path in Nano v3.32 is a from-scratch, in-house implementation. No hnsw_rs, no faiss, no third-party graph crate. Apache 2.0 end-to-end. Eight phases (P0–P7) over the merge branch feat/persistent-pq-hnsw, from design (87b0497) to the head-to-head benchmark on main (8699293). This is what was in each phase and why we built it ourselves.
Why in-house
Two reasons. Licensing. The strongest off-the-shelf Rust vector indexes are BSL or AGPL — fine for an internal tool, a problem for a database you want anyone to host or resell. Apache 2.0 was a hard constraint, which narrowed the options. Persistence shape. Most in-RAM HNSW crates assume the graph lives in a single allocation; we wanted a graph keyed into a RocksDB column family with a coarse per-index lock, so that open() restores from disk without rebuilding and a SIGKILL mid-insert recovers atomically with the row. Retrofitting that onto an upstream crate would have been worse than writing it.
P2 — the HNSW graph itself
Malkov & Yashunin's algorithm, level assignment via public-domain SplitMix64 (so reindexing is reproducible across machines without dragging in a CSPRNG dependency). The graph is a per-element neighbour list per level; we picked the layout that round-trips cleanly to RocksDB without a serialisation library — three column-family keys per element rather than a single blob, so partial updates during remove() don't rewrite the whole node.
P1 — persistence and recovery
The index lives in a single RocksDB instance under the __vidx: keyspace. open() walks the keyspace once on startup, restores the entry-point pointer, and is ready to answer queries — no graph rebuild, no codebook regeneration. Crash recovery is the standard RocksDB-WAL story: every insert() / remove() writes a batch; on restart, RocksDB replays the WAL and the index is whole. Coarse per-index locking — we explicitly did not chase fine-grained concurrency in P1; getting the persistence shape right was higher value than getting parallel writers to scale.
P3 — online deletes with neighbour repair
Tombstone-only deletes are the trap. They look fine in tests (recall stays high until you've deleted a few percent), and they look wrong in production six months later (recall drops, p99 climbs, you can't tell why). remove() in v3.32 walks the affected node's incoming-edge set and rewrites each neighbour's adjacency list to drop the deleted entry — the graph stays connected, the entry-point invariant holds, and recall doesn't rot.
compact() reclaims the tombstoned RocksDB keyspace when the dead-node ratio gets high. Same shape as RocksDB's own compaction, one level up.
P4 — Product Quantization with ADC traversal and two-stage rerank
PQ basics: split a D-dim vector into M sub-vectors of D/M dims each, k-means each sub-space into 256 centroids, store each vector as M bytes (the centroid id per sub-space). Distance between a query and a code is summed from M pre-computed lookup tables — Asymmetric Distance Computation. ~16× compression vs raw F32.
The trick that keeps recall: two-stage exact rerank. The graph traversal uses PQ codes (fast, approximate); for the candidate set returned at the top of the graph, we load the full vectors from disk and rerank against the query for exact ordering. The candidate set is a small multiple of k, so the rerank cost is negligible. PQ-vs-exact recall@10: 0.987 vs 0.989 on the canonical fixture.
One catch we fixed in v3.32.1: ProductQuantizerConfig::default_for_dimension picked too few sub-quantizers for common embedding dimensions, collapsing recall on any caller using defaults — including the SQL CREATE INDEX … USING hnsw PQ path and quantized_hnsw. New default: ~4 dimensions per sub-vector. The default-path regression test we added with the fix would have caught it; every prior PQ test passed an explicit config, which is how it slipped through. Found by the CodeKB MCP team's adoption smoke.
P5 — filtered KNN, evaluated during traversal
Post-filter is wrong for vector search. If a top-50 has 47 rows that fail your WHERE tenant_id = $1 filter, you get top-3 instead of top-k. The right shape is "top-k that pass the filter" — and the only way to get that is to evaluate the predicate inside the graph traversal, expanding the search until k passing neighbours are found. search_filtered takes a closure; the closure is called per candidate during traversal, not after.
P6 — multi-precision rerank vectors
The rerank vectors don't have to be F32. F16 (hand-rolled IEEE half — no half crate dependency) halves the rerank-store size; I8 scalar quantization quarters it. Pick the precision dial that matches your recall budget. Zero new dependencies — the conversion is a tight bit-twiddle loop.
P7 — validation and head-to-head vs main
Two reports shipped in-tree:
VALIDATION_REPORT_persistent_pq_hnsw.md— the feature's own recall / memory / latency characterisation, plus a persistence round-trip check (drop → reopen → identical top-10).BENCHMARK_main_vs_persistent_pq_hnsw.md— the no-regression gate.git worktreecheckout ofmainalongside the branch,cargo benchdefault features (sovector-persistis OFF and the new code isn't compiled), same machine, ~10 min apart. Theart_index_bench+vector_search_benchdeltas scatter bidirectionally (−13 % … +16 %) — machine noise, not code. The entire delta is gated behind#[cfg(feature = "vector-persist")], so the default binary is byte-identical to v3.31.2.
What's not there yet
SQL CREATE INDEX wiring for the persistent path. Today the new PersistentVectorIndex is a Rust library API — the same way the engine drives code_index and graph_rag_ingest_docs. Wiring it into DDL is on the roadmap and will appear in a later 3.32.x or 3.33.x release.
Also: PQ is L2-only. Embedding models that produce normalised vectors (BGE-Small, OpenAI text-embedding-3-*, most modern open models) work natively because cosine ≈ L2 on the unit sphere. Inner-product PQ is a separate problem we have not solved.
HeliosDB Nano is Apache 2.0. Repository: github.com/dimensigon/HDB-HeliosDB-Nano. Branch: feat/persistent-pq-hnsw (merged), commits 87b0497 through 4048e93.