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_ANALYZER: u8 = b'a';
42const TAG_TABLE_FIELD_ANALYZER: u8 = b'A';
43const TAG_FOREIGN_SERVER: u8 = b'F';
44const TAG_FOREIGN_TABLE: u8 = b'T';
45const TAG_CATALOG_INDEX: u8 = b'C';
46const TAG_PATH_INDEX: u8 = b'P';
47const TAG_COLUMN_STATS: u8 = b'c';
48const TAG_SCHEMA: u8 = b's';
49const TAG_SEQUENCE: u8 = b'q';
50const TAG_RELATION: u8 = b'R';
51const TAG_VIEW: u8 = b'w';
52const TAG_DOCUMENT: u8 = b'd';
53const TAG_POSTING: u8 = b'p';
54const TAG_POSTING_CLUSTER_SCORE: u8 = b'k';
55const TAG_POSTING_CLUSTER_POSITIONS: u8 = b'o';
56const TAG_POSTING_DOCUMENT: u8 = b'x';
57const TAG_DOC_LENGTH: u8 = b'l';
58const TAG_FIELD_STATS: u8 = b'f';
59const TAG_REVERSE_POSTING: u8 = b'r';
60const TAG_VECTOR: u8 = b'v';
61const TAG_BTREE_INDEX: u8 = b'B';
62const TAG_BTREE_ENTRY: u8 = b'b';
63const TAG_NAMED_BTREE_INDEX: u8 = b'N';
64const TAG_NAMED_BTREE_ENTRY: u8 = b'n';
65const TAG_IVF_METADATA: u8 = b'I';
66const TAG_IVF_CENTROID: u8 = b'i';
67const TAG_IVF_ASSIGNMENT: u8 = b'j';
68const TAG_HNSW_METADATA: u8 = b'H';
69const TAG_HNSW_NODE: u8 = b'h';
70
71/// Prefix for the unambiguous document encoding introduced after JSON arrays
72/// became ordinary [`Value::List`] values. A legacy document is plain JSON and
73/// therefore cannot start with NUL; the prefix lets reads preserve the old
74/// `Bytes`-before-`List` interpretation without misreading newly written lists.
75const DOCUMENT_VALUE_V1_PREFIX: &[u8] = b"\0uqa-document-json-v1\0";
76const DOCUMENT_VALUE_V2_PREFIX: &[u8] = b"\0uqa-document-record-v2\0";
77
78#[derive(Debug, Clone)]
79enum KeyValueBatchOperation {
80    Put(Vec<u8>, Vec<u8>),
81    Delete(Vec<u8>),
82    DeletePrefix(Vec<u8>),
83}
84
85/// Atomic mutation buffer for a [`KeyValueStore`].
86pub trait KeyValueBatch {
87    fn put(&mut self, key: &[u8], value: &[u8]) -> StorageBackendResult<()>;
88    fn delete(&mut self, key: &[u8]) -> StorageBackendResult<()>;
89    fn delete_prefix(&mut self, prefix: &[u8]) -> StorageBackendResult<()>;
90    fn commit(self: Box<Self>) -> StorageBackendResult<()>;
91}
92
93/// Ordered byte-key storage used by Key/Value catalog and index backends.
94pub trait KeyValueStore: Send + Sync {
95    fn storage_identity(&self) -> StorageBackendResult<Option<PersistentStorageIdentity>> {
96        Ok(None)
97    }
98
99    /// 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.
100    fn open_session(&self) -> StorageBackendResult<Arc<dyn KeyValueStore>> {
101        Err(StorageBackendError::Other(
102            "independent sessions are not implemented for this KeyValue store".into(),
103        ))
104    }
105
106    fn get(&self, key: &[u8]) -> StorageBackendResult<Option<Vec<u8>>>;
107    fn contains_key(&self, key: &[u8]) -> StorageBackendResult<bool> {
108        self.get(key).map(|value| value.is_some())
109    }
110    fn put(&self, key: &[u8], value: &[u8]) -> StorageBackendResult<()>;
111    fn delete(&self, key: &[u8]) -> StorageBackendResult<()>;
112    fn scan_prefix(&self, prefix: &[u8]) -> StorageBackendResult<Vec<(Vec<u8>, Vec<u8>)>>;
113    /// Return at most `limit` key/value pairs in key order, strictly after
114    /// `after` when supplied. This is the bounded value cursor used by large
115    /// format migrations and other paged consumers.
116    fn scan_prefix_after(
117        &self,
118        prefix: &[u8],
119        after: Option<&[u8]>,
120        limit: usize,
121    ) -> StorageBackendResult<Vec<(Vec<u8>, Vec<u8>)>> {
122        if limit == 0 {
123            return Ok(Vec::new());
124        }
125        Ok(self
126            .scan_prefix(prefix)?
127            .into_iter()
128            .filter(|(key, _)| after.is_none_or(|after| key.as_slice() > after))
129            .take(limit)
130            .collect())
131    }
132    /// Return at most `limit` keys in key order, strictly after `after` when
133    /// it is present. Backends should override this method with a key-only,
134    /// bounded range scan so cursor consumers neither materialize the entire
135    /// prefix nor read values they do not need on every page.
136    fn scan_prefix_keys_after(
137        &self,
138        prefix: &[u8],
139        after: Option<&[u8]>,
140        limit: usize,
141    ) -> StorageBackendResult<Vec<Vec<u8>>> {
142        if limit == 0 {
143            return Ok(Vec::new());
144        }
145        Ok(self
146            .scan_prefix(prefix)?
147            .into_iter()
148            .filter(|(key, _)| after.is_none_or(|after| key.as_slice() > after))
149            .take(limit)
150            .map(|(key, _)| key)
151            .collect())
152    }
153    fn first_prefix_after(
154        &self,
155        prefix: &[u8],
156        after: Option<&[u8]>,
157    ) -> StorageBackendResult<Option<(Vec<u8>, Vec<u8>)>> {
158        Ok(self
159            .scan_prefix(prefix)?
160            .into_iter()
161            .find(|(key, _)| after.is_none_or(|after| key.as_slice() > after)))
162    }
163    fn delete_prefix(&self, prefix: &[u8]) -> StorageBackendResult<usize>;
164    fn batch(&self) -> Box<dyn KeyValueBatch + '_>;
165
166    fn begin_transaction(&self) -> StorageBackendResult<()> {
167        Err(StorageBackendError::Other(
168            "KeyValue transaction begin is not implemented for this store".into(),
169        ))
170    }
171
172    fn begin_read_transaction(&self) -> StorageBackendResult<()> {
173        self.begin_transaction()
174    }
175
176    fn begin_upgradeable_transaction(&self) -> StorageBackendResult<()> {
177        self.begin_transaction()
178    }
179
180    fn in_transaction(&self) -> bool;
181
182    fn transaction_has_written(&self) -> StorageBackendResult<bool>;
183
184    fn change_version(&self) -> StorageBackendResult<Option<u64>> {
185        Ok(None)
186    }
187
188    fn change_version_monitor_is_nonblocking(&self) -> StorageBackendResult<bool> {
189        Ok(true)
190    }
191
192    fn pin_transaction_snapshot(&self) -> StorageBackendResult<()> {
193        Ok(())
194    }
195
196    fn commit_transaction(&self) -> StorageBackendResult<()> {
197        Err(StorageBackendError::Other(
198            "KeyValue transaction commit is not implemented for this store".into(),
199        ))
200    }
201
202    fn rollback_transaction(&self) -> StorageBackendResult<()> {
203        Err(StorageBackendError::Other(
204            "KeyValue transaction rollback is not implemented for this store".into(),
205        ))
206    }
207
208    fn savepoint(&self, _name: &str) -> StorageBackendResult<()> {
209        Err(StorageBackendError::Other(
210            "KeyValue savepoints are not implemented for this store".into(),
211        ))
212    }
213
214    fn release_savepoint(&self, _name: &str) -> StorageBackendResult<()> {
215        Err(StorageBackendError::Other(
216            "KeyValue savepoint release is not implemented for this store".into(),
217        ))
218    }
219
220    fn rollback_to_savepoint(&self, _name: &str) -> StorageBackendResult<()> {
221        Err(StorageBackendError::Other(
222            "KeyValue savepoint rollback is not implemented for this store".into(),
223        ))
224    }
225}
226
227mod btree_index;
228mod codec;
229pub mod conformance;
230mod document_store;
231mod hnsw_index;
232mod hnsw_persistence;
233mod index_keys;
234mod inverted_index;
235mod ivf_index;
236mod ivf_persistence;
237mod memory_store;
238mod storage_backend;
239mod vector_index;
240
241pub use codec::prefix_upper_bound;
242pub use document_store::KeyValueDocumentStore;
243pub use hnsw_index::KeyValueHNSWIndex;
244pub use inverted_index::KeyValueInvertedIndex;
245pub use ivf_index::KeyValueIVFIndex;
246pub use memory_store::MemoryKeyValueStore;
247pub use storage_backend::KeyValueStorageBackend;
248pub use vector_index::KeyValueVectorIndex;
249
250#[cfg(test)]
251mod tests;
uqa_storage/key_value.rs

uqa_storage/
key_value.rs
