joaoh82 / rust_sqlite / 25019854755

69%

push

github

Phase 7d.1: pure HNSW algorithm (no SQL integration yet) (#48)

First chunk of the split-up Phase 7d (see scope-correction in
docs/phase-7-plan.md): the algorithm itself, in a new
src/sql/hnsw.rs module, with no SQL integration.

The originally-estimated 700-900 LOC for 7d worked out closer
to ~1300 LOC end-to-end across algorithm + SQL integration +
persistence. Splitting into 7d.1 (this PR) / 7d.2 (SQL
integration) / 7d.3 (persistence) keeps each PR reviewable.

What this PR ships:

  - HnswIndex: in-memory multi-layer graph
  - DistanceMetric { L2, Cosine, Dot } with the same math as
    the vec_distance_* SQL functions from 7b
  - insert(node_id, vec, get_vec): full HNSW insertion —
    layer assignment via geometric distribution, greedy
    descent above the target layer, beam search + neighbor
    pruning at each layer the new node lives in
  - search(query, k, get_vec): greedy descent + ef_search
    beam at layer 0, returns top-k node ids in
    distance-ascending order
  - Custom MinHeapItem / MaxHeapItem wrappers around (f32, i64)
    so BinaryHeap works without f32: Ord drama. NaN sorts as
    Greater (worst possible candidate).
  - Internal xorshift64 RNG, seeded explicitly via new(),
    so tests can pin a deterministic sequence.

What this PR deliberately does NOT do (deferred to 7d.2 / 7d.3):

  - Any SQL surface — no CREATE INDEX, no INSERT plumbing,
    no query optimizer hook. The index is a pure Rust struct
    that callers feed manually.
  - Storing vectors. The algorithm calls a Fn(i64) -> Vec<f32>
    closure to fetch any vector it needs. In tests that
    closure pulls from an in-memory Vec<Vec<f32>>; in 7d.2 it
    will pull from the SQL table the index is attached to.
  - Persistence. The graph lives in HashMap<i64, Node> for
    now. 7d.3 wires it into the cell-encoded page format.
  - DELETE / UPDATE. Pre-existing nodes can't be removed.
    Soft-delete + lazy rebuild is the planned approach for
    7d.2/7d.3.

Parameters pe... (continued)

282 of 308 new or added lines in 1 file covered. (91.56%)

4765 of 6836 relevant lines covered (69.7%)

1.42 hits per line