chronix_engine/segment/
validity.rs

1//! Per-block validity bitmaps (`.csx` v2, D-NULL).
2//!
3//! Before v2 an absent field was encoded as a type-specific sentinel — `0`,
4//! `""` or `false` — and only an aggregate `null_count` survived in the block
5//! statistics. A stored zero and an absent field were therefore
6//! indistinguishable at read time, so `IS NULL` never matched, `= 0` matched
7//! rows that had no value at all, and `AVG`/`MIN`/`COUNT` silently folded
8//! sentinels into their results.
9//!
10//! v2 stores an Arrow-compatible validity bitmap next to each column block:
11//! LSB-first packed bits, one per row, **set = the row holds a real value**.
12//! Blocks with no nulls store no bitmap at all (`validity_length == 0`), so
13//! dense time-series data — the common case — pays nothing.
14//!
15//! The bitmap is written uncompressed and unencrypted. It leaks only *which*
16//! rows have values, never what they are, and keeping it outside the
17//! compressed/encrypted payload lets the reader build an Arrow `NullBuffer`
18//! with a single copy.
19
20use arrow::buffer::{BooleanBuffer, NullBuffer};
21
22/// Number of bytes needed to hold `len` validity bits.
23#[must_use]
24pub const fn bitmap_len(len: usize) -> usize {
25    len.div_ceil(8)
26}
27
28/// Incrementally builds a validity bitmap while a column block is encoded.
29#[derive(Debug)]
30pub struct ValidityBuilder {
31    bits: Vec<u8>,
32    len: usize,
33    nulls: usize,
34}
35
36impl ValidityBuilder {
37    /// Create a builder sized for `capacity` rows.
38    #[must_use]
39    pub fn with_capacity(capacity: usize) -> Self {
40        Self {
41            bits: vec![0u8; bitmap_len(capacity)],
42            len: 0,
43            nulls: 0,
44        }
45    }
46
47    /// Record one row: `valid == true` means a real value is present.
48    pub fn push(&mut self, valid: bool) {
49        let byte = self.len / 8;
50        if byte >= self.bits.len() {
51            self.bits.resize(byte + 1, 0);
52        }
53        if valid {
54            self.bits[byte] |= 1u8 << (self.len % 8);
55        } else {
56            self.nulls += 1;
57        }
58        self.len += 1;
59    }
60
61    /// Number of rows recorded so far.
62    #[must_use]
63    pub fn len(&self) -> usize {
64        self.len
65    }
66
67    /// Whether no rows have been recorded.
68    #[must_use]
69    pub fn is_empty(&self) -> bool {
70        self.len == 0
71    }
72
73    /// Number of null rows recorded so far.
74    #[must_use]
75    pub fn null_count(&self) -> usize {
76        self.nulls
77    }
78
79    /// Finish the bitmap.
80    ///
81    /// Returns `None` when every row was valid — the overwhelmingly common
82    /// case for time-series columns — so that dense blocks store no bitmap.
83    #[must_use]
84    pub fn finish(mut self) -> Option<Vec<u8>> {
85        if self.nulls == 0 {
86            return None;
87        }
88        self.bits.truncate(bitmap_len(self.len));
89        Some(self.bits)
90    }
91}
92
93/// Rebuild an Arrow [`NullBuffer`] from a stored bitmap.
94///
95/// `bytes` must hold at least [`bitmap_len(len)`](bitmap_len) bytes; extra
96/// trailing bytes are ignored. Returns `None` if the bitmap marks every row
97/// valid, which lets the caller skip attaching a null buffer entirely.
98#[must_use]
99pub fn null_buffer_from_bytes(bytes: &[u8], len: usize) -> Option<NullBuffer> {
100    if len == 0 || bytes.len() < bitmap_len(len) {
101        return None;
102    }
103    let buffer = BooleanBuffer::new(bytes[..bitmap_len(len)].to_vec().into(), 0, len);
104    let nulls = NullBuffer::new(buffer);
105    if nulls.null_count() == 0 {
106        None
107    } else {
108        Some(nulls)
109    }
110}
111
112#[cfg(test)]
113mod tests {
114    use super::*;
115
116    #[test]
117    fn dense_block_stores_no_bitmap() {
118        let mut b = ValidityBuilder::with_capacity(100);
119        for _ in 0..100 {
120            b.push(true);
121        }
122        assert_eq!(b.null_count(), 0);
123        assert!(b.finish().is_none());
124    }
125
126    #[test]
127    fn roundtrips_sparse_pattern() {
128        let pattern: Vec<bool> = (0..137).map(|i| i % 3 != 0).collect();
129        let mut b = ValidityBuilder::with_capacity(pattern.len());
130        for &v in &pattern {
131            b.push(v);
132        }
133        let expected_nulls = pattern.iter().filter(|v| !**v).count();
134        assert_eq!(b.null_count(), expected_nulls);
135
136        let bytes = b.finish().expect("has nulls");
137        assert_eq!(bytes.len(), bitmap_len(pattern.len()));
138
139        let nulls = null_buffer_from_bytes(&bytes, pattern.len()).expect("has nulls");
140        assert_eq!(nulls.null_count(), expected_nulls);
141        for (i, &want) in pattern.iter().enumerate() {
142            assert_eq!(nulls.is_valid(i), want, "row {i}");
143        }
144    }
145
146    #[test]
147    fn all_null_block() {
148        let mut b = ValidityBuilder::with_capacity(9);
149        for _ in 0..9 {
150            b.push(false);
151        }
152        let bytes = b.finish().expect("has nulls");
153        let nulls = null_buffer_from_bytes(&bytes, 9).expect("has nulls");
154        assert_eq!(nulls.null_count(), 9);
155    }
156
157    #[test]
158    fn truncated_bitmap_is_rejected() {
159        assert!(null_buffer_from_bytes(&[0xFF], 100).is_none());
160        assert!(null_buffer_from_bytes(&[], 0).is_none());
161    }
162
163    #[test]
164    fn all_valid_bitmap_yields_no_null_buffer() {
165        // A bitmap that happens to mark everything valid needs no NullBuffer.
166        assert!(null_buffer_from_bytes(&[0xFF], 8).is_none());
167    }
168
169    #[test]
170    fn bitmap_len_rounds_up() {
171        assert_eq!(bitmap_len(0), 0);
172        assert_eq!(bitmap_len(1), 1);
173        assert_eq!(bitmap_len(8), 1);
174        assert_eq!(bitmap_len(9), 2);
175    }
176}
chronix_engine/segment/validity.rs

chronix_engine/segment/
validity.rs
