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;
19use std::collections::HashMap;
20
21use crate::error::{VectorError, VectorResult};
22
23/// How similarity is measured. `search` always returns the highest-scoring
24/// entries, so every metric is oriented "higher = more similar".
25#[derive(Clone, Copy, Debug, PartialEq, Eq)]
26pub enum Metric {
27 /// Cosine similarity in `[-1, 1]` (1 = identical direction). Magnitude-invariant.
28 Cosine,
29 /// Raw dot product (higher = more aligned and larger).
30 Dot,
31 /// Negative Euclidean distance (0 = identical, more negative = farther).
32 Euclidean,
33}
34
35impl Metric {
36 /// Score `entry` against query `a`, whose norm is `na`. Norms only feed
37 /// Cosine: the query's is taken once per search and each entry's once at
38 /// insert, rather than both on every comparison — the same arithmetic in
39 /// the same order, so the same bits.
40 fn score(&self, a: &[f32], na: f32, entry: &Entry) -> f32 {
41 let b = &entry.vector;
42 match self {
43 Metric::Cosine => {
44 let nb = entry.norm;
45 if na == 0.0 || nb == 0.0 {
46 0.0
47 } else {
48 dot(a, b) / (na * nb)
49 }
50 }
51 Metric::Dot => dot(a, b),
52 Metric::Euclidean => -l2(a, b),
53 }
54 }
55
56 /// The norm a vector carries for this metric (only Cosine reads it).
57 fn norm_of(&self, v: &[f32]) -> f32 {
58 match self {
59 Metric::Cosine => norm(v),
60 Metric::Dot | Metric::Euclidean => 0.0,
61 }
62 }
63}
64
65/// A search hit: which entry, and how similar. **No vector is returned** — the
66/// corpus stays on the node.
67#[derive(Clone, Debug, PartialEq)]
68pub struct Match {
69 pub id: String,
70 pub score: f32,
71}
72
73struct Entry {
74 id: String,
75 vector: Vec<f32>,
76 /// `Metric::norm_of(vector)` for the index's metric.
77 norm: f32,
78}
79
80/// An on-node embedding index.
81pub struct VectorIndex {
82 dim: usize,
83 metric: Metric,
84 entries: Vec<Entry>,
85 /// Where each id sits in `entries`, so an insert finds an existing id
86 /// without comparing it against every stored id (a bulk load was O(n^2)).
87 positions: HashMap<String, usize>,
88}
89
90impl VectorIndex {
91 /// A new `dim`-dimensional index ranked by `metric`.
92 pub fn new(dim: usize, metric: Metric) -> Self {
93 Self {
94 dim,
95 metric,
96 entries: Vec::new(),
97 positions: HashMap::new(),
98 }
99 }
100
101 pub fn dim(&self) -> usize {
102 self.dim
103 }
104
105 pub fn len(&self) -> usize {
106 self.entries.len()
107 }
108
109 pub fn is_empty(&self) -> bool {
110 self.entries.is_empty()
111 }
112
113 /// Insert (or replace) the embedding for `id`. Errors on a dimension mismatch.
114 pub fn insert(&mut self, id: impl Into<String>, vector: Vec<f32>) -> VectorResult<()> {
115 if vector.len() != self.dim {
116 return Err(VectorError::DimMismatch {
117 expected: self.dim,
118 got: vector.len(),
119 });
120 }
121 let id = id.into();
122 let norm = self.metric.norm_of(&vector);
123 if let Some(&at) = self.positions.get(&id) {
124 let existing = &mut self.entries[at];
125 existing.vector = vector;
126 existing.norm = norm;
127 } else {
128 self.positions.insert(id.clone(), self.entries.len());
129 self.entries.push(Entry { id, vector, norm });
130 }
131 Ok(())
132 }
133
134 /// Remove `id`. Returns whether it was present.
135 pub fn remove(&mut self, id: &str) -> bool {
136 let Some(at) = self.positions.remove(id) else {
137 return false;
138 };
139 // Order-preserving, as `retain` was; every later entry moves down one.
140 self.entries.remove(at);
141 for entry in &self.entries[at..] {
142 if let Some(p) = self.positions.get_mut(&entry.id) {
143 *p -= 1;
144 }
145 }
146 true
147 }
148
149 /// Return the top-`k` entries nearest to `query`, highest score first. Ties
150 /// break by id for deterministic (corroboratable) results. Errors on a
151 /// dimension mismatch.
152 pub fn search(&self, query: &[f32], k: usize) -> VectorResult<Vec<Match>> {
153 if query.len() != self.dim {
154 return Err(VectorError::DimMismatch {
155 expected: self.dim,
156 got: query.len(),
157 });
158 }
159 let query_norm = self.metric.norm_of(query);
160 // Rank (score, position) pairs; an id is cloned only for the k returned.
161 let mut scored: Vec<(f32, usize)> = self
162 .entries
163 .iter()
164 .enumerate()
165 .map(|(at, e)| (self.metric.score(query, query_norm, e), at))
166 .collect();
167 let rank = |a: &(f32, usize), b: &(f32, usize)| {
168 b.0.partial_cmp(&a.0)
169 .unwrap_or(Ordering::Equal)
170 .then_with(|| self.entries[a.1].id.cmp(&self.entries[b.1].id))
171 };
172 // Ids are unique, so without NaN `rank` is a strict total order and
173 // selecting the top k then sorting only those gives exactly the full
174 // sort's first k. A NaN score breaks that order; keep the full sort then.
175 if k < scored.len() && !scored.iter().any(|(s, _)| s.is_nan()) {
176 if k > 0 {
177 scored.select_nth_unstable_by(k - 1, rank);
178 }
179 scored.truncate(k);
180 }
181 scored.sort_by(rank);
182 scored.truncate(k);
183 Ok(scored
184 .into_iter()
185 .map(|(score, at)| Match {
186 id: self.entries[at].id.clone(),
187 score,
188 })
189 .collect())
190 }
191}
192
193fn dot(a: &[f32], b: &[f32]) -> f32 {
194 a.iter().zip(b).map(|(x, y)| x * y).sum()
195}
196
197fn norm(a: &[f32]) -> f32 {
198 dot(a, a).sqrt()
199}
200
201fn l2(a: &[f32], b: &[f32]) -> f32 {
202 a.iter()
203 .zip(b)
204 .map(|(x, y)| {
205 let d = x - y;
206 d * d
207 })
208 .sum::<f32>()
209 .sqrt()
210}