mongreldb_core/index/
bitmap.rs

1//! Roaring-bitmap secondary index — `value bytes → row-id set`.
2//!
3//! Best for low-cardinality columns (equality, IN, GROUP BY). Multiple indexes
4//! intersect with cheap SIMD bitmap ops in the shared [`RowId`] space.
5
6use crate::rowid::RowId;
7use roaring::RoaringBitmap;
8
9/// `value → row-id set`. Values are type-aware encoded bytes (lexicographically
10/// comparable), matching the encoding used for page min/max.
11#[derive(Clone)]
12pub struct BitmapIndex {
13    map: std::collections::HashMap<Vec<u8>, RoaringBitmap>,
14}
15
16impl Default for BitmapIndex {
17    fn default() -> Self {
18        Self::new()
19    }
20}
21
22impl BitmapIndex {
23    pub fn new() -> Self {
24        Self {
25            map: std::collections::HashMap::new(),
26        }
27    }
28
29    pub fn insert(&mut self, value: Vec<u8>, row_id: RowId) {
30        // Roaring bitmaps address u32. The Phase-3 upgrade shards bitmaps by
31        // the high 32 bits to cover the full u64 row-id space; until then we
32        // require row ids < 2^32.
33        let id32 = u32::try_from(row_id.0)
34            .expect("bitmap index supports row_id < 2^32; shard-by-high-bits is a Phase-3 upgrade");
35        self.map.entry(value).or_default().insert(id32);
36    }
37
38    /// The row-id set for `value` (empty if absent).
39    pub fn get(&self, value: &[u8]) -> RoaringBitmap {
40        self.map.get(value).cloned().unwrap_or_default()
41    }
42
43    /// Intersection of several sets — the workhorse of multi-condition queries.
44    pub fn intersect(sets: &[RoaringBitmap]) -> RoaringBitmap {
45        match sets {
46            [] => RoaringBitmap::new(),
47            [first, rest @ ..] => {
48                let mut acc = first.clone();
49                for s in rest {
50                    acc &= s;
51                }
52                acc
53            }
54        }
55    }
56
57    pub fn value_count(&self) -> usize {
58        self.map.len()
59    }
60
61    /// All distinct values (keys) in this index — Phase 17.2 broadcast join.
62    pub fn keys(&self) -> Vec<&Vec<u8>> {
63        self.map.keys().collect()
64    }
65
66    /// Snapshot `(value_bytes → serialized RoaringBitmap)` pairs for
67    /// checkpointing to `_idx/global.idx`.
68    pub fn entries(&self) -> Vec<(Vec<u8>, Vec<u8>)> {
69        self.map
70            .iter()
71            .map(|(k, v)| {
72                let mut bytes = Vec::new();
73                v.serialize_into(&mut bytes)
74                    .expect("roaring serialize is infallible for Vec");
75                (k.clone(), bytes)
76            })
77            .collect()
78    }
79
80    /// Rebuild from a snapshot produced by [`BitmapIndex::entries`].
81    pub fn from_entries(
82        entries: Vec<(Vec<u8>, Vec<u8>)>,
83    ) -> std::result::Result<Self, &'static str> {
84        let mut map = std::collections::HashMap::new();
85        for (k, bytes) in entries {
86            let bm = RoaringBitmap::deserialize_from(&bytes[..]).map_err(|_| "bad bitmap bytes")?;
87            map.insert(k, bm);
88        }
89        Ok(Self { map })
90    }
91}
92
93#[cfg(test)]
94mod tests {
95    use super::*;
96
97    #[test]
98    fn insert_get_and_intersect() {
99        let mut color = BitmapIndex::new();
100        color.insert(b"red".to_vec(), RowId(1));
101        color.insert(b"red".to_vec(), RowId(3));
102        color.insert(b"blue".to_vec(), RowId(3));
103
104        let mut region = BitmapIndex::new();
105        region.insert(b"us".to_vec(), RowId(1));
106        region.insert(b"us".to_vec(), RowId(3));
107        region.insert(b"eu".to_vec(), RowId(2));
108
109        let red = color.get(b"red");
110        let us = region.get(b"us");
111        let both = BitmapIndex::intersect(&[red, us]);
112        let ids: Vec<u32> = both.iter().collect();
113        assert_eq!(ids, vec![1, 3]);
114    }
115}
mongreldb_core/index/bitmap.rs

mongreldb_core/index/
bitmap.rs
