reddb_server/storage/index/
mod.rs

1//! Unified index abstraction shared across RedDB data structures.
2//!
3//! Tables, graphs, vectors, timeseries, documents and queues each maintain
4//! their own access structures today (btree, hash, bitmap, HNSW, inverted
5//! lists, adjacency maps...). This module does not replace those concrete
6//! implementations — it defines the cross-cutting traits and primitives so
7//! the query planner, segment layer and diagnostics can treat them uniformly.
8//!
9//! # Components
10//!
11//! - [`IndexBase`]   — metadata, stats, bloom, lifecycle
12//! - [`PointIndex`]  — key → values lookups
13//! - [`RangeIndex`]  — ordered iteration over key ranges
14//! - [`IndexStats`]  — cardinality/selectivity surfaced to the planner
15//! - [`IndexKind`]   — enum of supported index families
16//! - [`BloomSegment`] — reusable bloom header attachable to any segment
17//!
18//! Each concrete index (existing or future) can opt-in by implementing the
19//! traits that match its access patterns. Cross-structure features such as
20//! the hybrid executor, plan cache statistics and segment pruning consume the
21//! traits, not concrete types.
22
23pub mod bloom_segment;
24pub mod heavy_hitters;
25pub mod registry;
26pub mod stats;
27pub mod tid_bitmap;
28pub mod zone_map;
29pub mod zone_map_persist;
30
31pub use bloom_segment::{BloomSegment, BloomSegmentBuilder, HasBloom};
32pub use heavy_hitters::HeavyHitters;
33pub use registry::{IndexRegistry, IndexScope, SharedIndex};
34pub use stats::{IndexKind, IndexStats};
35pub use zone_map::{ZoneDecision, ZoneMap, ZonePredicate};
36
37use std::fmt;
38
39/// Error type emitted by index operations.
40#[derive(Debug, Clone)]
41pub enum IndexError {
42    /// Key was not valid for this index (e.g. wrong type).
43    InvalidKey(String),
44    /// Value was not valid for this index.
45    InvalidValue(String),
46    /// Index is read-only / sealed.
47    ReadOnly,
48    /// Capacity exceeded.
49    Full,
50    /// Underlying storage error.
51    Storage(String),
52}
53
54impl fmt::Display for IndexError {
55    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
56        match self {
57            IndexError::InvalidKey(m) => write!(f, "invalid key: {m}"),
58            IndexError::InvalidValue(m) => write!(f, "invalid value: {m}"),
59            IndexError::ReadOnly => write!(f, "index is read-only"),
60            IndexError::Full => write!(f, "index capacity exceeded"),
61            IndexError::Storage(m) => write!(f, "storage error: {m}"),
62        }
63    }
64}
65
66impl std::error::Error for IndexError {}
67
68/// Cross-cutting metadata every index exposes. Used by the planner for
69/// cost estimation, by the segment layer for bloom-based pruning and by
70/// diagnostics tooling.
71pub trait IndexBase: Send + Sync {
72    /// Human-readable name (e.g. "users.email", "graph.city_by_node").
73    fn name(&self) -> &str;
74
75    /// Index family (btree, hash, bitmap, hnsw, ...).
76    fn kind(&self) -> IndexKind;
77
78    /// Current statistics (cardinality, estimated selectivity, memory).
79    fn stats(&self) -> IndexStats;
80
81    /// Returns `true` iff the key is *guaranteed* to be absent from this
82    /// index. Default implementation returns `false` (meaning "don't know —
83    /// caller must probe").
84    ///
85    /// Concrete indexes may override with tighter signals (e.g. zone map
86    /// min/max for range indexes).
87    fn definitely_absent(&self, _key_bytes: &[u8]) -> bool {
88        false
89    }
90}
91
92/// Point lookup access pattern. Implemented by hash, btree (as exact match),
93/// bitmap, cuckoo, etc.
94pub trait PointIndex<K: ?Sized, V>: IndexBase {
95    /// Insert `value` under `key`. Multi-value semantics are index-specific.
96    fn insert(&mut self, key: &K, value: V) -> Result<(), IndexError>;
97
98    /// Remove all values under `key`. Returns number removed.
99    fn remove(&mut self, key: &K) -> Result<usize, IndexError>;
100
101    /// Look up every value associated with `key`.
102    fn lookup(&self, key: &K) -> Vec<V>;
103
104    /// Convenience: does the key exist at all?
105    fn contains(&self, key: &K) -> bool {
106        !self.lookup(key).is_empty()
107    }
108}
109
110/// Range / ordered access pattern. Implemented by btree, skiplist, zone map.
111pub trait RangeIndex<K: ?Sized, V>: PointIndex<K, V> {
112    /// Iterate values whose key falls in `[start, end)`.
113    /// `None` bounds are open (min/max).
114    fn range(&self, start: Option<&K>, end: Option<&K>) -> Vec<(Vec<u8>, V)>;
115
116    /// Total number of distinct keys.
117    fn distinct_keys(&self) -> usize;
118}
119
120#[cfg(test)]
121mod tests {
122    use super::*;
123    use crate::storage::index::BloomSegment;
124    use std::collections::BTreeMap;
125
126    /// Tiny in-memory btree to exercise the traits end-to-end.
127    struct TestBTree {
128        name: String,
129        map: BTreeMap<Vec<u8>, Vec<u64>>,
130        bloom: BloomSegment,
131    }
132
133    impl TestBTree {
134        fn new(name: &str) -> Self {
135            Self {
136                name: name.to_string(),
137                map: BTreeMap::new(),
138                bloom: BloomSegment::with_capacity(1024),
139            }
140        }
141    }
142
143    impl IndexBase for TestBTree {
144        fn name(&self) -> &str {
145            &self.name
146        }
147        fn kind(&self) -> IndexKind {
148            IndexKind::BTree
149        }
150        fn stats(&self) -> IndexStats {
151            IndexStats {
152                entries: self.map.values().map(|v| v.len()).sum(),
153                distinct_keys: self.map.len(),
154                approx_bytes: 0,
155                kind: IndexKind::BTree,
156                has_bloom: true,
157                index_correlation: 0.0,
158            }
159        }
160        fn definitely_absent(&self, key_bytes: &[u8]) -> bool {
161            self.bloom.definitely_absent(key_bytes)
162        }
163    }
164
165    impl PointIndex<[u8], u64> for TestBTree {
166        fn insert(&mut self, key: &[u8], value: u64) -> Result<(), IndexError> {
167            self.bloom.insert(key);
168            self.map.entry(key.to_vec()).or_default().push(value);
169            Ok(())
170        }
171        fn remove(&mut self, key: &[u8]) -> Result<usize, IndexError> {
172            Ok(self.map.remove(key).map(|v| v.len()).unwrap_or(0))
173        }
174        fn lookup(&self, key: &[u8]) -> Vec<u64> {
175            self.map.get(key).cloned().unwrap_or_default()
176        }
177    }
178
179    impl RangeIndex<[u8], u64> for TestBTree {
180        fn range(&self, start: Option<&[u8]>, end: Option<&[u8]>) -> Vec<(Vec<u8>, u64)> {
181            use std::ops::Bound;
182            let lo = start.map(Bound::Included).unwrap_or(Bound::Unbounded);
183            let hi = end.map(Bound::Excluded).unwrap_or(Bound::Unbounded);
184            self.map
185                .range::<[u8], _>((lo, hi))
186                .flat_map(|(k, vs)| vs.iter().map(move |v| (k.clone(), *v)))
187                .collect()
188        }
189        fn distinct_keys(&self) -> usize {
190            self.map.len()
191        }
192    }
193
194    #[test]
195    fn point_index_roundtrip() {
196        let mut idx = TestBTree::new("test");
197        idx.insert(b"alpha", 1).unwrap();
198        idx.insert(b"alpha", 2).unwrap();
199        idx.insert(b"beta", 3).unwrap();
200
201        assert_eq!(idx.lookup(b"alpha"), vec![1, 2]);
202        assert!(idx.contains(b"beta"));
203        assert!(!idx.contains(b"gamma"));
204    }
205
206    #[test]
207    fn bloom_prunes_absent_keys() {
208        let mut idx = TestBTree::new("test");
209        idx.insert(b"alpha", 1).unwrap();
210        // Bloom must never produce false negatives.
211        assert!(!idx.definitely_absent(b"alpha"));
212        // Random unknown key: bloom may say "absent" or "unknown".
213        // Either way, probing must still return empty.
214        assert!(idx.lookup(b"not-there").is_empty());
215    }
216
217    #[test]
218    fn range_iteration() {
219        let mut idx = TestBTree::new("test");
220        for (i, k) in [b"a", b"b", b"c", b"d"].iter().enumerate() {
221            idx.insert(*k, i as u64).unwrap();
222        }
223        let out = idx.range(Some(b"b"), Some(b"d"));
224        let keys: Vec<&[u8]> = out.iter().map(|(k, _)| k.as_slice()).collect();
225        assert_eq!(keys, vec![b"b".as_slice(), b"c".as_slice()]);
226    }
227
228    #[test]
229    fn stats_surface_cardinality() {
230        let mut idx = TestBTree::new("test");
231        idx.insert(b"a", 1).unwrap();
232        idx.insert(b"a", 2).unwrap();
233        idx.insert(b"b", 3).unwrap();
234        let s = idx.stats();
235        assert_eq!(s.entries, 3);
236        assert_eq!(s.distinct_keys, 2);
237        assert!(s.has_bloom);
238    }
239}
reddb_server/storage/index/mod.rs

reddb_server/storage/index/
mod.rs
