1use 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
40pub 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 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 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 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
219fn 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 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 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 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
271const BLOCK_BYTES: usize = 32;
273
274struct RunWriter<T> {
282 buffer: BufferMut<T>,
283 len: usize,
284 length: usize,
285}
286
287impl<T: Copy> RunWriter<T> {
288 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 #[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 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 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
363pub 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
396pub 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 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}