Skip to main content

vortex_array/arrays/runend/
compress.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4use itertools::Itertools;
5use vortex_buffer::BitBuffer;
6use vortex_buffer::BitBufferMut;
7use vortex_buffer::Buffer;
8use vortex_buffer::BufferAllocatorRef;
9use vortex_buffer::BufferMut;
10use vortex_buffer::buffer;
11use vortex_error::VortexExpect;
12use vortex_error::VortexResult;
13use vortex_mask::Mask;
14
15use crate::ArrayRef;
16use crate::ArrayView;
17use crate::ExecutionCtx;
18use crate::IntoArray;
19use crate::arrays::BoolArray;
20use crate::arrays::ConstantArray;
21use crate::arrays::DecimalArray;
22use crate::arrays::Primitive;
23use crate::arrays::PrimitiveArray;
24use crate::arrays::VarBinViewArray;
25use crate::arrays::bool::BoolArrayExt;
26use crate::arrays::decimal::DecimalArrayExt;
27use crate::arrays::primitive::PrimitiveArrayExt;
28use crate::arrays::runend::iter::trimmed_ends_iter;
29use crate::buffer::BufferHandle;
30use crate::dtype::NativePType;
31use crate::dtype::Nullability;
32use crate::expr::stats::Precision;
33use crate::expr::stats::Stat;
34use crate::match_each_decimal_value_type;
35use crate::match_each_native_ptype;
36use crate::match_each_unsigned_integer_ptype;
37use crate::scalar::Scalar;
38use crate::validity::Validity;
39
40/// Run-end encode a `PrimitiveArray`, returning a tuple of `(ends, values)`.
41pub fn runend_encode(
42    array: ArrayView<Primitive>,
43    ctx: &mut ExecutionCtx,
44) -> (PrimitiveArray, ArrayRef) {
45    let validity = match array
46        .validity()
47        .vortex_expect("run-end validity should be derivable")
48    {
49        Validity::NonNullable => None,
50        Validity::AllValid => None,
51        Validity::AllInvalid => {
52            // We can trivially return an all-null REE array
53            let ends = PrimitiveArray::new(buffer![array.len() as u64], Validity::NonNullable);
54            ends.statistics()
55                .set(Stat::IsStrictSorted, Precision::Exact(true.into()));
56            return (
57                ends,
58                ConstantArray::new(Scalar::null(array.dtype().clone()), 1).into_array(),
59            );
60        }
61        Validity::Array(a) => {
62            let bool_array = a
63                .execute::<BoolArray>(ctx)
64                .vortex_expect("validity array must be convertible to bool");
65            Some(bool_array.to_bit_buffer())
66        }
67    };
68
69    let (ends, values) = match validity {
70        None => {
71            match_each_native_ptype!(array.ptype(), |P| {
72                let (ends, values) = runend_encode_primitive(array.as_slice::<P>());
73                (
74                    PrimitiveArray::new(ends, Validity::NonNullable),
75                    PrimitiveArray::new(values, array.dtype().nullability().into()).into_array(),
76                )
77            })
78        }
79        Some(validity) => {
80            match_each_native_ptype!(array.ptype(), |P| {
81                let (ends, values) =
82                    runend_encode_nullable_primitive(array.as_slice::<P>(), validity);
83                (
84                    PrimitiveArray::new(ends, Validity::NonNullable),
85                    values.into_array(),
86                )
87            })
88        }
89    };
90
91    let ends = ends
92        .narrow(ctx)
93        .vortex_expect("Ends must succeed downcasting");
94
95    ends.statistics()
96        .set(Stat::IsStrictSorted, Precision::Exact(true.into()));
97
98    (ends, values)
99}
100
101fn runend_encode_primitive<T: NativePType>(elements: &[T]) -> (Buffer<u64>, Buffer<T>) {
102    let mut ends = BufferMut::empty();
103    let mut values = BufferMut::empty();
104
105    if elements.is_empty() {
106        return (ends.freeze(), values.freeze());
107    }
108
109    // Run-end encode the values
110    let mut prev = elements[0];
111    let mut end = 1;
112    for &e in elements.iter().skip(1) {
113        if e != prev {
114            ends.push(end);
115            values.push(prev);
116        }
117        prev = e;
118        end += 1;
119    }
120    ends.push(end);
121    values.push(prev);
122
123    (ends.freeze(), values.freeze())
124}
125
126fn runend_encode_nullable_primitive<T: NativePType>(
127    elements: &[T],
128    element_validity: BitBuffer,
129) -> (Buffer<u64>, PrimitiveArray) {
130    let mut ends = BufferMut::empty();
131    let mut values = BufferMut::empty();
132    let mut validity = BitBufferMut::with_capacity(values.capacity());
133
134    if elements.is_empty() {
135        return (
136            ends.freeze(),
137            PrimitiveArray::new(
138                values,
139                Validity::Array(BoolArray::from(validity.freeze()).into_array()),
140            ),
141        );
142    }
143
144    // Run-end encode the values
145    let mut prev = element_validity.value(0).then(|| elements[0]);
146    let mut end = 1;
147    for e in elements
148        .iter()
149        .zip(element_validity.iter())
150        .map(|(&e, is_valid)| is_valid.then_some(e))
151        .skip(1)
152    {
153        if e != prev {
154            ends.push(end);
155            match prev {
156                None => {
157                    validity.append(false);
158                    values.push(T::default());
159                }
160                Some(p) => {
161                    validity.append(true);
162                    values.push(p);
163                }
164            }
165        }
166        prev = e;
167        end += 1;
168    }
169    ends.push(end);
170
171    match prev {
172        None => {
173            validity.append(false);
174            values.push(T::default());
175        }
176        Some(p) => {
177            validity.append(true);
178            values.push(p);
179        }
180    }
181
182    (
183        ends.freeze(),
184        PrimitiveArray::new(values, Validity::from(validity.freeze())),
185    )
186}
187
188pub fn runend_decode_primitive(
189    ends: PrimitiveArray,
190    values: PrimitiveArray,
191    offset: usize,
192    length: usize,
193    ctx: &mut ExecutionCtx,
194) -> VortexResult<ArrayRef> {
195    let validity_mask = values
196        .as_ref()
197        .validity()?
198        .execute_mask(values.as_ref().len(), ctx)?;
199    if matches!(validity_mask, Mask::AllFalse(_)) {
200        return Ok(
201            ConstantArray::new(Scalar::null(values.dtype().as_nullable()), length).into_array(),
202        );
203    }
204    Ok(match_each_native_ptype!(values.ptype(), |P| {
205        match_each_unsigned_integer_ptype!(ends.ptype(), |E| {
206            runend_decode_typed_primitive(
207                trimmed_ends_iter(ends.as_slice::<E>(), offset, length),
208                values.as_slice::<P>(),
209                validity_mask,
210                values.dtype().nullability(),
211                length,
212                ctx.allocator(),
213            )
214            .into_array()
215        })
216    }))
217}
218
219/// Decode a run-end encoded slice of values into a flat `Buffer<T>` and `Validity`.
220///
221/// This is the core decode loop shared by primitive and varbinview run-end decoding.
222fn runend_decode_slice<T: Copy + Default>(
223    run_ends: impl Iterator<Item = usize>,
224    values: &[T],
225    values_validity: Mask,
226    values_nullability: Nullability,
227    length: usize,
228    allocator: &BufferAllocatorRef,
229) -> (Buffer<T>, Validity) {
230    match values_validity {
231        Mask::AllTrue(_) => {
232            let mut decoded = RunWriter::new(length, allocator);
233            for (end, &value) in run_ends.zip_eq(values) {
234                decoded.write_run(value, end);
235            }
236            (decoded.finish(), values_nullability.into())
237        }
238        Mask::AllFalse(_) => (Buffer::<T>::zeroed(length), Validity::AllInvalid),
239        Mask::Values(mask) => {
240            // Nulls are usually rare and clustered, so start from all-valid and clear each
241            // maximal streak of null runs once, rather than appending validity per run.
242            let mut decoded = RunWriter::new(length, allocator);
243            let mut decoded_validity = BitBufferMut::full(true, length);
244            let mut null_start = None;
245            for (end, (&value, is_valid)) in
246                run_ends.zip_eq(values.iter().zip(mask.bit_buffer().iter()))
247            {
248                let start = decoded.len();
249                decoded.write_run(if is_valid { value } else { T::default() }, end);
250                match (is_valid, null_start) {
251                    (false, None) => null_start = Some(start),
252                    (true, Some(null_from)) => {
253                        // SAFETY: null_from <= start <= length == decoded_validity.len()
254                        unsafe { decoded_validity.fill_range_unchecked(null_from, start, false) };
255                        null_start = None;
256                    }
257                    _ => {}
258                }
259            }
260            let decoded = decoded.finish();
261            if let Some(null_from) = null_start {
262                // SAFETY: null_from <= decoded.len() <= length == decoded_validity.len()
263                unsafe { decoded_validity.fill_range_unchecked(null_from, decoded.len(), false) };
264            }
265            decoded_validity.truncate(decoded.len());
266            (decoded, Validity::from(decoded_validity.freeze()))
267        }
268    }
269}
270
271/// Minimum bytes in a [`RunWriter`] block.
272const BLOCK_BYTES: usize = 32;
273
274/// Writes runs of values into a buffer of up to `length` elements.
275///
276/// Runs are usually short, and filling each one with a loop sized to its length costs more than
277/// the fill itself. Instead a run that fits in a fixed block writes the whole block, which the
278/// compiler lowers to a few vector stores, and the next run overwrites whatever went past its
279/// end. Longer runs are filled exactly. The buffer has a block of spare capacity so that the last
280/// run's block stays in bounds.
281struct RunWriter<T> {
282    buffer: BufferMut<T>,
283    len: usize,
284    length: usize,
285}
286
287impl<T: Copy> RunWriter<T> {
288    /// Elements in a block: enough to cover most short runs, at least 8 elements and 32 bytes.
289    const BLOCK: usize = if size_of::<T>() == 0 || size_of::<T>() >= BLOCK_BYTES / 8 {
290        8
291    } else {
292        BLOCK_BYTES / size_of::<T>()
293    };
294
295    fn new(length: usize, allocator: &BufferAllocatorRef) -> Self {
296        Self {
297            buffer: BufferMut::with_capacity_in(length + Self::BLOCK, allocator.clone()),
298            len: 0,
299            length,
300        }
301    }
302
303    fn len(&self) -> usize {
304        self.len
305    }
306
307    /// Fill `self.len()..end` with `value`.
308    #[inline]
309    fn write_run(&mut self, value: T, end: usize) {
310        assert!(
311            end >= self.len,
312            "Runend ends must be monotonic, got {end} after {}",
313            self.len
314        );
315        assert!(
316            end <= self.length,
317            "Runend end must be less than overall length"
318        );
319        // SAFETY: `self.len <= end <= length`, and the buffer holds `length + BLOCK` elements, so
320        // both the block and the remainder of the run are in bounds.
321        unsafe {
322            let dst = self.buffer.as_mut_ptr().add(self.len);
323            let run_len = end - self.len;
324            if run_len <= Self::BLOCK {
325                for i in 0..Self::BLOCK {
326                    dst.add(i).write(value);
327                }
328            } else {
329                for i in 0..run_len {
330                    dst.add(i).write(value);
331                }
332            }
333        }
334        self.len = end;
335    }
336
337    fn finish(mut self) -> Buffer<T> {
338        // SAFETY: every element below `self.len` was written by a run.
339        unsafe { self.buffer.set_len(self.len) };
340        self.buffer.freeze()
341    }
342}
343
344pub fn runend_decode_typed_primitive<T: NativePType>(
345    run_ends: impl Iterator<Item = usize>,
346    values: &[T],
347    values_validity: Mask,
348    values_nullability: Nullability,
349    length: usize,
350    allocator: &BufferAllocatorRef,
351) -> PrimitiveArray {
352    let (decoded, validity) = runend_decode_slice(
353        run_ends,
354        values,
355        values_validity,
356        values_nullability,
357        length,
358        allocator,
359    );
360    PrimitiveArray::new(decoded, validity)
361}
362
363/// Decode a run-end encoded decimal array by expanding its native values.
364pub fn runend_decode_decimal(
365    ends: PrimitiveArray,
366    values: DecimalArray,
367    offset: usize,
368    length: usize,
369    ctx: &mut ExecutionCtx,
370) -> VortexResult<ArrayRef> {
371    let validity_mask = values
372        .as_ref()
373        .validity()?
374        .execute_mask(values.as_ref().len(), ctx)?;
375    if matches!(validity_mask, Mask::AllFalse(_)) {
376        return Ok(
377            ConstantArray::new(Scalar::null(values.dtype().as_nullable()), length).into_array(),
378        );
379    }
380
381    Ok(match_each_decimal_value_type!(values.values_type(), |D| {
382        let (decoded, validity) = match_each_unsigned_integer_ptype!(ends.ptype(), |E| {
383            runend_decode_slice(
384                trimmed_ends_iter(ends.as_slice::<E>(), offset, length),
385                values.buffer::<D>().as_slice(),
386                validity_mask,
387                values.dtype().nullability(),
388                length,
389                ctx.allocator(),
390            )
391        });
392        DecimalArray::new(decoded, values.decimal_dtype(), validity).into_array()
393    }))
394}
395
396/// Decode a run-end encoded VarBinView array by expanding views directly.
397pub fn runend_decode_varbinview(
398    ends: PrimitiveArray,
399    values: VarBinViewArray,
400    offset: usize,
401    length: usize,
402    ctx: &mut ExecutionCtx,
403) -> VortexResult<ArrayRef> {
404    let validity_mask = values
405        .as_ref()
406        .validity()?
407        .execute_mask(values.as_ref().len(), ctx)?;
408    if matches!(validity_mask, Mask::AllFalse(_)) {
409        return Ok(
410            ConstantArray::new(Scalar::null(values.dtype().as_nullable()), length).into_array(),
411        );
412    }
413    let views = values.views();
414
415    let (decoded_views, validity) = match_each_unsigned_integer_ptype!(ends.ptype(), |E| {
416        runend_decode_slice(
417            trimmed_ends_iter(ends.as_slice::<E>(), offset, length),
418            views,
419            validity_mask,
420            values.dtype().nullability(),
421            length,
422            ctx.allocator(),
423        )
424    });
425
426    let parts = values.into_data_parts();
427    let view_handle = BufferHandle::new_host(decoded_views.into_byte_buffer());
428
429    // SAFETY: we are expanding views from a valid VarBinViewArray with the same
430    // buffers, so all buffer indices and offsets remain valid.
431    Ok(unsafe {
432        VarBinViewArray::new_handle_unchecked(view_handle, parts.buffers, parts.dtype, validity)
433    }
434    .into_array())
435}
436
437#[cfg(test)]
438mod tests {
439    use std::sync::LazyLock;
440
441    use rstest::rstest;
442    use vortex_buffer::BitBuffer;
443    use vortex_buffer::buffer;
444    use vortex_error::VortexResult;
445    use vortex_session::VortexSession;
446
447    use crate::VortexSessionExecute;
448    use crate::arrays::PrimitiveArray;
449    use crate::arrays::runend::compress::runend_decode_primitive;
450    use crate::arrays::runend::compress::runend_encode;
451    use crate::assert_arrays_eq;
452    use crate::validity::Validity;
453
454    static SESSION: LazyLock<VortexSession> = LazyLock::new(VortexSession::empty);
455
456    #[test]
457    fn encode() -> VortexResult<()> {
458        let mut ctx = SESSION.create_execution_ctx();
459        let arr = PrimitiveArray::from_iter([1i32, 1, 2, 2, 2, 3, 3, 3, 3, 3]);
460        let (ends, values) = runend_encode(arr.as_view(), &mut ctx);
461
462        let expected_ends = PrimitiveArray::from_iter(vec![2u8, 5, 10]);
463        assert_arrays_eq!(ends, expected_ends, &mut ctx);
464        let expected_values = PrimitiveArray::from_iter(vec![1i32, 2, 3]);
465        assert_arrays_eq!(values, expected_values, &mut ctx);
466        Ok(())
467    }
468
469    #[test]
470    fn encode_nullable() -> VortexResult<()> {
471        let mut ctx = SESSION.create_execution_ctx();
472        let arr = PrimitiveArray::new(
473            buffer![1i32, 1, 2, 2, 2, 3, 3, 3, 3, 3],
474            Validity::from(BitBuffer::from(vec![
475                true, true, false, false, true, true, true, true, false, false,
476            ])),
477        );
478        let (ends, values) = runend_encode(arr.as_view(), &mut ctx);
479
480        let expected_ends = PrimitiveArray::from_iter(vec![2u8, 4, 5, 8, 10]);
481        assert_arrays_eq!(ends, expected_ends, &mut ctx);
482        let expected_values =
483            PrimitiveArray::from_option_iter(vec![Some(1i32), None, Some(2), Some(3), None]);
484        assert_arrays_eq!(values, expected_values, &mut ctx);
485        Ok(())
486    }
487
488    #[test]
489    fn encode_all_null() -> VortexResult<()> {
490        let mut ctx = SESSION.create_execution_ctx();
491        let arr = PrimitiveArray::new(
492            buffer![0, 0, 0, 0, 0],
493            Validity::from(BitBuffer::new_unset(5)),
494        );
495        let (ends, values) = runend_encode(arr.as_view(), &mut ctx);
496
497        let expected_ends = PrimitiveArray::from_iter(vec![5u64]);
498        assert_arrays_eq!(ends, expected_ends, &mut ctx);
499        let expected_values = PrimitiveArray::from_option_iter(vec![Option::<i32>::None]);
500        assert_arrays_eq!(values, expected_values, &mut ctx);
501        Ok(())
502    }
503
504    #[test]
505    fn decode() -> VortexResult<()> {
506        let mut ctx = SESSION.create_execution_ctx();
507        let ends = PrimitiveArray::from_iter([2u32, 5, 10]);
508        let values = PrimitiveArray::from_iter([1i32, 2, 3]);
509        let decoded = runend_decode_primitive(ends, values, 0, 10, &mut ctx)?;
510
511        let expected = PrimitiveArray::from_iter(vec![1i32, 1, 2, 2, 2, 3, 3, 3, 3, 3]);
512        assert_arrays_eq!(decoded, expected, &mut ctx);
513        Ok(())
514    }
515
516    #[rstest]
517    #[case::middle_nulls(&[Some(1), None, None, Some(2)], 0, 10)]
518    #[case::leading_and_trailing_nulls(&[None, Some(1), Some(2), None], 0, 10)]
519    #[case::all_null(&[None, None, None, None], 0, 10)]
520    #[case::offset_and_trailing_null(&[None, Some(1), Some(2), None], 1, 8)]
521    fn decode_nullable(
522        #[case] values: &[Option<i32>],
523        #[case] offset: usize,
524        #[case] length: usize,
525    ) -> VortexResult<()> {
526        let mut ctx = SESSION.create_execution_ctx();
527        let ends = [2u32, 5, 7, 10];
528        let expected = PrimitiveArray::from_option_iter(
529            (offset..offset + length)
530                .map(|row| values[ends.iter().position(|&end| row < end as usize).unwrap_or(0)]),
531        );
532        let decoded = runend_decode_primitive(
533            PrimitiveArray::from_iter(ends),
534            PrimitiveArray::from_option_iter(values.iter().copied()),
535            offset,
536            length,
537            &mut ctx,
538        )?;
539        assert_arrays_eq!(decoded, expected, &mut ctx);
540        Ok(())
541    }
542}