Skip to main content

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}