Skip to main content

uqa_storage_sqlite/vector_index/
brute_force.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Persistent brute-force vector index and exact search contract.
8
9use parking_lot::RwLock;
10use uqa_core::memory::BudgetedVec;
11use uqa_storage::read_control::StorageReadControl;
12
13mod cache;
14
15use super::native::NativeVectorRead;
16use super::{
17    blob_to_vector, cosine_similarity, decode_doc_id, encode_doc_id, i64_to_usize, params,
18    select_top_k_scored, usize_to_u64, validate_persisted_ordinal_sequence,
19    validate_vector_ordinal_count, validate_vector_values, vector_to_blob, Arc, DocId,
20    EncodedDocVectors, ManagedConnection, Payload, PostingEntry, PostingList, SQLiteError,
21    SQLiteResult, StorageBackendResult, VectorIndex,
22};
23
24#[derive(Clone)]
25pub struct SQLiteVectorIndex {
26    pub(super) conn: ManagedConnection,
27    pub(super) table: String,
28    pub(super) field: String,
29    pub(super) dimensions: u32,
30    pub(super) retained: Option<Arc<crate::mvcc::native::NativeSnapshot>>,
31    cached_vectors: Arc<RwLock<Option<cache::CachedVectors>>>,
32}
33
34impl SQLiteVectorIndex {
35    pub fn new(
36        conn: ManagedConnection,
37        table: impl Into<String>,
38        field: impl Into<String>,
39        dimensions: u32,
40    ) -> Self {
41        Self {
42            conn,
43            table: table.into(),
44            field: field.into(),
45            dimensions,
46            retained: None,
47            cached_vectors: Arc::default(),
48        }
49    }
50
51    fn score_vectors(
52        &self,
53        query: &[f32],
54        threshold: Option<f32>,
55    ) -> SQLiteResult<Option<BudgetedVec<(DocId, f32)>>> {
56        if let Some(snapshot) = self.read_releasing_cache(|| self.native_snapshot())? {
57            let native = self.read_releasing_cache(|| NativeVectorRead::new(&snapshot, self))?;
58            self.score_cached_vectors(&native, query, threshold)
59        } else {
60            let control = StorageReadControl::with_limit(usize::MAX);
61            Self::score_stream(query, threshold, |visit| {
62                for (id, _, vector) in self.load_all_with_ordinals()? {
63                    visit(id, &vector, &control)?;
64                }
65                Ok(())
66            })
67        }
68    }
69
70    fn score_stream(
71        query: &[f32],
72        threshold: Option<f32>,
73        read: impl FnOnce(
74            &mut dyn FnMut(DocId, &[f32], &StorageReadControl) -> SQLiteResult<()>,
75        ) -> SQLiteResult<()>,
76    ) -> SQLiteResult<Option<BudgetedVec<(DocId, f32)>>> {
77        let mut scores: Option<BudgetedVec<(DocId, f32)>> = None;
78        read(&mut |doc_id, vector, control| {
79            let score = cosine_similarity(query, vector);
80            if threshold.is_none_or(|threshold| score >= threshold) {
81                let scores = scores.get_or_insert_with(|| BudgetedVec::new(control.memory()));
82                // Canonical and legacy cursors both order vectors by document and tensor ordinal.
83                if let Some((last_id, best)) = scores.last_mut().filter(|(id, _)| *id == doc_id) {
84                    debug_assert_eq!(*last_id, doc_id);
85                    if score > *best {
86                        *best = score;
87                    }
88                } else {
89                    scores.push((doc_id, score))?;
90                }
91            }
92            Ok(())
93        })?;
94        Ok(scores)
95    }
96
97    fn score_postings(
98        &self,
99        scores: Vec<(DocId, f32)>,
100        memory: &uqa_core::memory::MemoryBudget,
101    ) -> SQLiteResult<PostingList> {
102        let mut entries = BudgetedVec::new(memory);
103        self.read_releasing_cache(|| Ok(entries.reserve(scores.len())?))?;
104        for (doc_id, score) in scores {
105            entries.push(PostingEntry::new(
106                doc_id,
107                Payload::with_score(f64::from(score)),
108            ))?;
109        }
110        let (entries, _entry_memory) = entries.into_parts();
111        Ok(PostingList::from_sorted_unchecked(entries))
112    }
113
114    pub(super) fn load_all_with_ordinals(&self) -> SQLiteResult<Vec<(DocId, u32, Vec<f32>)>> {
115        self.conn
116            .with(|connection| self.load_all_with_ordinals_from(connection))
117    }
118
119    pub(super) fn load_all_with_ordinals_from(
120        &self,
121        connection: &rusqlite::Connection,
122    ) -> SQLiteResult<Vec<(DocId, u32, Vec<f32>)>> {
123        let mut stmt = connection.prepare(
124            "SELECT doc_id, vector_ordinal, vector FROM _vectors
125                 WHERE table_name = ?1 AND field = ?2
126                 ORDER BY doc_id, vector_ordinal",
127        )?;
128        let rows = stmt.query_map(params![self.table, self.field], |r| {
129            Ok((
130                r.get::<_, i64>(0)?,
131                r.get::<_, i64>(1)?,
132                r.get::<_, Vec<u8>>(2)?,
133            ))
134        })?;
135        let mut out = Vec::new();
136        for row in rows {
137            let (doc_id, ordinal, blob) = row?;
138            let ordinal = u32::try_from(ordinal).map_err(|_| {
139                SQLiteError::StorageBackend(format!(
140                    "invalid vector ordinal {ordinal} for {}.{}",
141                    self.table, self.field
142                ))
143            })?;
144            let vector = blob_to_vector(&blob)?;
145            self.validate_dimensions_sqlite(&vector)?;
146            out.push((decode_doc_id(doc_id)?, ordinal, vector));
147        }
148        validate_persisted_ordinal_sequence(&out)?;
149        Ok(out)
150    }
151
152    pub(super) fn validate_dimensions_sqlite(&self, vector: &[f32]) -> SQLiteResult<()> {
153        validate_vector_values(self.dimensions, vector).map_err(|error| {
154            SQLiteError::StorageBackend(format!(
155                "invalid vector for {}.{}: {error}",
156                self.table, self.field
157            ))
158        })
159    }
160
161    pub(super) fn validate_dimensions(&self, vector: &[f32]) -> StorageBackendResult<()> {
162        Ok(self.validate_dimensions_sqlite(vector)?)
163    }
164
165    pub(super) fn stage_doc_vectors(
166        &self,
167        doc_id: DocId,
168        vectors: &[Vec<f32>],
169    ) -> SQLiteResult<EncodedDocVectors> {
170        for vector in vectors {
171            self.validate_dimensions_sqlite(vector)?;
172        }
173        validate_vector_ordinal_count(usize_to_u64("vector count", vectors.len())?)?;
174        let doc_id = encode_doc_id(doc_id)?;
175        let encoded = vectors
176            .iter()
177            .enumerate()
178            .map(|(ordinal, vector)| {
179                let ordinal = u32::try_from(ordinal).map_err(|_| {
180                    SQLiteError::StorageBackend(
181                        "vector ordinal exceeds the u32 index format".into(),
182                    )
183                })?;
184                Ok((i64::from(ordinal), vector_to_blob(vector)?))
185            })
186            .collect::<SQLiteResult<Vec<_>>>()?;
187        Ok((doc_id, encoded))
188    }
189}
190
191impl VectorIndex for SQLiteVectorIndex {
192    fn contains_document(&self, doc_id: DocId) -> StorageBackendResult<bool> {
193        let doc_id = encode_doc_id(doc_id)?;
194        if let Some(found) = self.read_native(|read| read.contains_document(doc_id))? {
195            return Ok(found);
196        }
197        Ok(self.conn.with(|connection| {
198            Ok(connection.query_row(
199                "SELECT EXISTS(SELECT 1 FROM _vectors WHERE table_name = ?1 AND field = ?2 AND doc_id = ?3 AND vector_ordinal = 0)",
200                params![self.table, self.field, doc_id],
201                |row| row.get(0),
202            )?)
203        })?)
204    }
205
206    fn dimensions(&self) -> u32 {
207        self.dimensions
208    }
209
210    fn index_kind(&self) -> &'static str {
211        "sqlite-bruteforce"
212    }
213
214    fn add(&mut self, doc_id: DocId, vector: Vec<f32>) -> StorageBackendResult<()> {
215        self.add_many(doc_id, vec![vector])
216    }
217
218    fn add_many(&mut self, doc_id: DocId, vectors: Vec<Vec<f32>>) -> StorageBackendResult<()> {
219        let (doc_id, encoded_vectors) = self.stage_doc_vectors(doc_id, &vectors)?;
220        if self
221            .write_native(|read, batch| read.replace(batch, doc_id, &encoded_vectors))?
222            .is_some()
223        {
224            return Ok(());
225        }
226        self.conn.with_mut(|conn| {
227            let tx = conn.savepoint()?;
228            tx.execute(
229                "DELETE FROM _vectors
230                 WHERE table_name = ?1 AND field = ?2 AND doc_id = ?3",
231                params![self.table, self.field, doc_id],
232            )?;
233            let mut stmt = tx.prepare(
234                "INSERT INTO _vectors (table_name, field, doc_id, vector_ordinal, vector)
235                 VALUES (?1, ?2, ?3, ?4, ?5)",
236            )?;
237            for (ordinal, vector) in &encoded_vectors {
238                stmt.execute(params![self.table, self.field, doc_id, ordinal, vector,])?;
239            }
240            drop(stmt);
241            tx.commit()?;
242            Ok(())
243        })?;
244        Ok(())
245    }
246
247    fn delete(&mut self, doc_id: DocId) -> StorageBackendResult<()> {
248        let doc_id = encode_doc_id(doc_id)?;
249        if self
250            .write_native(|read, batch| read.delete(batch, doc_id))?
251            .is_some()
252        {
253            return Ok(());
254        }
255        self.conn.with(|c| {
256            c.execute(
257                "DELETE FROM _vectors
258                 WHERE table_name = ?1 AND field = ?2 AND doc_id = ?3",
259                params![self.table, self.field, doc_id],
260            )?;
261            Ok(())
262        })?;
263        Ok(())
264    }
265
266    fn clear(&mut self) -> StorageBackendResult<()> {
267        if self
268            .write_native(|read, batch| {
269                read.clear_family(batch, crate::mvcc::native::NativeRecordFamily::Vectors)
270            })?
271            .is_some()
272        {
273            return Ok(());
274        }
275        self.conn.with(|c| {
276            c.execute(
277                "DELETE FROM _vectors WHERE table_name = ?1 AND field = ?2",
278                params![self.table, self.field],
279            )?;
280            Ok(())
281        })?;
282        Ok(())
283    }
284
285    fn search_knn(&self, query: &[f32], k: usize) -> StorageBackendResult<PostingList> {
286        self.validate_dimensions(query)?;
287        if k == 0 {
288            return Ok(PostingList::new());
289        }
290        let Some(scores) = self.score_vectors(query, None)? else {
291            return Ok(PostingList::new());
292        };
293        let (mut scores, score_memory) = scores.into_parts();
294        select_top_k_scored(&mut scores, k);
295        scores.sort_by_key(|(id, _)| *id);
296        Ok(self.score_postings(scores, score_memory.budget())?)
297    }
298
299    fn search_threshold(&self, query: &[f32], threshold: f32) -> StorageBackendResult<PostingList> {
300        self.validate_dimensions(query)?;
301        if !threshold.is_finite() {
302            return Err(uqa_storage::StorageBackendError::Other(format!(
303                "vector similarity threshold must be finite, got {threshold}"
304            )));
305        }
306        let Some(scores) = self.score_vectors(query, Some(threshold))? else {
307            return Ok(PostingList::new());
308        };
309        let (mut scores, score_memory) = scores.into_parts();
310        scores.sort_by_key(|(id, _)| *id);
311        Ok(self.score_postings(scores, score_memory.budget())?)
312    }
313
314    fn count(&self) -> StorageBackendResult<usize> {
315        if let Some(snapshot) = self.native_snapshot()? {
316            return Ok(NativeVectorRead::new(&snapshot, self)?.count()?);
317        }
318        Ok(self.conn.with(|c| {
319            let n: i64 = c.query_row(
320                "SELECT COUNT(*) FROM _vectors WHERE table_name = ?1 AND field = ?2",
321                params![self.table, self.field],
322                |r| r.get(0),
323            )?;
324            i64_to_usize("vector count", n)
325        })?)
326    }
327
328    fn snapshot(&self) -> StorageBackendResult<Arc<dyn VectorIndex>> {
329        Ok(Arc::new(self.retained_snapshot()?))
330    }
331    fn vector_read_snapshot(
332        &self,
333        control: &uqa_storage::read_control::StorageReadControl,
334    ) -> StorageBackendResult<Option<uqa_storage::vector_index::VectorReadSnapshot>> {
335        super::native::canonical::capture(self, control)
336    }
337}
338
339#[cfg(test)]
340mod tests;