Skip to main content

uqa_storage/
vector_index.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Vector index abstraction and an in-memory brute-force fallback.
8//!
9//! Operators (`KNNOperator`, `VectorSimilarityOperator`,
10//! `QueryPoolVectorScoreOperator`) depend only on this trait. IVF and HNSW
11//! backends slot in by implementing the same surface.
12
13use std::sync::Arc;
14
15use uqa_core::{DocId, PostingList};
16
17use crate::{StorageBackendError, StorageBackendResult};
18
19mod canonical;
20mod collection;
21mod config;
22mod cosine;
23mod memory;
24mod memory_snapshot;
25mod memory_state;
26pub use memory::MemoryVectorIndex;
27pub mod query;
28pub use query::statistics::{DiskANNExecutionRoute, DiskANNExecutionStats, VectorQueryResult};
29pub(crate) mod retained;
30
31pub(crate) use canonical::{
32    canonical_vectors_equal, copy_vector, ordinal_count, selected_fingerprint,
33};
34pub use canonical::{decode_vector_bytes, SelectedVectorRead, VectorRead, VectorReadSnapshot};
35pub use collection::{
36    RetainedVectorIndexesBuilder, VectorIndexSource, VectorIndexes, VectorIndexesIter,
37};
38pub use config::{
39    DiskANNAlpha, DiskANNIndexParams, HNSWIndexParams, IVFIndexParams, VectorIndexOpenMode,
40    VectorIndexSpec,
41};
42pub use cosine::cosine_similarity;
43pub(crate) use cosine::cosine_similarity_controlled;
44pub use retained::{RetainedVectorIndex, RetainedVectorIndexBuilder};
45
46#[cfg(test)]
47mod physical_snapshots;
48
49pub fn validate_vector_values(dimensions: u32, vector: &[f32]) -> StorageBackendResult<()> {
50    validate_vector_values_controlled(dimensions, vector, None)
51}
52
53/// Validate canonical dimensions and finite coordinates with periodic cancellation checks.
54pub fn validate_vector_values_controlled(
55    dimensions: u32,
56    vector: &[f32],
57    control: Option<&crate::read_control::StorageReadControl>,
58) -> StorageBackendResult<()> {
59    if let Some(control) = control {
60        control.check()?;
61    }
62    let dimensions = usize::try_from(dimensions).map_err(|_| {
63        StorageBackendError::Other(format!(
64            "vector dimension {dimensions} exceeds the platform usize range"
65        ))
66    })?;
67    if vector.len() != dimensions {
68        return Err(StorageBackendError::Other(format!(
69            "vector dimension mismatch: expected {dimensions}, got {}",
70            vector.len()
71        )));
72    }
73    for (index, value) in vector.iter().copied().enumerate() {
74        if index.is_multiple_of(1024) {
75            if let Some(control) = control {
76                control.check()?;
77            }
78        }
79        if !value.is_finite() {
80            return Err(StorageBackendError::Other(format!(
81                "vector component {index} must be finite, got {value}"
82            )));
83        }
84    }
85    Ok(())
86}
87
88fn checked_vector_count(count: u128) -> StorageBackendResult<usize> {
89    usize::try_from(count).map_err(|_| StorageBackendError::Other("vector count overflow".into()))
90}
91
92pub(crate) fn validate_threshold(threshold: f32) -> StorageBackendResult<()> {
93    if threshold.is_finite() {
94        Ok(())
95    } else {
96        Err(StorageBackendError::Other(format!(
97            "vector similarity threshold must be finite, got {threshold}"
98        )))
99    }
100}
101
102pub fn select_top_k_scored(scored: &mut Vec<(DocId, f32)>, k: usize) {
103    if scored.len() > k {
104        scored.select_nth_unstable_by(k, |a, b| b.1.total_cmp(&a.1).then_with(|| a.0.cmp(&b.0)));
105        scored.truncate(k);
106    }
107}
108
109/// Collapse tensor-vector scores to the best score for each document without
110/// allocating one tree node per candidate. The final sort performed by each
111/// caller restores the posting-list invariant after top-k selection.
112pub(crate) fn deduplicate_scored_values(scored: &mut [(DocId, f32)]) -> usize {
113    if scored.len() < 2 {
114        return scored.len();
115    }
116    scored.sort_unstable_by_key(|(doc_id, _)| *doc_id);
117    let mut write = 1;
118    for read in 1..scored.len() {
119        let (doc_id, score) = scored[read];
120        if scored[write - 1].0 == doc_id {
121            scored[write - 1].1 = scored[write - 1].1.max(score);
122        } else {
123            scored[write] = (doc_id, score);
124            write += 1;
125        }
126    }
127    write
128}
129
130pub(crate) fn vector_norm(vector: &[f32]) -> f32 {
131    let mut squared_norm = 0.0_f32;
132    for value in vector {
133        squared_norm += value * value;
134    }
135    squared_norm.sqrt()
136}
137
138/// Cosine similarity when both vector norms were computed once outside the
139/// candidate loop. This preserves the raw-vector score while avoiding two
140/// norm reductions and two square roots for every candidate.
141pub(crate) fn cosine_similarity_with_norms(a: &[f32], b: &[f32], norm_a: f32, norm_b: f32) -> f32 {
142    if a.len() != b.len() || a.is_empty() || norm_a == 0.0 || norm_b == 0.0 {
143        return 0.0;
144    }
145    let mut dot = 0.0_f32;
146    for (x, y) in a.iter().zip(b) {
147        dot += x * y;
148    }
149    dot / (norm_a * norm_b)
150}
151
152pub trait VectorIndex: Send + Sync {
153    fn dimensions(&self) -> u32;
154    fn index_kind(&self) -> &'static str {
155        "vector"
156    }
157    /// The handle's declared physical method and parameters, without loading index state. This is not a generation or freshness check; providers without this metadata return `None`.
158    fn physical_configuration(&self) -> Option<VectorIndexSpec> {
159        None
160    }
161    /// Metadata from the actual selected physical/canonical view, without executing a logical vector query. Unsupported methods return None.
162    fn diskann_query_metadata(
163        &self,
164        control: &crate::read_control::StorageReadControl,
165    ) -> StorageBackendResult<Option<crate::diskann_index::DiskANNQueryMetadata>> {
166        control.check()?;
167        Ok(None)
168    }
169    fn add(&mut self, doc_id: DocId, vector: Vec<f32>) -> StorageBackendResult<()>;
170    fn add_many(&mut self, doc_id: DocId, vectors: Vec<Vec<f32>>) -> StorageBackendResult<()>;
171    fn delete(&mut self, doc_id: DocId) -> StorageBackendResult<()>;
172    fn clear(&mut self) -> StorageBackendResult<()>;
173    fn search_knn(&self, query: &[f32], k: usize) -> StorageBackendResult<PostingList>;
174    fn search_threshold(&self, query: &[f32], threshold: f32) -> StorageBackendResult<PostingList>;
175    /// Request a controlled search. The default checks cancellation and delegates to the provider's existing read boundary; in-memory physical algorithms override it to charge query workspace to the supplied allowance.
176    fn search_knn_with_control(
177        &self,
178        query: &[f32],
179        k: usize,
180        control: &crate::read_control::StorageReadControl,
181    ) -> StorageBackendResult<PostingList> {
182        control.check()?;
183        self.search_knn(query, k)
184    }
185    /// Controlled threshold search keeps the same result and caller-owned posting boundary as ordinary search.
186    fn search_threshold_with_control(
187        &self,
188        query: &[f32],
189        threshold: f32,
190        control: &crate::read_control::StorageReadControl,
191    ) -> StorageBackendResult<PostingList> {
192        control.check()?;
193        self.search_threshold(query, threshold)
194    }
195    /// Run one KNN invocation and retain its measured work when supported. An optional invoking control preserves the existing controlled-search boundary; absence preserves ordinary provider dispatch. Unsupported providers execute once and return no report.
196    fn search_knn_with_statistics(
197        &self,
198        query: &[f32],
199        k: usize,
200        control: Option<&crate::read_control::StorageReadControl>,
201    ) -> StorageBackendResult<VectorQueryResult> {
202        match control {
203            Some(control) => self.search_knn_with_control(query, k, control),
204            None => self.search_knn(query, k),
205        }
206        .map(VectorQueryResult::unmeasured)
207    }
208    /// Return exact threshold results and optional work from their one invocation. Report support must not introduce an additional scan or weaken the original provider's controls.
209    fn search_threshold_with_statistics(
210        &self,
211        query: &[f32],
212        threshold: f32,
213        control: Option<&crate::read_control::StorageReadControl>,
214    ) -> StorageBackendResult<VectorQueryResult> {
215        match control {
216            Some(control) => self.search_threshold_with_control(query, threshold, control),
217            None => self.search_threshold(query, threshold),
218        }
219        .map(VectorQueryResult::unmeasured)
220    }
221    fn count(&self) -> StorageBackendResult<usize>;
222
223    /// Test canonical membership at this handle's visibility boundary without searching or materializing the corpus. Empty tensor replacements have no membership. This is a maintenance probe, not a logical query observation.
224    fn contains_document(&self, _doc_id: DocId) -> StorageBackendResult<bool> {
225        Err(StorageBackendError::Other(
226            "canonical vector membership is not supported by this backend".into(),
227        ))
228    }
229
230    /// Build any auxiliary physical metadata required by this index from its
231    /// current vector contents. Brute-force indexes need no extra work;
232    /// persistent IVF and HNSW implementations use this during explicit
233    /// index creation, while restore paths deliberately skip it.
234    fn initialize(&mut self) -> StorageBackendResult<()> {
235        Ok(())
236    }
237
238    /// Read-only handle suitable for an `ExecutionContext`.
239    fn snapshot(&self) -> StorageBackendResult<Arc<dyn VectorIndex>>;
240
241    /// Capture using the caller's retention allowance and cancellation. Owners that copy index data override this method to reserve construction before allocation. The default preserves the provider's existing snapshot and its independently retained control.
242    fn snapshot_with_control(
243        &self,
244        control: &crate::read_control::StorageReadControl,
245    ) -> StorageBackendResult<Arc<dyn VectorIndex>> {
246        control.check()?;
247        self.snapshot()
248    }
249
250    /// Borrow an opaque retained `DiskANN` canonical source for evaluated document replacements. Capturing metadata does not execute or observe a vector query; other physical methods leave this capability absent.
251    fn diskann_read_snapshot(
252        &self,
253        control: &crate::read_control::StorageReadControl,
254    ) -> StorageBackendResult<Option<crate::diskann_index::DiskANNReadSnapshot>> {
255        control.check()?;
256        Ok(None)
257    }
258
259    /// Retain the actual canonical values independently of physical mutation provenance. Capturing this source is metadata access, not a logical vector query.
260    fn vector_read_snapshot(
261        &self,
262        control: &crate::read_control::StorageReadControl,
263    ) -> StorageBackendResult<Option<VectorReadSnapshot>> {
264        self.diskann_read_snapshot(control)?
265            .map(|source| {
266                uqa_core::memory::Budgeted::new(source, control.memory().empty_reservation())
267                    .into_shared()
268                    .map(|source| source as VectorReadSnapshot)
269                    .map_err(Into::into)
270            })
271            .transpose()
272    }
273
274    /// Check whether a SQL replacement can retain this document's canonical vectors. Unsupported providers return false and keep the normal replacement path. Live memory indexes override this to borrow their canonical data without cloning the entire index.
275    fn matches_document_vectors(
276        &self,
277        document: DocId,
278        vectors: &[Vec<f32>],
279        control: &crate::read_control::StorageReadControl,
280    ) -> StorageBackendResult<bool> {
281        self.vector_read_snapshot(control)?
282            .map_or(Ok(false), |source| {
283                canonical_vectors_equal(source.as_ref(), document, vectors, control)
284            })
285    }
286
287    /// Keep this selected physical `DiskANN` generation while reading a different fixed canonical field view. The query owner verifies raw coverage without inventing mutation origins.
288    fn snapshot_with_vector_read(
289        &self,
290        _source: VectorReadSnapshot,
291        control: &crate::read_control::StorageReadControl,
292    ) -> StorageBackendResult<Option<Arc<dyn VectorIndex>>> {
293        control.check()?;
294        Ok(None)
295    }
296
297    /// Retain this physical `DiskANN` generation with the selected actual canonical replacements. Wrappers preserve their original read observation and retention boundary on the returned index. Unsupported methods return None without changing physical selection.
298    fn snapshot_with_diskann_changes(
299        &self,
300        _changes: &crate::diskann_index::DiskANNReadChanges,
301        control: &crate::read_control::StorageReadControl,
302    ) -> StorageBackendResult<Option<Arc<dyn VectorIndex>>> {
303        control.check()?;
304        Ok(None)
305    }
306
307    /// Independent writable copy used by in-memory engine rollback. The
308    /// default keeps third-party and persistent implementations source
309    /// compatible; only indexes hosted by a memory engine need to support it.
310    fn writable_snapshot(&self) -> StorageBackendResult<Box<dyn VectorIndex>> {
311        Err(StorageBackendError::Other(
312            "writable vector-index snapshots are not supported by this backend".into(),
313        ))
314    }
315}
316
317#[cfg(test)]
318mod tests {
319    use super::*;
320
321    #[test]
322    fn canonical_membership_tracks_tensor_replacement_and_retained_snapshots() {
323        let indexes: [Box<dyn VectorIndex>; 3] = [
324            Box::new(MemoryVectorIndex::new(2)),
325            Box::new(crate::IVFIndex::new(2)),
326            Box::new(crate::HNSWIndex::new(2)),
327        ];
328        for mut index in indexes {
329            assert!(!index.contains_document(1).unwrap());
330            index
331                .add_many(1, vec![vec![1.0, 0.0], vec![0.0, 1.0]])
332                .unwrap();
333            let retained = index.snapshot().unwrap();
334            assert!(index.contains_document(1).unwrap());
335            assert!(!index.contains_document(2).unwrap());
336            index.add_many(1, Vec::new()).unwrap();
337            assert!(!index.contains_document(1).unwrap());
338            assert!(retained.contains_document(1).unwrap());
339            index.add(1, vec![0.5, 0.5]).unwrap();
340            index.delete(1).unwrap();
341            assert!(!index.contains_document(1).unwrap());
342        }
343    }
344
345    fn approx_eq(a: f32, b: f32, eps: f32) {
346        assert!((a - b).abs() < eps, "expected {a} ~ {b} within {eps}");
347    }
348
349    #[test]
350    fn cosine_identity_is_one() {
351        let v = vec![1.0, 2.0, 3.0];
352        approx_eq(cosine_similarity(&v, &v), 1.0, 1e-6);
353    }
354
355    #[test]
356    fn vector_count_overflow_is_reported() {
357        let error = checked_vector_count(usize::MAX as u128 + 1).unwrap_err();
358        assert!(error.to_string().contains("vector count overflow"));
359    }
360
361    #[test]
362    fn cosine_orthogonal_is_zero() {
363        let a = vec![1.0, 0.0];
364        let b = vec![0.0, 1.0];
365        approx_eq(cosine_similarity(&a, &b), 0.0, 1e-6);
366    }
367
368    #[test]
369    fn cosine_zero_norm_is_zero() {
370        let a = vec![0.0, 0.0];
371        let b = vec![1.0, 1.0];
372        approx_eq(cosine_similarity(&a, &b), 0.0, 1e-6);
373    }
374
375    #[test]
376    fn knn_orders_by_similarity_descending_then_doc_id() {
377        let mut idx = MemoryVectorIndex::new(2);
378        idx.add(1, vec![1.0, 0.0]).unwrap();
379        idx.add(2, vec![0.5, 0.5]).unwrap();
380        idx.add(3, vec![0.0, 1.0]).unwrap();
381        let pl = idx.search_knn(&[1.0, 0.0], 2).unwrap();
382        let docs: Vec<_> = pl.iter().map(|e| e.doc_id).collect();
383        // posting list is doc_id-sorted but the top-2 should be {1, 2}.
384        assert_eq!(docs, vec![1, 2]);
385        let entry1 = pl.get_entry(1).unwrap();
386        let entry2 = pl.get_entry(2).unwrap();
387        assert!(entry1.payload.score > entry2.payload.score);
388    }
389
390    #[test]
391    fn partial_top_k_keeps_deterministic_doc_id_ties() {
392        let mut scored = vec![(10, 0.5), (3, 0.9), (1, 0.9), (8, 0.7), (2, 0.1)];
393        select_top_k_scored(&mut scored, 2);
394        scored.sort_by_key(|(doc_id, _)| *doc_id);
395        assert_eq!(scored, vec![(1, 0.9), (3, 0.9)]);
396    }
397
398    #[test]
399    fn precomputed_norm_cosine_matches_reference_bits() {
400        let a = [0.25, -3.0, 1.5, 8.0];
401        let b = [2.0, 0.75, -4.0, 0.5];
402        let expected = cosine_similarity(&a, &b);
403        let actual = cosine_similarity_with_norms(&a, &b, vector_norm(&a), vector_norm(&b));
404        assert_eq!(actual.to_bits(), expected.to_bits());
405    }
406
407    #[test]
408    fn score_deduplication_keeps_best_tensor_vector() {
409        let mut scored = vec![(7, 0.3), (2, 0.8), (7, 0.9), (2, 0.4), (9, -0.2)];
410        let count = deduplicate_scored_values(&mut scored);
411        scored.truncate(count);
412        assert_eq!(scored, vec![(2, 0.8), (7, 0.9), (9, -0.2)]);
413    }
414
415    #[test]
416    fn threshold_filters_below_cutoff() {
417        let mut idx = MemoryVectorIndex::new(2);
418        idx.add(1, vec![1.0, 0.0]).unwrap();
419        idx.add(2, vec![0.5, 0.5]).unwrap();
420        idx.add(3, vec![0.0, 1.0]).unwrap();
421        let pl = idx.search_threshold(&[1.0, 0.0], 0.5).unwrap();
422        let docs: Vec<_> = pl.iter().map(|e| e.doc_id).collect();
423        assert_eq!(docs, vec![1, 2]);
424    }
425
426    #[test]
427    fn delete_removes_vector() {
428        let mut idx = MemoryVectorIndex::new(2);
429        idx.add(1, vec![1.0, 0.0]).unwrap();
430        idx.delete(1).unwrap();
431        assert_eq!(idx.count().unwrap(), 0);
432    }
433
434    #[test]
435    fn non_finite_vectors_queries_and_thresholds_are_errors() {
436        let mut idx = MemoryVectorIndex::new(2);
437        assert!(idx.add(1, vec![f32::NAN, 0.0]).is_err());
438        idx.add(1, vec![1.0, 0.0]).unwrap();
439        assert!(idx.search_knn(&[f32::INFINITY, 0.0], 1).is_err());
440        assert!(idx
441            .search_threshold(&[1.0, 0.0], f32::NEG_INFINITY)
442            .is_err());
443    }
444}