chroma_types/
signed_rbm.rs

1use std::ops::{BitAnd, BitOr};
2
3use roaring::RoaringBitmap;
4
5/// This enum helps to delay the evaluation of set minus in metadata filtering:
6/// - `Include(rbm)` suggests the result contains the specified ids in `rbm`.
7///   For example, `<k>: {$eq: <v>}` will result in a `Include(<record ids with k=v>)`.
8/// - `Exclude(rbm)` suggests the result exludes the specified ids in `rbm`.
9///   For example, `<k>: {$ne: <v>}` will result in a `Exclude(<record ids with k=v>)`
10///
11/// Without this, we need to figure out the set of existing ids when we evaluate `$ne`, `$nin`, and `$not_contains`,
12/// but this is not always necessary and may lead to overheads. Let's consider the following where clause as an example:
13///
14/// `{$and: [{<k0>: {$gt: <v0>}}, {<k1>: {$ne: <v1>}}]}`
15///
16/// The naive way is to evaluate the `$gt` and `$ne` seperately and take the conjunction, but this requires
17/// us to know the full set of existing ids because it is needed to evaluate `$ne`.
18/// However, we can first evaluate `$gt` and then exclude the offset ids for records with metadata `k1=v1`.
19/// This behavior is captured in the `BitAnd::bitand` operator of `SignedRoaringBitmap`:
20/// - A bitand between `Include(...)` and `Exclude(...)` will always result in `Include(...)`
21/// - This process does not require the knowledge of the full domain
22/// - The domain is needed only when we have to convert an `Exclude(...)` to the actual result in the end.
23///
24/// In summary, this enum distinguishes the results that depends on the domain and those that do not:
25/// - `Include(...)` does not depend on the domain
26/// - `Exclude(...)` depends on the domain
27///    We only need to figure out the domain (i.e. the set of ids for existing records) when it is
28///    necessary to do so.
29#[derive(Clone, Debug, PartialEq)]
30pub enum SignedRoaringBitmap {
31    Include(RoaringBitmap),
32    Exclude(RoaringBitmap),
33}
34
35impl SignedRoaringBitmap {
36    pub fn empty() -> Self {
37        Self::Include(RoaringBitmap::new())
38    }
39
40    pub fn full() -> Self {
41        Self::Exclude(RoaringBitmap::new())
42    }
43
44    pub fn contains(&self, value: u32) -> bool {
45        use SignedRoaringBitmap::*;
46        match self {
47            Include(rbm) => rbm.contains(value),
48            Exclude(rbm) => !rbm.contains(value),
49        }
50    }
51
52    pub fn flip(self) -> Self {
53        use SignedRoaringBitmap::*;
54        match self {
55            Include(rbm) => Exclude(rbm),
56            Exclude(rbm) => Include(rbm),
57        }
58    }
59}
60
61impl BitAnd for SignedRoaringBitmap {
62    type Output = Self;
63
64    fn bitand(self, rhs: Self) -> Self {
65        use SignedRoaringBitmap::*;
66        match (self, rhs) {
67            (Include(lhs), Include(rhs)) => Include(lhs & rhs),
68            (Include(lhs), Exclude(rhs)) => Include(lhs - rhs),
69            (Exclude(lhs), Include(rhs)) => Include(rhs - lhs),
70            (Exclude(lhs), Exclude(rhs)) => Exclude(lhs | rhs),
71        }
72    }
73}
74
75impl BitOr for SignedRoaringBitmap {
76    type Output = Self;
77
78    fn bitor(self, rhs: Self) -> Self::Output {
79        use SignedRoaringBitmap::*;
80        match (self, rhs) {
81            (Include(lhs), Include(rhs)) => Include(lhs | rhs),
82            (Include(lhs), Exclude(rhs)) => Exclude(rhs - lhs),
83            (Exclude(lhs), Include(rhs)) => Exclude(lhs - rhs),
84            (Exclude(lhs), Exclude(rhs)) => Exclude(lhs & rhs),
85        }
86    }
87}
chroma_types/signed_rbm.rs

chroma_types/
signed_rbm.rs
