rushdb_types/
stats.rs

1//! Planner value-distribution summaries: estimates only,
2//! never query results.
3
4/// Number of equi-width buckets in a [`Histogram`].
5pub const VALUE_DISTRIBUTION_BUCKETS: usize = 64;
6
7/// Value-domain shape of one `(kind, pid)` for planner estimates:
8/// exact extrema and distinct count, plus an equi-width histogram over the
9/// order-preserving payload space. Computed on demand from the value
10/// dictionary; never a query result.
11#[derive(Clone, Debug, PartialEq, Eq)]
12pub struct Histogram {
13    /// Smallest payload.
14    pub min: Vec<u8>,
15    /// Largest payload.
16    pub max: Vec<u8>,
17    /// Distinct payloads.
18    pub distinct: u64,
19    /// Owner-occurrence counts per fixed bucket.
20    pub buckets: [u32; VALUE_DISTRIBUTION_BUCKETS],
21    /// The walk that built this stopped at its budget: buckets, distinct and
22    /// `max` cover only the walked (smallest) prefix of the value domain.
23    pub partial: bool,
24}
25
26impl Default for Histogram {
27    fn default() -> Self {
28        Self {
29            min: Vec::new(),
30            max: Vec::new(),
31            distinct: 0,
32            buckets: [0; VALUE_DISTRIBUTION_BUCKETS],
33            partial: false,
34        }
35    }
36}
37
38impl Histogram {
39    /// Fold one distinct payload held by `count` owner-occurrences.
40    pub fn add(&mut self, payload: &[u8], count: u64) {
41        if self.min.is_empty() || payload < self.min.as_slice() {
42            self.min = payload.to_vec();
43        }
44        if payload > self.max.as_slice() {
45            self.max = payload.to_vec();
46        }
47        self.distinct += 1;
48        let bucket = &mut self.buckets[fixed_bucket_index(payload)];
49        *bucket = bucket.saturating_add(u32::try_from(count).unwrap_or(u32::MAX));
50    }
51
52    /// Resident bytes, for cache accounting.
53    #[must_use]
54    pub fn resident_bytes(&self) -> usize {
55        std::mem::size_of::<Self>() + self.min.capacity() + self.max.capacity()
56    }
57
58    /// Total owner-occurrences across all buckets.
59    #[must_use]
60    pub fn total(&self) -> u64 {
61        self.buckets.iter().map(|&b| u64::from(b)).sum()
62    }
63
64    /// Estimated owners satisfying a range bound (`above` = `Gt`/`Gte`),
65    /// interpolating uniformly within the bound's fixed bucket.
66    #[must_use]
67    #[expect(
68        clippy::cast_possible_truncation,
69        clippy::cast_precision_loss,
70        clippy::cast_sign_loss,
71        reason = "selectivity estimate: a non-negative fraction of a u32 bucket count"
72    )]
73    pub fn estimate(&self, bound: &[u8], above: bool) -> u64 {
74        let total = self.total();
75        if total == 0 || self.max.is_empty() {
76            return 0;
77        }
78        let (min_v, max_v, bound_v) = (
79            encoded_to_u128(&self.min),
80            encoded_to_u128(&self.max),
81            encoded_to_u128(bound),
82        );
83        if above {
84            if bound_v <= min_v {
85                return total;
86            }
87            if bound_v > max_v {
88                return 0;
89            }
90        } else {
91            if bound_v > max_v {
92                return total;
93            }
94            if bound_v <= min_v {
95                return 0;
96            }
97        }
98        let width = self.min.len().max(self.max.len()).max(bound.len());
99        let bidx = fixed_bucket_index(bound);
100        let (lo, hi) = fixed_bucket_bounds(width, bidx);
101        let bucket_width = hi.saturating_sub(lo).max(1);
102        let within = if above {
103            hi.saturating_sub(bound_v)
104        } else {
105            bound_v.saturating_sub(lo)
106        };
107        let fraction = (within as f64 / bucket_width as f64).clamp(0.0, 1.0);
108        let partial = (f64::from(self.buckets[bidx]) * fraction).round() as u32;
109        let rest: u64 = if above {
110            self.buckets[bidx + 1..].iter().map(|&b| u64::from(b)).sum()
111        } else {
112            self.buckets[..bidx].iter().map(|&b| u64::from(b)).sum()
113        };
114        rest.saturating_add(u64::from(partial)).min(total)
115    }
116}
117
118fn encoded_to_u128(bytes: &[u8]) -> u128 {
119    let mut buf = [0u8; 16];
120    let take = bytes.len().min(16);
121    buf[16 - take..].copy_from_slice(&bytes[bytes.len() - take..]);
122    u128::from_be_bytes(buf)
123}
124
125fn fixed_bucket_index(encoded: &[u8]) -> usize {
126    let bits = encoded.len().saturating_mul(8);
127    let shift = bits.saturating_sub(6);
128    ((encoded_to_u128(encoded) >> shift) & 0x3F) as usize
129}
130
131fn fixed_bucket_bounds(width: usize, idx: usize) -> (u128, u128) {
132    let bits = width.saturating_mul(8);
133    let shift = bits.saturating_sub(6);
134    let lo = (idx as u128) << shift;
135    let hi = if idx + 1 < VALUE_DISTRIBUTION_BUCKETS {
136        (idx as u128 + 1) << shift
137    } else if bits >= 128 {
138        u128::MAX
139    } else {
140        (1u128 << bits) - 1
141    };
142    (lo, hi)
143}
rushdb_types/stats.rs

rushdb_types/
stats.rs
