uqa_storage/vector_index/
retained.rs1use 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#[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;