spacedb_vector/index.rs
1//! The on-node vector index — *query embedding in, top-k out, corpus stays*.
2//!
3//! The index holds the corpus: `(id, embedding)` entries that **never leave the
4//! node**. A [`search`](VectorIndex::search) takes a query embedding and returns
5//! only the top-k [`Match`]es — ids and similarity scores. The return type makes
6//! the privacy property structural: there is no way to read a stored vector back
7//! out of a search; the most an authorized caller learns is *which* items are
8//! near their query and *how* near.
9//!
10//! ## Algorithm
11//!
12//! S3 ships an **exact flat k-NN** search (scan every entry, rank, truncate). For
13//! a home-scale corpus that is correct and fast, and — unlike an approximate
14//! index — has perfect recall. Sub-linear ANN (HNSW / IVF-flat) is an optimization
15//! for very large corpora behind the same [`VectorIndex`] surface, deferred until
16//! corpus size demands it.
17
18use std::cmp::Ordering;
19
20use crate::error::{VectorError, VectorResult};
21
22/// How similarity is measured. `search` always returns the highest-scoring
23/// entries, so every metric is oriented "higher = more similar".
24#[derive(Clone, Copy, Debug, PartialEq, Eq)]
25pub enum Metric {
26 /// Cosine similarity in `[-1, 1]` (1 = identical direction). Magnitude-invariant.
27 Cosine,
28 /// Raw dot product (higher = more aligned and larger).
29 Dot,
30 /// Negative Euclidean distance (0 = identical, more negative = farther).
31 Euclidean,
32}
33
34impl Metric {
35 fn score(&self, a: &[f32], b: &[f32]) -> f32 {
36 match self {
37 Metric::Cosine => {
38 let (na, nb) = (norm(a), norm(b));
39 if na == 0.0 || nb == 0.0 {
40 0.0
41 } else {
42 dot(a, b) / (na * nb)
43 }
44 }
45 Metric::Dot => dot(a, b),
46 Metric::Euclidean => -l2(a, b),
47 }
48 }
49}
50
51/// A search hit: which entry, and how similar. **No vector is returned** — the
52/// corpus stays on the node.
53#[derive(Clone, Debug, PartialEq)]
54pub struct Match {
55 pub id: String,
56 pub score: f32,
57}
58
59struct Entry {
60 id: String,
61 vector: Vec<f32>,
62}
63
64/// An on-node embedding index.
65pub struct VectorIndex {
66 dim: usize,
67 metric: Metric,
68 entries: Vec<Entry>,
69}
70
71impl VectorIndex {
72 /// A new `dim`-dimensional index ranked by `metric`.
73 pub fn new(dim: usize, metric: Metric) -> Self {
74 Self {
75 dim,
76 metric,
77 entries: Vec::new(),
78 }
79 }
80
81 pub fn dim(&self) -> usize {
82 self.dim
83 }
84
85 pub fn len(&self) -> usize {
86 self.entries.len()
87 }
88
89 pub fn is_empty(&self) -> bool {
90 self.entries.is_empty()
91 }
92
93 /// Insert (or replace) the embedding for `id`. Errors on a dimension mismatch.
94 pub fn insert(&mut self, id: impl Into<String>, vector: Vec<f32>) -> VectorResult<()> {
95 if vector.len() != self.dim {
96 return Err(VectorError::DimMismatch {
97 expected: self.dim,
98 got: vector.len(),
99 });
100 }
101 let id = id.into();
102 if let Some(existing) = self.entries.iter_mut().find(|e| e.id == id) {
103 existing.vector = vector;
104 } else {
105 self.entries.push(Entry { id, vector });
106 }
107 Ok(())
108 }
109
110 /// Remove `id`. Returns whether it was present.
111 pub fn remove(&mut self, id: &str) -> bool {
112 let before = self.entries.len();
113 self.entries.retain(|e| e.id != id);
114 self.entries.len() != before
115 }
116
117 /// Return the top-`k` entries nearest to `query`, highest score first. Ties
118 /// break by id for deterministic (corroboratable) results. Errors on a
119 /// dimension mismatch.
120 pub fn search(&self, query: &[f32], k: usize) -> VectorResult<Vec<Match>> {
121 if query.len() != self.dim {
122 return Err(VectorError::DimMismatch {
123 expected: self.dim,
124 got: query.len(),
125 });
126 }
127 let mut scored: Vec<Match> = self
128 .entries
129 .iter()
130 .map(|e| Match {
131 id: e.id.clone(),
132 score: self.metric.score(query, &e.vector),
133 })
134 .collect();
135 scored.sort_by(|a, b| {
136 b.score
137 .partial_cmp(&a.score)
138 .unwrap_or(Ordering::Equal)
139 .then_with(|| a.id.cmp(&b.id))
140 });
141 scored.truncate(k);
142 Ok(scored)
143 }
144}
145
146fn dot(a: &[f32], b: &[f32]) -> f32 {
147 a.iter().zip(b).map(|(x, y)| x * y).sum()
148}
149
150fn norm(a: &[f32]) -> f32 {
151 dot(a, a).sqrt()
152}
153
154fn l2(a: &[f32], b: &[f32]) -> f32 {
155 a.iter()
156 .zip(b)
157 .map(|(x, y)| {
158 let d = x - y;
159 d * d
160 })
161 .sum::<f32>()
162 .sqrt()
163}