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 visit_ordered_vectors_from(
120        &self,
121        connection: &rusqlite::Connection,
122        control: &StorageReadControl,
123        mut visit: impl FnMut(DocId, u32, &[f32]) -> SQLiteResult<()>,
124    ) -> SQLiteResult<()> {
125        control.check()?;
126        let mut statement = connection.prepare(
127            "SELECT doc_id, vector_ordinal, vector FROM _vectors
128             WHERE table_name = ?1 AND field = ?2 ORDER BY doc_id, vector_ordinal",
129        )?;
130        let mut rows = statement.query(params![self.table, self.field])?;
131        let mut ordinals = super::codec::PersistedOrdinalSequence::default();
132        while let Some(row) = rows.next()? {
133            control.check()?;
134            let document = decode_doc_id(row.get(0)?)?;
135            let ordinal: i64 = row.get(1)?;
136            let ordinal = u32::try_from(ordinal).map_err(|_| {
137                SQLiteError::StorageBackend(format!(
138                    "invalid vector ordinal {ordinal} for {}.{}",
139                    self.table, self.field
140                ))
141            })?;
142            let bytes = row
143                .get_ref(2)?
144                .as_blob()
145                .map_err(|_| SQLiteError::StorageBackend("invalid vector payload".into()))?;
146            let mut payload = control.memory().reserve(bytes.len())?;
147            let vector = blob_to_vector(bytes)?;
148            let capacity = vector
149                .capacity()
150                .checked_mul(size_of::<f32>())
151                .ok_or(uqa_core::memory::MemoryError::SizeOverflow)?;
152            payload.grow(capacity.saturating_sub(bytes.len()))?;
153            self.validate_dimensions_sqlite(&vector)?;
154            ordinals.push(document, ordinal)?;
155            visit(document, ordinal, &vector)?;
156        }
157        Ok(())
158    }
159
160    pub(super) fn load_all_with_ordinals_from(
161        &self,
162        connection: &rusqlite::Connection,
163    ) -> SQLiteResult<Vec<(DocId, u32, Vec<f32>)>> {
164        let mut stmt = connection.prepare(
165            "SELECT doc_id, vector_ordinal, vector FROM _vectors
166                 WHERE table_name = ?1 AND field = ?2
167                 ORDER BY doc_id, vector_ordinal",
168        )?;
169        let rows = stmt.query_map(params![self.table, self.field], |r| {
170            Ok((
171                r.get::<_, i64>(0)?,
172                r.get::<_, i64>(1)?,
173                r.get::<_, Vec<u8>>(2)?,
174            ))
175        })?;
176        let mut out = Vec::new();
177        for row in rows {
178            let (doc_id, ordinal, blob) = row?;
179            let ordinal = u32::try_from(ordinal).map_err(|_| {
180                SQLiteError::StorageBackend(format!(
181                    "invalid vector ordinal {ordinal} for {}.{}",
182                    self.table, self.field
183                ))
184            })?;
185            let vector = blob_to_vector(&blob)?;
186            self.validate_dimensions_sqlite(&vector)?;
187            out.push((decode_doc_id(doc_id)?, ordinal, vector));
188        }
189        validate_persisted_ordinal_sequence(&out)?;
190        Ok(out)
191    }
192
193    pub(super) fn validate_dimensions_sqlite(&self, vector: &[f32]) -> SQLiteResult<()> {
194        validate_vector_values(self.dimensions, vector).map_err(|error| {
195            SQLiteError::StorageBackend(format!(
196                "invalid vector for {}.{}: {error}",
197                self.table, self.field
198            ))
199        })
200    }
201
202    pub(super) fn validate_dimensions(&self, vector: &[f32]) -> StorageBackendResult<()> {
203        Ok(self.validate_dimensions_sqlite(vector)?)
204    }
205
206    pub(super) fn stage_doc_vectors(
207        &self,
208        doc_id: DocId,
209        vectors: &[Vec<f32>],
210    ) -> SQLiteResult<EncodedDocVectors> {
211        for vector in vectors {
212            self.validate_dimensions_sqlite(vector)?;
213        }
214        validate_vector_ordinal_count(usize_to_u64("vector count", vectors.len())?)?;
215        let doc_id = encode_doc_id(doc_id)?;
216        let encoded = vectors
217            .iter()
218            .enumerate()
219            .map(|(ordinal, vector)| {
220                let ordinal = u32::try_from(ordinal).map_err(|_| {
221                    SQLiteError::StorageBackend(
222                        "vector ordinal exceeds the u32 index format".into(),
223                    )
224                })?;
225                Ok((i64::from(ordinal), vector_to_blob(vector)?))
226            })
227            .collect::<SQLiteResult<Vec<_>>>()?;
228        Ok((doc_id, encoded))
229    }
230}
231
232impl VectorIndex for SQLiteVectorIndex {
233    fn contains_document(&self, doc_id: DocId) -> StorageBackendResult<bool> {
234        let doc_id = encode_doc_id(doc_id)?;
235        if let Some(found) = self.read_native(|read| read.contains_document(doc_id))? {
236            return Ok(found);
237        }
238        Ok(self.conn.with(|connection| {
239            Ok(connection.query_row(
240                "SELECT EXISTS(SELECT 1 FROM _vectors WHERE table_name = ?1 AND field = ?2 AND doc_id = ?3 AND vector_ordinal = 0)",
241                params![self.table, self.field, doc_id],
242                |row| row.get(0),
243            )?)
244        })?)
245    }
246
247    fn dimensions(&self) -> u32 {
248        self.dimensions
249    }
250
251    fn index_kind(&self) -> &'static str {
252        "sqlite-bruteforce"
253    }
254
255    fn add(&mut self, doc_id: DocId, vector: Vec<f32>) -> StorageBackendResult<()> {
256        self.add_many(doc_id, vec![vector])
257    }
258
259    fn add_many(&mut self, doc_id: DocId, vectors: Vec<Vec<f32>>) -> StorageBackendResult<()> {
260        let (doc_id, encoded_vectors) = self.stage_doc_vectors(doc_id, &vectors)?;
261        if self
262            .write_native(|read, batch| read.replace(batch, doc_id, &encoded_vectors))?
263            .is_some()
264        {
265            return Ok(());
266        }
267        self.conn.with_mut(|conn| {
268            let tx = conn.savepoint()?;
269            tx.execute(
270                "DELETE FROM _vectors
271                 WHERE table_name = ?1 AND field = ?2 AND doc_id = ?3",
272                params![self.table, self.field, doc_id],
273            )?;
274            let mut stmt = tx.prepare(
275                "INSERT INTO _vectors (table_name, field, doc_id, vector_ordinal, vector)
276                 VALUES (?1, ?2, ?3, ?4, ?5)",
277            )?;
278            for (ordinal, vector) in &encoded_vectors {
279                stmt.execute(params![self.table, self.field, doc_id, ordinal, vector,])?;
280            }
281            drop(stmt);
282            tx.commit()?;
283            Ok(())
284        })?;
285        Ok(())
286    }
287
288    fn delete(&mut self, doc_id: DocId) -> StorageBackendResult<()> {
289        let doc_id = encode_doc_id(doc_id)?;
290        if self
291            .write_native(|read, batch| read.delete(batch, doc_id))?
292            .is_some()
293        {
294            return Ok(());
295        }
296        self.conn.with(|c| {
297            c.execute(
298                "DELETE FROM _vectors
299                 WHERE table_name = ?1 AND field = ?2 AND doc_id = ?3",
300                params![self.table, self.field, doc_id],
301            )?;
302            Ok(())
303        })?;
304        Ok(())
305    }
306
307    fn clear(&mut self) -> StorageBackendResult<()> {
308        if self
309            .write_native(|read, batch| {
310                read.clear_family(batch, crate::mvcc::native::NativeRecordFamily::Vectors)
311            })?
312            .is_some()
313        {
314            return Ok(());
315        }
316        self.conn.with(|c| {
317            c.execute(
318                "DELETE FROM _vectors WHERE table_name = ?1 AND field = ?2",
319                params![self.table, self.field],
320            )?;
321            Ok(())
322        })?;
323        Ok(())
324    }
325
326    fn search_knn(&self, query: &[f32], k: usize) -> StorageBackendResult<PostingList> {
327        self.validate_dimensions(query)?;
328        if k == 0 {
329            return Ok(PostingList::new());
330        }
331        let Some(scores) = self.score_vectors(query, None)? else {
332            return Ok(PostingList::new());
333        };
334        let (mut scores, score_memory) = scores.into_parts();
335        select_top_k_scored(&mut scores, k);
336        scores.sort_by_key(|(id, _)| *id);
337        Ok(self.score_postings(scores, score_memory.budget())?)
338    }
339
340    fn search_threshold(&self, query: &[f32], threshold: f32) -> StorageBackendResult<PostingList> {
341        self.validate_dimensions(query)?;
342        if !threshold.is_finite() {
343            return Err(uqa_storage::StorageBackendError::Other(format!(
344                "vector similarity threshold must be finite, got {threshold}"
345            )));
346        }
347        let Some(scores) = self.score_vectors(query, Some(threshold))? else {
348            return Ok(PostingList::new());
349        };
350        let (mut scores, score_memory) = scores.into_parts();
351        scores.sort_by_key(|(id, _)| *id);
352        Ok(self.score_postings(scores, score_memory.budget())?)
353    }
354
355    fn count(&self) -> StorageBackendResult<usize> {
356        if let Some(snapshot) = self.native_snapshot()? {
357            return Ok(NativeVectorRead::new(&snapshot, self)?.count()?);
358        }
359        Ok(self.conn.with(|c| {
360            let n: i64 = c.query_row(
361                "SELECT COUNT(*) FROM _vectors WHERE table_name = ?1 AND field = ?2",
362                params![self.table, self.field],
363                |r| r.get(0),
364            )?;
365            i64_to_usize("vector count", n)
366        })?)
367    }
368
369    fn snapshot(&self) -> StorageBackendResult<Arc<dyn VectorIndex>> {
370        Ok(Arc::new(self.retained_snapshot()?))
371    }
372    fn vector_read_snapshot(
373        &self,
374        control: &uqa_storage::read_control::StorageReadControl,
375    ) -> StorageBackendResult<Option<uqa_storage::vector_index::VectorReadSnapshot>> {
376        super::native::canonical::capture(self, control)
377    }
378}
379
380#[cfg(test)]
381mod tests;