uqa_storage/
key_value.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Backend-neutral Key/Value storage.
8//!
9//! This module is the logical storage boundary for non-relational
10//! persistence. Concrete stores only need ordered byte keys, atomic
11//! batches, prefix scans, and transaction hooks. Catalog, document,
12//! inverted-index, and vector-index behavior stays above that boundary.
13
14use std::collections::{BTreeMap, BTreeSet};
15use std::sync::Arc;
16
17use parking_lot::Mutex;
18use serde::{Deserialize, Serialize};
19use uqa_analysis::Analyzer;
20use uqa_core::{DocId, FieldName, IndexStats, Payload, PostingEntry, PostingList, Value};
21
22use crate::backend::{PersistentStorageBackend, PersistentStorageIdentity};
23use crate::document_store::{Document, DocumentMetadata, DocumentStore, StoredDocument};
24use crate::inverted_index::{AnalyzerPhase, InvertedIndex};
25use crate::vector_index::{
26    cosine_similarity, validate_vector_values, VectorIndex, VectorIndexOpenMode, VectorIndexSpec,
27};
28use crate::{StorageBackendError, StorageBackendResult};
29
30mod catalog;
31pub use catalog::KeyValueCatalog;
32
33const TAG_METADATA: u8 = b'm';
34const TAG_TABLE: u8 = b't';
35const TAG_MODEL: u8 = b'M';
36const TAG_SCORING_PARAMS: u8 = b'S';
37const TAG_NAMED_GRAPH: u8 = b'g';
38const TAG_VERTEX: u8 = b'V';
39const TAG_EDGE: u8 = b'E';
40const TAG_GRAPH_MEMBERSHIP: u8 = b'G';
41const TAG_GRAPH_LOOKUP: u8 = b'J';
42const TAG_ANALYZER: u8 = b'a';
43const TAG_ANALYZER_DESCRIPTOR: u8 = b'D';
44const TAG_FIELD_ANALYZER_BINDING: u8 = b'U';
45const TAG_TABLE_FIELD_ANALYZER: u8 = b'A';
46const TAG_FOREIGN_SERVER: u8 = b'F';
47const TAG_FOREIGN_TABLE: u8 = b'T';
48const TAG_CATALOG_INDEX: u8 = b'C';
49const TAG_PATH_INDEX: u8 = b'P';
50const TAG_PATH_INDEX_DATA: u8 = b'Q';
51const TAG_COLUMN_STATS: u8 = b'c';
52const TAG_SCHEMA: u8 = b's';
53const TAG_SEQUENCE: u8 = b'q';
54const TAG_RELATION: u8 = b'R';
55const TAG_VIEW: u8 = b'w';
56const TAG_DOCUMENT: u8 = b'd';
57const TAG_POSTING: u8 = b'p';
58const TAG_OCCURRENCE_INDEX: u8 = b'e';
59const TAG_POSTING_CLUSTER_SCORE: u8 = b'k';
60const TAG_POSTING_CLUSTER_POSITIONS: u8 = b'o';
61const TAG_POSTING_DOCUMENT: u8 = b'x';
62const TAG_DOC_LENGTH: u8 = b'l';
63const TAG_FIELD_STATS: u8 = b'f';
64const TAG_REVERSE_POSTING: u8 = b'r';
65const TAG_VECTOR: u8 = b'v';
66const TAG_BTREE_INDEX: u8 = b'B';
67const TAG_BTREE_ENTRY: u8 = b'b';
68const TAG_NAMED_BTREE_INDEX: u8 = b'N';
69const TAG_NAMED_BTREE_ENTRY: u8 = b'n';
70const TAG_IVF_METADATA: u8 = b'I';
71const TAG_IVF_CENTROID: u8 = b'i';
72const TAG_IVF_ASSIGNMENT: u8 = b'j';
73const TAG_HNSW_METADATA: u8 = b'H';
74const TAG_HNSW_NODE: u8 = b'h';
75
76/// Prefix for the unambiguous document encoding introduced after JSON arrays
77/// became ordinary [`Value::List`] values. A legacy document is plain JSON and
78/// therefore cannot start with NUL; the prefix lets reads preserve the old
79/// `Bytes`-before-`List` interpretation without misreading newly written lists.
80const DOCUMENT_VALUE_V1_PREFIX: &[u8] = b"\0uqa-document-json-v1\0";
81const DOCUMENT_VALUE_V2_PREFIX: &[u8] = b"\0uqa-document-record-v2\0";
82
83#[derive(Debug, Clone)]
84enum KeyValueBatchOperation {
85    Put(Vec<u8>, Vec<u8>),
86    Delete(Vec<u8>),
87    DeletePrefix(Vec<u8>),
88}
89
90/// Atomic mutation buffer for a [`KeyValueStore`].
91pub trait KeyValueBatch {
92    fn put(&mut self, key: &[u8], value: &[u8]) -> StorageBackendResult<()>;
93    fn delete(&mut self, key: &[u8]) -> StorageBackendResult<()>;
94    fn delete_prefix(&mut self, prefix: &[u8]) -> StorageBackendResult<()>;
95    fn commit(self: Box<Self>) -> StorageBackendResult<()>;
96}
97
98/// Ordered byte-key storage used by Key/Value catalog and index backends.
99pub trait KeyValueStore: Send + Sync {
100    fn storage_identity(&self) -> StorageBackendResult<Option<PersistentStorageIdentity>> {
101        Ok(None)
102    }
103
104    /// Open an independent transaction session over the same logical store. The default keeps simple test/custom stores source-compatible while making the missing MVCC capability explicit when a persistent engine needs a committed reader alongside a pinned statement snapshot.
105    fn open_session(&self) -> StorageBackendResult<Arc<dyn KeyValueStore>> {
106        Err(StorageBackendError::Other(
107            "independent sessions are not implemented for this KeyValue store".into(),
108        ))
109    }
110
111    fn get(&self, key: &[u8]) -> StorageBackendResult<Option<Vec<u8>>>;
112    /// Visit one borrowed value under the retained read. Providers reserve any temporary encoded payload before fetching it; callbacks must not reenter the store.
113    fn visit_value(
114        &self,
115        _key: &[u8],
116        control: &crate::read_control::StorageReadControl,
117        _visit: &mut crate::read_control::ValueReadVisitor<'_>,
118    ) -> StorageBackendResult<()> {
119        control.check()?;
120        Err(StorageBackendError::Other(
121            "controlled value reads are not supported by this KeyValue store".into(),
122        ))
123    }
124    /// Visit at most `limit` entries in key order, strictly after `after` when supplied. Encoded values remain borrowed from their provider owner and callbacks must not reenter the store.
125    fn visit_prefix_after(
126        &self,
127        _prefix: &[u8],
128        _after: Option<&[u8]>,
129        _limit: usize,
130        control: &crate::read_control::StorageReadControl,
131        _visit: &mut crate::read_control::KeyValueReadVisitor<'_>,
132    ) -> StorageBackendResult<()> {
133        control.check()?;
134        Err(StorageBackendError::Other(
135            "controlled prefix reads are not supported by this KeyValue store".into(),
136        ))
137    }
138    /// Test prefix existence under the read allowance. Providers that materialize values should implement a key-only probe.
139    fn contains_prefix_budgeted(
140        &self,
141        prefix: &[u8],
142        control: &crate::read_control::StorageReadControl,
143    ) -> StorageBackendResult<bool> {
144        let mut found = false;
145        self.visit_prefix_after(prefix, None, 1, control, &mut |_, _| {
146            found = true;
147            Ok(())
148        })?;
149        control.check()?;
150        Ok(found)
151    }
152
153    fn contains_key(&self, key: &[u8]) -> StorageBackendResult<bool> {
154        self.get(key).map(|value| value.is_some())
155    }
156    fn put(&self, key: &[u8], value: &[u8]) -> StorageBackendResult<()>;
157    fn delete(&self, key: &[u8]) -> StorageBackendResult<()>;
158    fn scan_prefix(&self, prefix: &[u8]) -> StorageBackendResult<Vec<(Vec<u8>, Vec<u8>)>>;
159    /// Return at most `limit` key/value pairs in key order, strictly after
160    /// `after` when supplied. This is the bounded value cursor used by large
161    /// format migrations and other paged consumers.
162    fn scan_prefix_after(
163        &self,
164        prefix: &[u8],
165        after: Option<&[u8]>,
166        limit: usize,
167    ) -> StorageBackendResult<Vec<(Vec<u8>, Vec<u8>)>> {
168        if limit == 0 {
169            return Ok(Vec::new());
170        }
171        Ok(self
172            .scan_prefix(prefix)?
173            .into_iter()
174            .filter(|(key, _)| after.is_none_or(|after| key.as_slice() > after))
175            .take(limit)
176            .collect())
177    }
178    /// Return at most `limit` keys in key order, strictly after `after` when
179    /// it is present. Backends should override this method with a key-only,
180    /// bounded range scan so cursor consumers neither materialize the entire
181    /// prefix nor read values they do not need on every page.
182    fn scan_prefix_keys_after(
183        &self,
184        prefix: &[u8],
185        after: Option<&[u8]>,
186        limit: usize,
187    ) -> StorageBackendResult<Vec<Vec<u8>>> {
188        if limit == 0 {
189            return Ok(Vec::new());
190        }
191        Ok(self
192            .scan_prefix(prefix)?
193            .into_iter()
194            .filter(|(key, _)| after.is_none_or(|after| key.as_slice() > after))
195            .take(limit)
196            .map(|(key, _)| key)
197            .collect())
198    }
199    fn first_prefix_after(
200        &self,
201        prefix: &[u8],
202        after: Option<&[u8]>,
203    ) -> StorageBackendResult<Option<(Vec<u8>, Vec<u8>)>> {
204        Ok(self
205            .scan_prefix(prefix)?
206            .into_iter()
207            .find(|(key, _)| after.is_none_or(|after| key.as_slice() > after)))
208    }
209    fn delete_prefix(&self, prefix: &[u8]) -> StorageBackendResult<usize>;
210    fn batch(&self) -> Box<dyn KeyValueBatch + '_>;
211
212    fn begin_transaction(&self) -> StorageBackendResult<()> {
213        Err(StorageBackendError::Other(
214            "KeyValue transaction begin is not implemented for this store".into(),
215        ))
216    }
217
218    fn begin_read_transaction(&self) -> StorageBackendResult<()> {
219        self.begin_transaction()
220    }
221
222    fn begin_upgradeable_transaction(&self) -> StorageBackendResult<()> {
223        self.begin_transaction()
224    }
225
226    fn in_transaction(&self) -> bool;
227
228    fn transaction_has_written(&self) -> StorageBackendResult<bool>;
229
230    fn change_version(&self) -> StorageBackendResult<Option<u64>> {
231        Ok(None)
232    }
233
234    fn change_version_monitor_is_nonblocking(&self) -> StorageBackendResult<bool> {
235        Ok(true)
236    }
237
238    fn pin_transaction_snapshot(&self) -> StorageBackendResult<()> {
239        Ok(())
240    }
241
242    fn commit_transaction(&self) -> StorageBackendResult<()> {
243        Err(StorageBackendError::Other(
244            "KeyValue transaction commit is not implemented for this store".into(),
245        ))
246    }
247
248    fn rollback_transaction(&self) -> StorageBackendResult<()> {
249        Err(StorageBackendError::Other(
250            "KeyValue transaction rollback is not implemented for this store".into(),
251        ))
252    }
253
254    fn savepoint(&self, _name: &str) -> StorageBackendResult<()> {
255        Err(StorageBackendError::Other(
256            "KeyValue savepoints are not implemented for this store".into(),
257        ))
258    }
259
260    fn release_savepoint(&self, _name: &str) -> StorageBackendResult<()> {
261        Err(StorageBackendError::Other(
262            "KeyValue savepoint release is not implemented for this store".into(),
263        ))
264    }
265
266    fn rollback_to_savepoint(&self, _name: &str) -> StorageBackendResult<()> {
267        Err(StorageBackendError::Other(
268            "KeyValue savepoint rollback is not implemented for this store".into(),
269        ))
270    }
271}
272
273mod btree_index;
274mod codec;
275pub mod conformance;
276mod document_store;
277mod hnsw_index;
278mod hnsw_persistence;
279mod index_keys;
280mod inverted_index;
281mod ivf_index;
282mod ivf_persistence;
283mod memory_store;
284mod occurrence_keys;
285mod storage_backend;
286mod vector_index;
287
288pub use codec::prefix_upper_bound;
289pub use document_store::KeyValueDocumentStore;
290pub use hnsw_index::KeyValueHNSWIndex;
291pub use inverted_index::KeyValueInvertedIndex;
292pub use ivf_index::KeyValueIVFIndex;
293pub use memory_store::MemoryKeyValueStore;
294pub use storage_backend::KeyValueStorageBackend;
295pub use vector_index::KeyValueVectorIndex;
296
297#[cfg(test)]
298mod tests;
uqa_storage/key_value.rs

uqa_storage/
key_value.rs
