1use 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
53pub 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
109pub(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
138pub(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 fn physical_configuration(&self) -> Option<VectorIndexSpec> {
159 None
160 }
161 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 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 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 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 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 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 fn initialize(&mut self) -> StorageBackendResult<()> {
235 Ok(())
236 }
237
238 fn snapshot(&self) -> StorageBackendResult<Arc<dyn VectorIndex>>;
240
241 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 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 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 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 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 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 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 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}