Skip to main content

uqa_storage/vector_index/
retained.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Exact readers retain canonical vectors and their allowance independently of the live session.
8
9use std::sync::Arc;
10
11use uqa_core::{
12    memory::{Budgeted, BudgetedVec},
13    DocId, Payload, PostingEntry, PostingList,
14};
15
16use crate::read_control::StorageReadControl;
17use crate::vector_index::{
18    cosine_similarity_controlled, query::TopK, validate_vector_values, VectorIndex,
19};
20use crate::{StorageBackendError, StorageBackendResult};
21use sha2::{Digest, Sha256};
22
23mod builder;
24mod canonical;
25pub use builder::RetainedVectorIndexBuilder;
26
27pub(crate) type VectorEntries = Vec<(DocId, u32, Vec<f32>)>;
28
29/// An immutable exact index whose vector buffers and read workspace share the original retention allowance.
30#[derive(Clone)]
31pub struct RetainedVectorIndex {
32    entries: Arc<Budgeted<VectorEntries>>,
33    dimensions: u32,
34    index_kind: &'static str,
35    control: StorageReadControl,
36    fingerprint: [u8; 32],
37}
38
39impl RetainedVectorIndex {
40    pub(crate) fn from_entries(
41        entries: Budgeted<VectorEntries>,
42        dimensions: u32,
43        index_kind: &'static str,
44        control: &StorageReadControl,
45    ) -> StorageBackendResult<Self> {
46        control.check()?;
47        let mut digest = Sha256::new();
48        digest.update(b"uqa-retained-vector-values-v1\0");
49        digest.update(dimensions.to_le_bytes());
50        for (document, ordinal, vector) in entries.iter() {
51            control.check()?;
52            digest.update(document.to_le_bytes());
53            digest.update(ordinal.to_le_bytes());
54            digest.update((vector.len() as u64).to_le_bytes());
55            for chunk in vector.chunks(1024) {
56                control.check()?;
57                for value in chunk {
58                    digest.update(value.to_bits().to_le_bytes());
59                }
60            }
61        }
62        Ok(Self {
63            entries: entries.into_shared()?,
64            dimensions,
65            index_kind,
66            control: control.clone(),
67            fingerprint: digest.finalize().into(),
68        })
69    }
70
71    fn visit_scores(
72        &self,
73        query: &[f32],
74        mut visit: impl FnMut(DocId, f32) -> StorageBackendResult<()>,
75    ) -> StorageBackendResult<()> {
76        for vectors in self.entries.chunk_by(|a, b| a.0 == b.0) {
77            self.control.check()?;
78            let mut best =
79                cosine_similarity_controlled(query, &vectors[0].2, || self.control.check())?;
80            for (_, _, vector) in &vectors[1..] {
81                let score = cosine_similarity_controlled(query, vector, || self.control.check())?;
82                if score.total_cmp(&best).is_gt() {
83                    best = score;
84                }
85            }
86            visit(vectors[0].0, best)?;
87        }
88        self.control.check()
89    }
90
91    fn scores(
92        &self,
93        query: &[f32],
94        threshold: f32,
95    ) -> StorageBackendResult<BudgetedVec<(DocId, f32)>> {
96        let mut scores = BudgetedVec::new(self.control.memory());
97        self.visit_scores(query, |document, score| {
98            if score >= threshold {
99                scores.push((document, score))?;
100            }
101            Ok(())
102        })?;
103        Ok(scores)
104    }
105
106    fn postings(&self, scores: &[(DocId, f32)]) -> StorageBackendResult<PostingList> {
107        let mut postings = BudgetedVec::new(self.control.memory());
108        postings.reserve(scores.len())?;
109        for &(doc_id, score) in scores {
110            self.control.check()?;
111            postings.push(PostingEntry::new(
112                doc_id,
113                Payload::with_score(f64::from(score)),
114            ))?;
115        }
116        let (postings, _memory) = postings.into_parts();
117        Ok(PostingList::from_sorted_unchecked(postings))
118    }
119}
120
121impl VectorIndex for RetainedVectorIndex {
122    fn contains_document(&self, doc_id: DocId) -> StorageBackendResult<bool> {
123        self.control.check()?;
124        Ok(self
125            .entries
126            .binary_search_by_key(&doc_id, |entry| entry.0)
127            .is_ok())
128    }
129
130    fn dimensions(&self) -> u32 {
131        self.dimensions
132    }
133    fn index_kind(&self) -> &'static str {
134        self.index_kind
135    }
136    fn add(&mut self, _: DocId, _: Vec<f32>) -> StorageBackendResult<()> {
137        Err(read_only())
138    }
139    fn add_many(&mut self, _: DocId, _: Vec<Vec<f32>>) -> StorageBackendResult<()> {
140        Err(read_only())
141    }
142    fn delete(&mut self, _: DocId) -> StorageBackendResult<()> {
143        Err(read_only())
144    }
145    fn clear(&mut self) -> StorageBackendResult<()> {
146        Err(read_only())
147    }
148    fn initialize(&mut self) -> StorageBackendResult<()> {
149        Err(read_only())
150    }
151    fn search_knn(&self, query: &[f32], k: usize) -> StorageBackendResult<PostingList> {
152        self.control.check()?;
153        validate_vector_values(self.dimensions, query)?;
154        if k == 0 {
155            return Ok(PostingList::new());
156        }
157        let mut selected = TopK::new(k, &self.control);
158        self.visit_scores(query, |document, score| selected.offer_raw(document, score))?;
159        selected.finish(&self.control)
160    }
161    fn search_threshold(&self, query: &[f32], threshold: f32) -> StorageBackendResult<PostingList> {
162        self.control.check()?;
163        validate_vector_values(self.dimensions, query)?;
164        if !threshold.is_finite() {
165            return Err(StorageBackendError::Other(format!(
166                "vector similarity threshold must be finite, got {threshold}"
167            )));
168        }
169        let scores = self.scores(query, threshold)?;
170        self.postings(&scores)
171    }
172    fn count(&self) -> StorageBackendResult<usize> {
173        self.control.check()?;
174        Ok(self.entries.len())
175    }
176    fn snapshot(&self) -> StorageBackendResult<Arc<dyn VectorIndex>> {
177        Ok(Arc::new(self.clone()))
178    }
179
180    fn vector_read_snapshot(
181        &self,
182        control: &StorageReadControl,
183    ) -> StorageBackendResult<Option<super::VectorReadSnapshot>> {
184        self.control.check()?;
185        control.check()?;
186        Ok(Some(
187            Budgeted::new(self.clone(), self.control.memory().empty_reservation()).into_shared()?,
188        ))
189    }
190}
191
192fn read_only() -> StorageBackendError {
193    StorageBackendError::Other("cannot write a retained vector snapshot".into())
194}
195
196#[cfg(test)]
197mod tests;