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