tonbo_predicate/core/
row_set.rs

1//! Shared row-set abstractions built on top of roaring bitmaps.
2
3use std::convert::TryFrom;
4
5use roaring::RoaringBitmap;
6
7/// Unique identifier for a row referenced by the planner.
8pub type RowId = u32;
9
10/// Borrowed iterator that yields [`RowId`] values.
11pub type RowIdIter<'a> = Box<dyn Iterator<Item = RowId> + Send + 'a>;
12
13/// Abstract set of row identifiers that supports basic set algebra.
14pub trait RowSet: Send + Sync {
15    /// Returns the number of rows tracked by the set.
16    fn len(&self) -> usize;
17
18    /// Returns true when the set is empty.
19    fn is_empty(&self) -> bool {
20        self.len() == 0
21    }
22
23    /// Returns true when the set represents the whole universe of rows.
24    fn is_full(&self) -> bool;
25
26    /// Returns an iterator over row identifiers.
27    fn iter(&self) -> RowIdIter<'_>;
28
29    /// Returns the intersection between this set and `other`.
30    fn intersect(&self, other: &Self) -> Self
31    where
32        Self: Sized;
33
34    /// Returns the union between this set and `other`.
35    fn union(&self, other: &Self) -> Self
36    where
37        Self: Sized;
38
39    /// Returns the relative complement (`self \ other`).
40    fn difference(&self, other: &Self) -> Self
41    where
42        Self: Sized;
43}
44
45/// [`RowSet`] implementation backed by a roaring bitmap.
46#[derive(Clone, Debug, Default)]
47pub struct BitmapRowSet {
48    bitmap: RoaringBitmap,
49}
50
51impl BitmapRowSet {
52    /// Creates an empty bitmap-backed row set.
53    #[must_use]
54    pub fn new() -> Self {
55        Self::default()
56    }
57
58    /// Inserts a row identifier into the set.
59    pub fn insert(&mut self, row: RowId) {
60        self.bitmap.insert(row);
61    }
62
63    /// Returns true when the set contains the provided row identifier.
64    #[must_use]
65    pub fn contains(&self, row: RowId) -> bool {
66        self.bitmap.contains(row)
67    }
68}
69
70impl RowSet for BitmapRowSet {
71    fn len(&self) -> usize {
72        usize::try_from(self.bitmap.len()).unwrap_or(usize::MAX)
73    }
74
75    fn is_full(&self) -> bool {
76        self.bitmap.is_full()
77    }
78
79    fn iter(&self) -> RowIdIter<'_> {
80        Box::new(self.bitmap.iter())
81    }
82
83    fn intersect(&self, other: &Self) -> Self {
84        let bitmap = &self.bitmap & &other.bitmap;
85        Self { bitmap }
86    }
87
88    fn union(&self, other: &Self) -> Self {
89        let bitmap = &self.bitmap | &other.bitmap;
90        Self { bitmap }
91    }
92
93    fn difference(&self, other: &Self) -> Self {
94        let bitmap = &self.bitmap - &other.bitmap;
95        Self { bitmap }
96    }
97}
tonbo_predicate/core/row_set.rs

tonbo_predicate/core/
row_set.rs
