|
| 1 | +// SPDX-License-Identifier: Apache-2.0 |
| 2 | +// SPDX-FileCopyrightText: Copyright the Vortex contributors |
| 3 | + |
| 4 | +//! Express run-end decoding as a gather from the existing values child. |
| 5 | +//! |
| 6 | +//! Repeated run indices let the generic take machinery handle logical types without specialized |
| 7 | +//! run-end decoders. Piecewise codes keep that mapping compact until a consumer needs flat indices. |
| 8 | +
|
| 9 | +use vortex_buffer::BufferMut; |
| 10 | +use vortex_error::VortexResult; |
| 11 | + |
| 12 | +use crate::Canonical; |
| 13 | +use crate::ExecutionCtx; |
| 14 | +use crate::IntoArray; |
| 15 | +use crate::arrays::ConstantArray; |
| 16 | +use crate::arrays::DictArray; |
| 17 | +use crate::arrays::PiecewiseSequenceArray; |
| 18 | +use crate::arrays::PrimitiveArray; |
| 19 | +use crate::arrays::runend::RunEndArray; |
| 20 | +use crate::arrays::runend::RunEndArrayExt; |
| 21 | +use crate::arrays::runend::RunEndArraySlotsExt; |
| 22 | +use crate::arrays::runend::slice_relative_ends; |
| 23 | +use crate::dtype::Nullability; |
| 24 | +use crate::dtype::UnsignedPType; |
| 25 | +use crate::match_each_unsigned_integer_ptype; |
| 26 | + |
| 27 | +impl RunEndArray { |
| 28 | + /// Converts to a dictionary with the same logical dtype and slice. |
| 29 | + /// |
| 30 | + /// Non-empty arrays share the values child without executing it. Codes use one constant piece |
| 31 | + /// per overlapping run, so construction needs no expanded index buffer. Executing the resulting |
| 32 | + /// [`DictArray`] may still materialize those indices. Empty arrays retain no source children. |
| 33 | + pub fn to_dict(&self, ctx: &mut ExecutionCtx) -> VortexResult<DictArray> { |
| 34 | + if self.is_empty() { |
| 35 | + return DictArray::try_new( |
| 36 | + PrimitiveArray::empty::<u64>(Nullability::NonNullable).into_array(), |
| 37 | + Canonical::empty(self.dtype()).into_array(), |
| 38 | + ); |
| 39 | + } |
| 40 | + |
| 41 | + let ends = self.ends().clone().execute::<PrimitiveArray>(ctx)?; |
| 42 | + let codes = match_each_unsigned_integer_ptype!(ends.ptype(), |E| { |
| 43 | + run_indices(ends.as_slice::<E>(), self.offset(), self.len())? |
| 44 | + }); |
| 45 | + |
| 46 | + DictArray::try_new(codes.into_array(), self.values().clone()) |
| 47 | + } |
| 48 | +} |
| 49 | + |
| 50 | +/// Builds repeated physical value indices for a slice covered by validated run ends. |
| 51 | +fn run_indices<E: UnsignedPType>( |
| 52 | + ends: &[E], |
| 53 | + offset: usize, |
| 54 | + len: usize, |
| 55 | +) -> VortexResult<PiecewiseSequenceArray> { |
| 56 | + let mut starts = BufferMut::<u64>::with_capacity(ends.len()); |
| 57 | + let mut lengths = BufferMut::<u64>::with_capacity(ends.len()); |
| 58 | + let mut run_start = 0; |
| 59 | + |
| 60 | + for (index, run_end) in slice_relative_ends(ends, offset, len).enumerate() { |
| 61 | + let length = run_end - run_start; |
| 62 | + if length != 0 { |
| 63 | + starts.push(u64::try_from(index)?); |
| 64 | + lengths.push(u64::try_from(length)?); |
| 65 | + } |
| 66 | + run_start = run_end; |
| 67 | + |
| 68 | + if run_end == len { |
| 69 | + break; |
| 70 | + } |
| 71 | + } |
| 72 | + |
| 73 | + let multipliers = ConstantArray::new(0u64, starts.len()).into_array(); |
| 74 | + |
| 75 | + PiecewiseSequenceArray::try_new( |
| 76 | + starts.freeze().into_array(), |
| 77 | + lengths.freeze().into_array(), |
| 78 | + multipliers, |
| 79 | + len, |
| 80 | + ) |
| 81 | +} |
| 82 | + |
| 83 | +#[cfg(test)] |
| 84 | +mod tests { |
| 85 | + use rstest::rstest; |
| 86 | + use vortex_buffer::buffer; |
| 87 | + use vortex_error::VortexResult; |
| 88 | + |
| 89 | + use crate::ArrayRef; |
| 90 | + use crate::ExecutionCtx; |
| 91 | + use crate::IntoArray; |
| 92 | + use crate::VortexSessionExecute; |
| 93 | + use crate::arrays::ExtensionArray; |
| 94 | + use crate::arrays::FixedSizeListArray; |
| 95 | + use crate::arrays::PiecewiseSequence; |
| 96 | + use crate::arrays::PrimitiveArray; |
| 97 | + use crate::arrays::StructArray; |
| 98 | + use crate::arrays::dict::DictArraySlotsExt; |
| 99 | + use crate::arrays::piecewise_sequence::array::PiecewiseSequenceArraySlotsExt; |
| 100 | + use crate::arrays::runend::RunEnd; |
| 101 | + use crate::arrays::runend::RunEndArray; |
| 102 | + use crate::arrays::runend::RunEndArraySlotsExt; |
| 103 | + use crate::arrays::runend::tests::SESSION; |
| 104 | + use crate::assert_arrays_eq; |
| 105 | + use crate::builtins::ArrayBuiltins; |
| 106 | + use crate::dtype::DType; |
| 107 | + use crate::dtype::Nullability; |
| 108 | + use crate::dtype::PType; |
| 109 | + use crate::extension::datetime::TimeUnit; |
| 110 | + use crate::extension::datetime::Timestamp; |
| 111 | + use crate::scalar::Scalar; |
| 112 | + |
| 113 | + #[track_caller] |
| 114 | + fn check_conversion( |
| 115 | + array: &RunEndArray, |
| 116 | + expected: ArrayRef, |
| 117 | + ctx: &mut ExecutionCtx, |
| 118 | + ) -> VortexResult<()> { |
| 119 | + let dict = array.to_dict(ctx)?; |
| 120 | + |
| 121 | + if array.is_empty() { |
| 122 | + assert!(dict.codes().is_empty()); |
| 123 | + assert!(dict.values().is_empty()); |
| 124 | + } else { |
| 125 | + assert!(ArrayRef::ptr_eq(dict.values(), array.values())); |
| 126 | + let codes = dict.codes().as_::<PiecewiseSequence>(); |
| 127 | + assert_eq!(codes.multipliers().as_constant(), Some(&Scalar::from(0u64))); |
| 128 | + } |
| 129 | + |
| 130 | + assert_arrays_eq!(dict.into_array(), expected, ctx); |
| 131 | + |
| 132 | + Ok(()) |
| 133 | + } |
| 134 | + |
| 135 | + fn struct_values(storage: ArrayRef) -> VortexResult<ArrayRef> { |
| 136 | + Ok(StructArray::from_fields(&[("value", storage)])?.into_array()) |
| 137 | + } |
| 138 | + |
| 139 | + fn fixed_size_list_values(storage: ArrayRef) -> VortexResult<ArrayRef> { |
| 140 | + Ok( |
| 141 | + FixedSizeListArray::try_new(storage.clone(), 1, storage.validity()?, storage.len())? |
| 142 | + .into_array(), |
| 143 | + ) |
| 144 | + } |
| 145 | + |
| 146 | + fn timestamp_values(storage: ArrayRef) -> VortexResult<ArrayRef> { |
| 147 | + let ext_dtype = Timestamp::try_new_with_tz( |
| 148 | + TimeUnit::Microseconds, |
| 149 | + Some("UTC".into()), |
| 150 | + storage.dtype().nullability(), |
| 151 | + )?; |
| 152 | + |
| 153 | + Ok(ExtensionArray::try_new(ext_dtype.erased(), storage)?.into_array()) |
| 154 | + } |
| 155 | + |
| 156 | + #[rstest] |
| 157 | + #[case::full(PType::U32, 0, 8)] |
| 158 | + #[case::clipped_u8(PType::U8, 2, 5)] |
| 159 | + #[case::clipped_u16(PType::U16, 2, 5)] |
| 160 | + #[case::clipped_u32(PType::U32, 2, 5)] |
| 161 | + #[case::clipped_u64(PType::U64, 2, 5)] |
| 162 | + #[case::run_boundary(PType::U32, 3, 2)] |
| 163 | + #[case::single_row(PType::U32, 1, 1)] |
| 164 | + #[case::empty_retained_runs(PType::U32, 8, 0)] |
| 165 | + fn sliced_conversion( |
| 166 | + #[case] ends_type: PType, |
| 167 | + #[case] offset: usize, |
| 168 | + #[case] len: usize, |
| 169 | + ) -> VortexResult<()> { |
| 170 | + let mut ctx = SESSION.create_execution_ctx(); |
| 171 | + let ends = buffer![3u64, 5, 8] |
| 172 | + .into_array() |
| 173 | + .cast(DType::Primitive(ends_type, Nullability::NonNullable))?; |
| 174 | + let values = PrimitiveArray::from_option_iter([Some(10i64), None, Some(30)]).into_array(); |
| 175 | + let array = RunEnd::try_new_offset_length(ends, values, offset, len, &mut ctx)?; |
| 176 | + let expanded = [ |
| 177 | + Some(10i64), |
| 178 | + Some(10), |
| 179 | + Some(10), // First run. |
| 180 | + None, |
| 181 | + None, // Null run. |
| 182 | + Some(30), |
| 183 | + Some(30), |
| 184 | + Some(30), // Last run. |
| 185 | + ]; |
| 186 | + let expected = |
| 187 | + PrimitiveArray::from_option_iter(expanded[offset..offset + len].iter().copied()); |
| 188 | + |
| 189 | + check_conversion(&array, expected.into_array(), &mut ctx) |
| 190 | + } |
| 191 | + |
| 192 | + #[test] |
| 193 | + fn codes_retain_only_overlapping_runs() -> VortexResult<()> { |
| 194 | + let mut ctx = SESSION.create_execution_ctx(); |
| 195 | + let array = RunEnd::try_new_offset_length( |
| 196 | + buffer![3u32, 5, 8].into_array(), |
| 197 | + buffer![10i64, 20, 30].into_array(), |
| 198 | + 3, |
| 199 | + 4, |
| 200 | + &mut ctx, |
| 201 | + )?; |
| 202 | + let dict = array.to_dict(&mut ctx)?; |
| 203 | + let codes = dict.codes().as_::<PiecewiseSequence>(); |
| 204 | + |
| 205 | + assert_arrays_eq!(codes.starts(), buffer![1u64, 2].into_array(), &mut ctx); |
| 206 | + assert_arrays_eq!(codes.lengths(), buffer![2u64, 2].into_array(), &mut ctx); |
| 207 | + |
| 208 | + assert_arrays_eq!( |
| 209 | + dict.into_array(), |
| 210 | + buffer![20i64, 20, 30, 30].into_array(), |
| 211 | + &mut ctx |
| 212 | + ); |
| 213 | + |
| 214 | + Ok(()) |
| 215 | + } |
| 216 | + |
| 217 | + #[test] |
| 218 | + fn empty_conversion() -> VortexResult<()> { |
| 219 | + let mut ctx = SESSION.create_execution_ctx(); |
| 220 | + let values = PrimitiveArray::empty::<i64>(Nullability::Nullable).into_array(); |
| 221 | + let array = RunEnd::try_new( |
| 222 | + PrimitiveArray::empty::<u64>(Nullability::NonNullable).into_array(), |
| 223 | + values.clone(), |
| 224 | + &mut ctx, |
| 225 | + )?; |
| 226 | + |
| 227 | + check_conversion(&array, values, &mut ctx) |
| 228 | + } |
| 229 | + |
| 230 | + #[test] |
| 231 | + fn repeated_slicing() -> VortexResult<()> { |
| 232 | + let mut ctx = SESSION.create_execution_ctx(); |
| 233 | + let array = RunEnd::try_new( |
| 234 | + buffer![3u32, 5, 8].into_array(), |
| 235 | + PrimitiveArray::from_option_iter([Some(10i64), None, Some(30)]).into_array(), |
| 236 | + &mut ctx, |
| 237 | + )?; |
| 238 | + let sliced = array.slice(2..8)?.execute_until::<RunEnd>(&mut ctx)?; |
| 239 | + let sliced = sliced |
| 240 | + .slice(1..5)? |
| 241 | + .execute_until::<RunEnd>(&mut ctx)? |
| 242 | + .downcast::<RunEnd>(); |
| 243 | + let expected = PrimitiveArray::from_option_iter([None, None, Some(30i64), Some(30)]); |
| 244 | + |
| 245 | + check_conversion(&sliced, expected.into_array(), &mut ctx) |
| 246 | + } |
| 247 | + |
| 248 | + #[rstest] |
| 249 | + #[case::structure(struct_values)] |
| 250 | + #[case::fixed_size_list(fixed_size_list_values)] |
| 251 | + #[case::extension(timestamp_values)] |
| 252 | + fn fallback_preserves_dtype( |
| 253 | + #[case] wrap: fn(ArrayRef) -> VortexResult<ArrayRef>, |
| 254 | + #[values(false, true)] empty: bool, |
| 255 | + ) -> VortexResult<()> { |
| 256 | + let mut ctx = SESSION.create_execution_ctx(); |
| 257 | + let storage = PrimitiveArray::from_option_iter([Some(10i64), None, Some(30)]).into_array(); |
| 258 | + let values = wrap(storage)?; |
| 259 | + let len = if empty { 0 } else { 5 }; |
| 260 | + let expected = wrap( |
| 261 | + PrimitiveArray::from_option_iter( |
| 262 | + [Some(10i64), None, None, Some(30), Some(30)] |
| 263 | + .into_iter() |
| 264 | + .take(len), |
| 265 | + ) |
| 266 | + .into_array(), |
| 267 | + )?; |
| 268 | + let array = RunEnd::try_new_offset_length( |
| 269 | + buffer![3u32, 5, 8].into_array(), |
| 270 | + values, |
| 271 | + 2, |
| 272 | + len, |
| 273 | + &mut ctx, |
| 274 | + )?; |
| 275 | + |
| 276 | + check_conversion(&array, expected.clone(), &mut ctx)?; |
| 277 | + assert_arrays_eq!(array.into_array(), expected, &mut ctx); |
| 278 | + |
| 279 | + Ok(()) |
| 280 | + } |
| 281 | +} |
0 commit comments