Skip to main content

vortex_array/arrays/runend/
decompress_bool.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4//! Optimized run-end decoding for boolean arrays.
5//!
6//! Uses an adaptive strategy that pre-fills the buffer with the majority value
7//! (0s or 1s) and only fills the minority runs, minimizing work for skewed distributions.
8
9use vortex_buffer::BitBuffer;
10use vortex_buffer::BitBufferMut;
11use vortex_error::VortexResult;
12use vortex_mask::Mask;
13
14use crate::ArrayRef;
15use crate::ExecutionCtx;
16use crate::IntoArray;
17use crate::arrays::BoolArray;
18use crate::arrays::ConstantArray;
19use crate::arrays::PrimitiveArray;
20use crate::arrays::bool::BoolArrayExt;
21use crate::arrays::runend::iter::trimmed_ends_iter;
22use crate::dtype::DType;
23use crate::dtype::Nullability;
24use crate::match_each_unsigned_integer_ptype;
25use crate::scalar::Scalar;
26use crate::validity::Validity;
27
28/// Threshold for number of runs below which we use sequential append instead of prefill.
29/// With few runs, the overhead of prefilling the entire buffer dominates.
30const PREFILL_RUN_THRESHOLD: usize = 32;
31
32/// Decodes run-end encoded boolean values into a flat `BoolArray`.
33///
34/// # Panics
35///
36/// Panics if `ends` and `values` have different lengths.
37pub fn runend_decode_bools(
38    ends: PrimitiveArray,
39    values: BoolArray,
40    offset: usize,
41    length: usize,
42    ctx: &mut ExecutionCtx,
43) -> VortexResult<ArrayRef> {
44    // NB: The decode loops pair run ends with values through `zip`, which stops at the shorter
45    // input, so this check must stay. Do not switch the loops to `itertools::zip_eq`: `ZipEq::next`
46    // has no `#[inline]`, so rustc can place it in another codegen unit, and the loop then calls it
47    // out of line once per run.
48    assert_eq!(
49        ends.len(),
50        values.len(),
51        "run ends and values must have the same length"
52    );
53
54    let validity = values
55        .as_ref()
56        .validity()?
57        .execute_mask(values.as_ref().len(), ctx)?;
58    let values_buf = values.to_bit_buffer();
59    let nullability = values.dtype().nullability();
60
61    // Fast path for few runs with no offset - avoids iterator overhead
62    let num_runs = values_buf.len();
63    if offset == 0 && num_runs < PREFILL_RUN_THRESHOLD {
64        return Ok(match_each_unsigned_integer_ptype!(ends.ptype(), |E| {
65            decode_few_runs_no_offset(
66                ends.as_slice::<E>(),
67                &values_buf,
68                validity,
69                nullability,
70                length,
71            )
72        }));
73    }
74
75    Ok(match_each_unsigned_integer_ptype!(ends.ptype(), |E| {
76        runend_decode_typed_bool(
77            trimmed_ends_iter(ends.as_slice::<E>(), offset, length),
78            &values_buf,
79            validity,
80            nullability,
81            length,
82        )
83    }))
84}
85
86/// Decodes run-end encoded boolean values using an adaptive strategy.
87///
88/// The strategy counts true vs false runs and chooses the optimal approach:
89/// - If more true runs: pre-fill with 1s, clear false runs
90/// - If more false runs: pre-fill with 0s, fill true runs
91///
92/// This minimizes work for skewed distributions (e.g., sparse validity masks).
93pub fn runend_decode_typed_bool(
94    run_ends: impl Iterator<Item = usize>,
95    values: &BitBuffer,
96    values_validity: Mask,
97    values_nullability: Nullability,
98    length: usize,
99) -> ArrayRef {
100    match values_validity {
101        Mask::AllTrue(_) => {
102            decode_bool_non_nullable(run_ends, values, values_nullability, length).into_array()
103        }
104        Mask::AllFalse(_) => {
105            ConstantArray::new(Scalar::null(DType::Bool(Nullability::Nullable)), length)
106                .into_array()
107        }
108        Mask::Values(mask) => {
109            decode_bool_nullable(run_ends, values, mask.bit_buffer(), length).into_array()
110        }
111    }
112}
113
114/// Fast path for few runs with no offset. Uses direct slice access to minimize overhead.
115/// This avoids the `trimmed_ends_iter` iterator chain which adds significant overhead
116/// for small numbers of runs.
117#[allow(clippy::inline_always)]
118#[inline(always)]
119fn decode_few_runs_no_offset<E: crate::dtype::IntegerPType>(
120    ends: &[E],
121    values: &BitBuffer,
122    validity: Mask,
123    nullability: Nullability,
124    length: usize,
125) -> ArrayRef {
126    match validity {
127        Mask::AllTrue(_) => {
128            let mut decoded = BitBufferMut::with_capacity(length);
129            let mut prev_end = 0usize;
130            for (i, &end) in ends.iter().enumerate() {
131                let end = end.as_().min(length);
132                decoded.append_n(values.value(i), end - prev_end);
133                prev_end = end;
134            }
135            BoolArray::new(decoded.freeze(), nullability.into()).into_array()
136        }
137        Mask::AllFalse(_) => {
138            ConstantArray::new(Scalar::null(DType::Bool(Nullability::Nullable)), length)
139                .into_array()
140        }
141        Mask::Values(mask) => {
142            let validity_buf = mask.bit_buffer();
143            let mut decoded = BitBufferMut::with_capacity(length);
144            let mut decoded_validity = BitBufferMut::with_capacity(length);
145            let mut prev_end = 0usize;
146            for (i, &end) in ends.iter().enumerate() {
147                let end = end.as_().min(length);
148                let run_len = end - prev_end;
149                let is_valid = validity_buf.value(i);
150                if is_valid {
151                    decoded_validity.append_n(true, run_len);
152                    decoded.append_n(values.value(i), run_len);
153                } else {
154                    decoded_validity.append_n(false, run_len);
155                    decoded.append_n(false, run_len);
156                }
157                prev_end = end;
158            }
159            BoolArray::new(decoded.freeze(), Validity::from(decoded_validity.freeze())).into_array()
160        }
161    }
162}
163
164/// Decodes run-end encoded booleans when all values are valid (non-nullable).
165fn decode_bool_non_nullable(
166    run_ends: impl Iterator<Item = usize>,
167    values: &BitBuffer,
168    nullability: Nullability,
169    length: usize,
170) -> BoolArray {
171    let num_runs = values.len();
172
173    // For few runs, sequential append is faster than prefill + modify
174    if num_runs < PREFILL_RUN_THRESHOLD {
175        let mut decoded = BitBufferMut::with_capacity(length);
176        for (end, value) in run_ends.zip(values.iter()) {
177            decoded.append_n(value, end - decoded.len());
178        }
179        return BoolArray::new(decoded.freeze(), nullability.into());
180    }
181
182    // Adaptive strategy: prefill with majority value, only flip minority runs
183    let prefill = values.true_count() > num_runs - values.true_count();
184    let mut decoded = BitBufferMut::full(prefill, length);
185    let mut current_pos = 0usize;
186
187    for (end, value) in run_ends.zip(values.iter()) {
188        if end > current_pos && value != prefill {
189            // SAFETY: current_pos < end <= length == decoded.len()
190            unsafe { decoded.fill_range_unchecked(current_pos, end, value) };
191        }
192        current_pos = end;
193    }
194    BoolArray::new(decoded.freeze(), nullability.into())
195}
196
197/// Decodes run-end encoded booleans when values may be null (nullable).
198fn decode_bool_nullable(
199    run_ends: impl Iterator<Item = usize>,
200    values: &BitBuffer,
201    validity_mask: &BitBuffer,
202    length: usize,
203) -> BoolArray {
204    let num_runs = values.len();
205
206    // For few runs, sequential append is faster than prefill + modify
207    if num_runs < PREFILL_RUN_THRESHOLD {
208        return decode_nullable_sequential(run_ends, values, validity_mask, length);
209    }
210
211    // Adaptive strategy: prefill each buffer with its majority value
212    let prefill_decoded = values.true_count() > num_runs - values.true_count();
213    let prefill_valid = validity_mask.true_count() > num_runs - validity_mask.true_count();
214
215    let mut decoded = BitBufferMut::full(prefill_decoded, length);
216    let mut decoded_validity = BitBufferMut::full(prefill_valid, length);
217    let mut current_pos = 0usize;
218
219    for (end, (value, is_valid)) in run_ends.zip(values.iter().zip(validity_mask.iter())) {
220        if end > current_pos {
221            // SAFETY: current_pos < end <= length == decoded.len() == decoded_validity.len()
222            if is_valid != prefill_valid {
223                unsafe { decoded_validity.fill_range_unchecked(current_pos, end, is_valid) };
224            }
225            // Decoded bit should be the actual value when valid, false when null.
226            let want_decoded = is_valid && value;
227            if want_decoded != prefill_decoded {
228                unsafe { decoded.fill_range_unchecked(current_pos, end, want_decoded) };
229            }
230            current_pos = end;
231        }
232    }
233    BoolArray::new(decoded.freeze(), Validity::from(decoded_validity.freeze()))
234}
235
236/// Sequential decode for few runs - avoids prefill overhead.
237#[allow(clippy::inline_always)]
238#[inline(always)]
239fn decode_nullable_sequential(
240    run_ends: impl Iterator<Item = usize>,
241    values: &BitBuffer,
242    validity_mask: &BitBuffer,
243    length: usize,
244) -> BoolArray {
245    let mut decoded = BitBufferMut::with_capacity(length);
246    let mut decoded_validity = BitBufferMut::with_capacity(length);
247
248    for (end, (value, is_valid)) in run_ends.zip(values.iter().zip(validity_mask.iter())) {
249        let run_len = end - decoded.len();
250        if is_valid {
251            decoded_validity.append_n(true, run_len);
252            decoded.append_n(value, run_len);
253        } else {
254            decoded_validity.append_n(false, run_len);
255            decoded.append_n(false, run_len);
256        }
257    }
258
259    BoolArray::new(decoded.freeze(), Validity::from(decoded_validity.freeze()))
260}
261
262#[cfg(test)]
263mod tests {
264    use std::sync::LazyLock;
265
266    use vortex_buffer::BitBuffer;
267    use vortex_error::VortexResult;
268    use vortex_session::VortexSession;
269
270    use super::runend_decode_bools;
271    use crate::VortexSessionExecute;
272    use crate::arrays::BoolArray;
273    use crate::arrays::PrimitiveArray;
274    use crate::assert_arrays_eq;
275    use crate::validity::Validity;
276
277    static SESSION: LazyLock<VortexSession> = LazyLock::new(VortexSession::empty);
278
279    #[test]
280    fn decode_bools_alternating() -> VortexResult<()> {
281        let mut ctx = SESSION.create_execution_ctx();
282        // Alternating true/false: [T, T, F, F, F, T, T, T, T, T]
283        let ends = PrimitiveArray::from_iter([2u32, 5, 10]);
284        let values = BoolArray::from(BitBuffer::from(vec![true, false, true]));
285        let decoded = runend_decode_bools(ends, values, 0, 10, &mut ctx)?;
286
287        let expected = BoolArray::from(BitBuffer::from(vec![
288            true, true, false, false, false, true, true, true, true, true,
289        ]));
290        assert_arrays_eq!(decoded, expected, &mut ctx);
291        Ok(())
292    }
293
294    #[test]
295    fn decode_bools_mostly_true() -> VortexResult<()> {
296        let mut ctx = SESSION.create_execution_ctx();
297        // Mostly true: [T, T, T, T, T, F, T, T, T, T]
298        let ends = PrimitiveArray::from_iter([5u32, 6, 10]);
299        let values = BoolArray::from(BitBuffer::from(vec![true, false, true]));
300        let decoded = runend_decode_bools(ends, values, 0, 10, &mut ctx)?;
301
302        let expected = BoolArray::from(BitBuffer::from(vec![
303            true, true, true, true, true, false, true, true, true, true,
304        ]));
305        assert_arrays_eq!(decoded, expected, &mut ctx);
306        Ok(())
307    }
308
309    #[test]
310    fn decode_bools_mostly_false() -> VortexResult<()> {
311        let mut ctx = SESSION.create_execution_ctx();
312        // Mostly false: [F, F, F, F, F, T, F, F, F, F]
313        let ends = PrimitiveArray::from_iter([5u32, 6, 10]);
314        let values = BoolArray::from(BitBuffer::from(vec![false, true, false]));
315        let decoded = runend_decode_bools(ends, values, 0, 10, &mut ctx)?;
316
317        let expected = BoolArray::from(BitBuffer::from(vec![
318            false, false, false, false, false, true, false, false, false, false,
319        ]));
320        assert_arrays_eq!(decoded, expected, &mut ctx);
321        Ok(())
322    }
323
324    #[test]
325    fn decode_bools_all_true_single_run() -> VortexResult<()> {
326        let mut ctx = SESSION.create_execution_ctx();
327        let ends = PrimitiveArray::from_iter([10u32]);
328        let values = BoolArray::from(BitBuffer::from(vec![true]));
329        let decoded = runend_decode_bools(ends, values, 0, 10, &mut ctx)?;
330
331        let expected = BoolArray::from(BitBuffer::from(vec![
332            true, true, true, true, true, true, true, true, true, true,
333        ]));
334        assert_arrays_eq!(decoded, expected, &mut ctx);
335        Ok(())
336    }
337
338    #[test]
339    fn decode_bools_all_false_single_run() -> VortexResult<()> {
340        let mut ctx = SESSION.create_execution_ctx();
341        let ends = PrimitiveArray::from_iter([10u32]);
342        let values = BoolArray::from(BitBuffer::from(vec![false]));
343        let decoded = runend_decode_bools(ends, values, 0, 10, &mut ctx)?;
344
345        let expected = BoolArray::from(BitBuffer::from(vec![
346            false, false, false, false, false, false, false, false, false, false,
347        ]));
348        assert_arrays_eq!(decoded, expected, &mut ctx);
349        Ok(())
350    }
351
352    #[test]
353    fn decode_bools_with_offset() -> VortexResult<()> {
354        let mut ctx = SESSION.create_execution_ctx();
355        // Test with offset: [T, T, F, F, F, T, T, T, T, T] -> slice [2..8] = [F, F, F, T, T, T]
356        let ends = PrimitiveArray::from_iter([2u32, 5, 10]);
357        let values = BoolArray::from(BitBuffer::from(vec![true, false, true]));
358        let decoded = runend_decode_bools(ends, values, 2, 6, &mut ctx)?;
359
360        let expected =
361            BoolArray::from(BitBuffer::from(vec![false, false, false, true, true, true]));
362        assert_arrays_eq!(decoded, expected, &mut ctx);
363        Ok(())
364    }
365
366    #[test]
367    fn decode_bools_nullable() -> VortexResult<()> {
368        use crate::validity::Validity;
369
370        let mut ctx = SESSION.create_execution_ctx();
371        // 3 runs: T (valid), F (null), T (valid) -> [T, T, null, null, null, T, T, T, T, T]
372        let ends = PrimitiveArray::from_iter([2u32, 5, 10]);
373        let values = BoolArray::new(
374            BitBuffer::from(vec![true, false, true]),
375            Validity::from(BitBuffer::from(vec![true, false, true])),
376        );
377        let decoded = runend_decode_bools(ends, values, 0, 10, &mut ctx)?;
378
379        // Expected: values=[T, T, F, F, F, T, T, T, T, T], validity=[1, 1, 0, 0, 0, 1, 1, 1, 1, 1]
380        let expected = BoolArray::new(
381            BitBuffer::from(vec![
382                true, true, false, false, false, true, true, true, true, true,
383            ]),
384            Validity::from(BitBuffer::from(vec![
385                true, true, false, false, false, true, true, true, true, true,
386            ])),
387        );
388        assert_arrays_eq!(decoded, expected, &mut ctx);
389        Ok(())
390    }
391
392    #[test]
393    fn decode_bools_nullable_few_runs() -> VortexResult<()> {
394        let mut ctx = SESSION.create_execution_ctx();
395        // Test few runs (uses fast path): 5 runs of length 2000 each
396        let ends = PrimitiveArray::from_iter([2000u32, 4000, 6000, 8000, 10000]);
397        let values = BoolArray::new(
398            BitBuffer::from(vec![true, false, true, false, true]),
399            Validity::from(BitBuffer::from(vec![true, false, true, false, true])),
400        );
401        let decoded = runend_decode_bools(ends, values, 0, 10000, &mut ctx)?;
402
403        let expected =
404            BoolArray::from_iter((0..10000).map(|i| ((i / 2000) % 2 == 0).then_some(true)));
405        assert_arrays_eq!(decoded, expected, &mut ctx);
406        Ok(())
407    }
408}