Skip to main content

vortex_array/arrays/dict/vtable/
mod.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4use std::hash::Hasher;
5
6use num_traits::AsPrimitive;
7use prost::Message;
8use smallvec::smallvec;
9use vortex_error::VortexResult;
10use vortex_error::vortex_bail;
11use vortex_error::vortex_ensure_eq;
12use vortex_error::vortex_err;
13use vortex_error::vortex_panic;
14use vortex_mask::AllOr;
15use vortex_mask::Mask;
16use vortex_session::VortexSession;
17use vortex_session::registry::CachedId;
18
19use super::DictData;
20use super::DictMetadata;
21use super::DictOwnedExt;
22use super::DictParts;
23use super::array::DictSlots;
24use super::array::DictSlotsView;
25use crate::AnyCanonical;
26use crate::ArrayEq;
27use crate::ArrayHash;
28use crate::ArrayRef;
29use crate::Canonical;
30use crate::CanonicalView;
31use crate::EqMode;
32use crate::IntoArray;
33use crate::array::Array;
34use crate::array::ArrayId;
35use crate::array::ArrayParts;
36use crate::array::ArrayView;
37use crate::array::VTable;
38use crate::array::with_empty_buffers;
39use crate::arrays::ConstantArray;
40use crate::arrays::Primitive;
41use crate::arrays::PrimitiveArray;
42use crate::arrays::VarBinView;
43use crate::arrays::dict::DictArrayExt;
44use crate::arrays::dict::DictArraySlotsExt;
45use crate::arrays::dict::compute::rules::PARENT_RULES;
46use crate::arrays::dict::execute::take_canonical;
47use crate::buffer::BufferHandle;
48use crate::builders::ArrayBuilder;
49use crate::builders::VarBinBuilder;
50use crate::builders::VarBinViewBuilder;
51use crate::dtype::DType;
52use crate::dtype::Nullability;
53use crate::dtype::OffsetBuilderPType;
54use crate::dtype::PType;
55use crate::executor::ExecutionCtx;
56use crate::executor::ExecutionResult;
57use crate::match_each_integer_ptype;
58use crate::match_each_varbin_builder;
59use crate::require_child;
60use crate::scalar::Scalar;
61use crate::serde::ArrayChildren;
62
63mod kernel;
64mod operations;
65mod validity;
66
67/// A [`Dict`]-encoded Vortex array.
68pub type DictArray = Array<Dict>;
69
70pub(crate) fn initialize(session: &VortexSession) {
71    kernel::initialize(session);
72}
73
74#[derive(Clone, Debug)]
75pub struct Dict;
76
77impl ArrayHash for DictData {
78    fn array_hash<H: Hasher>(&self, _state: &mut H, _accuracy: EqMode) {}
79}
80
81impl ArrayEq for DictData {
82    fn array_eq(&self, _other: &Self, _accuracy: EqMode) -> bool {
83        true
84    }
85}
86
87impl VTable for Dict {
88    type TypedArrayData = DictData;
89
90    type OperationsVTable = Self;
91    type ValidityVTable = Self;
92
93    fn id(&self) -> ArrayId {
94        static ID: CachedId = CachedId::new("vortex.dict");
95        *ID
96    }
97
98    fn validate(
99        &self,
100        _data: &DictData,
101        dtype: &DType,
102        len: usize,
103        slots: &[Option<ArrayRef>],
104    ) -> VortexResult<()> {
105        let view = DictSlotsView::from_slots(slots);
106        let codes = view.codes;
107        let values = view.values;
108        vortex_ensure_eq!(codes.len(), len, "DictArray codes length mismatch");
109        vortex_ensure_eq!(
110            values
111                .dtype()
112                .union_nullability(codes.dtype().nullability()),
113            *dtype,
114            "DictArray dtype does not match codes/values dtype",
115        );
116        Ok(())
117    }
118
119    fn nbuffers(_array: ArrayView<'_, Self>) -> usize {
120        0
121    }
122
123    fn buffer(_array: ArrayView<'_, Self>, idx: usize) -> BufferHandle {
124        vortex_panic!("DictArray buffer index {idx} out of bounds")
125    }
126
127    fn buffer_name(_array: ArrayView<'_, Self>, _idx: usize) -> Option<String> {
128        None
129    }
130
131    fn with_buffers(
132        &self,
133        array: ArrayView<'_, Self>,
134        buffers: &[BufferHandle],
135    ) -> VortexResult<ArrayParts<Self>> {
136        with_empty_buffers(self, array, buffers)
137    }
138
139    fn serialize(
140        array: ArrayView<'_, Self>,
141        _session: &VortexSession,
142    ) -> VortexResult<Option<Vec<u8>>> {
143        Ok(Some(
144            DictMetadata {
145                codes_ptype: PType::try_from(array.codes().dtype())? as i32,
146                values_len: u32::try_from(array.values().len()).map_err(|_| {
147                    vortex_err!(
148                        "Dictionary values size {} overflowed u32",
149                        array.values().len()
150                    )
151                })?,
152                is_nullable_codes: Some(array.codes().dtype().is_nullable()),
153                all_values_referenced: Some(array.has_all_values_referenced()),
154            }
155            .encode_to_vec(),
156        ))
157    }
158
159    fn deserialize(
160        &self,
161        dtype: &DType,
162        len: usize,
163        metadata: &[u8],
164        _buffers: &[BufferHandle],
165        children: &dyn ArrayChildren,
166        _session: &VortexSession,
167    ) -> VortexResult<ArrayParts<Self>> {
168        let metadata = DictMetadata::decode(metadata)?;
169        let codes_ptype = metadata.get_codes_ptype()?;
170        if children.len() != 2 {
171            vortex_bail!(
172                "Expected 2 children for dict encoding, found {}",
173                children.len()
174            )
175        }
176        let codes_nullable = metadata
177            .is_nullable_codes
178            .map(Nullability::from)
179            // If no `is_nullable_codes` metadata use the nullability of the values
180            // (and whole array) as before.
181            .unwrap_or_else(|| dtype.nullability());
182        let codes_dtype = DType::Primitive(codes_ptype, codes_nullable);
183        let codes = children.get(0, &codes_dtype, len)?;
184        let values = children.get(1, dtype, metadata.values_len as usize)?;
185        let all_values_referenced = metadata.all_values_referenced.unwrap_or(false);
186
187        Ok(ArrayParts::new(
188            self.clone(),
189            dtype.clone(),
190            len,
191            unsafe { DictData::new_unchecked().set_all_values_referenced(all_values_referenced) },
192            smallvec![Some(codes), Some(values)],
193        ))
194    }
195
196    fn slot_name(_array: ArrayView<'_, Self>, idx: usize) -> String {
197        DictSlots::NAMES[idx].to_string()
198    }
199
200    fn execute(array: Array<Self>, ctx: &mut ExecutionCtx) -> VortexResult<ExecutionResult> {
201        if array.is_empty() {
202            let result_dtype = array
203                .dtype()
204                .union_nullability(array.codes().dtype().nullability());
205            return Ok(ExecutionResult::done(Canonical::empty(&result_dtype)));
206        }
207
208        let array = require_child!(array, array.codes(), DictSlots::CODES => Primitive);
209
210        if array.codes().validity()?.definitely_all_null() {
211            return Ok(ExecutionResult::done(ConstantArray::new(
212                Scalar::null(array.dtype().as_nullable()),
213                array.codes().len(),
214            )));
215        }
216
217        let array = require_child!(array, array.values(), DictSlots::VALUES => AnyCanonical);
218
219        let DictParts { values, codes, .. } = array.into_parts();
220
221        Ok(ExecutionResult::done(take_canonical(
222            values.as_::<AnyCanonical>(),
223            codes.as_::<Primitive>(),
224            ctx,
225        )?))
226    }
227
228    fn append_to_builder(
229        array: ArrayView<'_, Self>,
230        builder: &mut dyn ArrayBuilder,
231        ctx: &mut ExecutionCtx,
232    ) -> VortexResult<()> {
233        if !array.is_empty() {
234            let codes = array.codes().clone().execute::<PrimitiveArray>(ctx)?;
235            if !codes.validity()?.definitely_all_null() {
236                let values = array.values();
237                if array.len() <= values.len() / 4
238                    && matches!(array.dtype(), DType::Utf8(_) | DType::Binary(_))
239                    && !values.is::<AnyCanonical>()
240                {
241                    // A sparse selection reaches the take kernel of the values, such as the OnPair
242                    // token-run gather, before the whole dictionary is decoded.
243                    // SAFETY: executing the codes keeps their values, dtype and length.
244                    let taken =
245                        unsafe { DictArray::new_unchecked(codes.into_array(), values.clone()) };
246                    let canonical = taken.into_array().execute::<Canonical>(ctx)?.into_array();
247                    return canonical.append_to_builder(builder, ctx);
248                }
249
250                // Decode the children without taking values to the full row count. The
251                // variable-binary builders gather directly through these dictionary codes.
252                let values = if array.values().is::<AnyCanonical>() {
253                    array.values().clone()
254                } else {
255                    array
256                        .values()
257                        .clone()
258                        .execute::<Canonical>(ctx)?
259                        .into_array()
260                };
261                let values = values.as_::<AnyCanonical>();
262                let codes = codes.as_view();
263                if let CanonicalView::VarBinView(values) = values
264                    && let Some(result) = match_each_varbin_builder!(builder, |builder| {
265                        let validity = array.validity()?.execute_mask(array.len(), ctx)?;
266                        append_dict_to_varbin(codes, values, validity, builder)
267                    })
268                {
269                    return result;
270                }
271                if let CanonicalView::VarBinView(values) = values
272                    && let Some(builder) = builder.as_any_mut().downcast_mut::<VarBinViewBuilder>()
273                {
274                    let validity = array.validity()?.execute_mask(array.len(), ctx)?;
275                    return append_dict_to_varbinview(codes, values, validity, builder);
276                }
277                let canonical = take_canonical(values, codes, ctx)?.into_array();
278                canonical.append_to_builder(builder, ctx)?;
279                return Ok(());
280            }
281        }
282
283        let canonical = array
284            .array()
285            .clone()
286            .execute::<Canonical>(ctx)?
287            .into_array();
288        canonical.append_to_builder(builder, ctx)?;
289        Ok(())
290    }
291
292    fn reduce_parent(
293        array: ArrayView<'_, Self>,
294        parent: &ArrayRef,
295        child_idx: usize,
296    ) -> VortexResult<Option<ArrayRef>> {
297        PARENT_RULES.evaluate(array, parent, child_idx)
298    }
299}
300
301/// Gathers the dictionary values straight into `builder` as views.
302///
303/// The canonical route first takes the values to full logical length — allocating an intermediate
304/// views buffer proportional to the row count — and then `append_varbinview_array` walks all
305/// those views a second time to rebase their buffer indices onto the builder's. Gathering through
306/// the codes directly instead adopts the dictionary's buffers once (deduplicated across chunks
307/// sharing the dictionary, when the builder deduplicates) and writes each row's rebased view in a
308/// single pass, with no byte copy at all.
309fn append_dict_to_varbinview(
310    codes: ArrayView<'_, Primitive>,
311    values: ArrayView<'_, VarBinView>,
312    validity: Mask,
313    builder: &mut VarBinViewBuilder,
314) -> VortexResult<()> {
315    let views = values.views();
316    let buffers = values
317        .data_buffers()
318        .iter()
319        .map(|buffer| buffer.as_host().clone())
320        .collect::<Vec<_>>();
321
322    match_each_integer_ptype!(codes.ptype(), |C| {
323        let codes = codes.as_slice::<C>();
324        builder.append_views_gathered(buffers, views, &validity, |row| {
325            AsPrimitive::<usize>::as_(codes[row])
326        });
327    });
328    Ok(())
329}
330
331/// Gathers the dictionary values straight into `builder`.
332///
333/// The canonical route first takes the values to full logical length, which allocates and then
334/// re-reads a views buffer proportional to the row count. The dictionary is usually far smaller
335/// than the column, so resolving each code against it in place skips that intermediate entirely
336/// and leaves one `memcpy` per row as the only work.
337fn append_dict_to_varbin<O: OffsetBuilderPType>(
338    codes: ArrayView<'_, Primitive>,
339    values: ArrayView<'_, VarBinView>,
340    validity: Mask,
341    builder: &mut VarBinBuilder<O>,
342) -> VortexResult<()>
343where
344    usize: AsPrimitive<O>,
345{
346    let len = codes.as_ref().len();
347    vortex_ensure_eq!(
348        validity.len(),
349        len,
350        "Dictionary gather validity length mismatch"
351    );
352
353    // Resolve the dictionary's storage once so that looking up a code is an O(1) read.
354    let views = values.views();
355    let buffers = values
356        .data_buffers()
357        .iter()
358        .map(|buffer| buffer.as_host().as_slice())
359        .collect::<Vec<_>>();
360
361    match_each_integer_ptype!(codes.ptype(), |C| {
362        let codes = codes.as_slice::<C>();
363        let view = |row: usize| &views[AsPrimitive::<usize>::as_(codes[row])];
364
365        // Both passes below resolve a row through its code, so the byte total comes from the same
366        // walk over the valid rows that the copy will make.
367        let num_bytes = match validity.bit_buffer() {
368            AllOr::All => (0..len).map(|row| view(row).len() as usize).sum(),
369            AllOr::None => {
370                builder.push_nulls(len);
371                return Ok(());
372            }
373            AllOr::Some(bits) => {
374                let mut total = 0;
375                bits.for_each_set_index(|row| total += view(row).len() as usize);
376                total
377            }
378        };
379
380        builder.append_valid_slices(num_bytes, &validity, |row| {
381            // SAFETY: the byte-count pass checked every selected code against `views`, and
382            // append_valid_slices visits exactly those same rows. The slices and validity are
383            // immutable, and the length check above bounds every visited row within `codes`.
384            let value = unsafe {
385                views.get_unchecked(AsPrimitive::<usize>::as_(*codes.get_unchecked(row)))
386            };
387            value.bytes(&buffers)
388        })
389    })
390}
391
392#[cfg(test)]
393mod tests {
394    use std::sync::LazyLock;
395
396    use vortex_session::VortexSession;
397
398    use super::*;
399    use crate::VortexSessionExecute;
400    use crate::arrays::PrimitiveArray;
401    use crate::arrays::VarBinViewArray;
402    use crate::arrays::dict::DictArray;
403    use crate::assert_arrays_eq;
404    use crate::dtype::Nullability::Nullable;
405
406    static SESSION: LazyLock<VortexSession> = LazyLock::new(VortexSession::empty);
407
408    const LONG: &str = "a string that is far too long to be inlined in a view";
409
410    #[test]
411    fn dictionary_gather_rejects_mismatched_validity() -> VortexResult<()> {
412        let ctx = SESSION.create_execution_ctx();
413        let codes = PrimitiveArray::from_iter([0u8, 1]);
414        let values = VarBinViewArray::from_iter([Some("one"), Some("two")], DType::Utf8(Nullable));
415        let mut builder = VarBinBuilder::<i32>::new_in(DType::Utf8(Nullable), ctx.allocator());
416        let result = append_dict_to_varbin(
417            codes.as_view(),
418            values.as_view(),
419            Mask::new_true(3),
420            &mut builder,
421        );
422        assert!(result.is_err());
423        assert_eq!(builder.len(), 0);
424        Ok(())
425    }
426
427    #[test]
428    fn dictionary_gather_does_not_read_null_row_codes() -> VortexResult<()> {
429        let mut ctx = SESSION.create_execution_ctx();
430        let codes = PrimitiveArray::from_iter([0u8, 255, 1]);
431        let values = VarBinViewArray::from_iter([Some("one"), Some("two")], DType::Utf8(Nullable));
432        let mut builder = VarBinBuilder::<i32>::new_in(DType::Utf8(Nullable), ctx.allocator());
433        append_dict_to_varbin(
434            codes.as_view(),
435            values.as_view(),
436            Mask::from_iter([true, false, true]),
437            &mut builder,
438        )?;
439        let expected =
440            VarBinViewArray::from_iter([Some("one"), None, Some("two")], DType::Utf8(Nullable));
441        assert_arrays_eq!(builder.finish_into_varbin(), expected, &mut ctx);
442        Ok(())
443    }
444
445    #[test]
446    #[should_panic(expected = "index out of bounds")]
447    fn dictionary_gather_checks_selected_codes_before_copy() {
448        let ctx = SESSION.create_execution_ctx();
449        let codes = PrimitiveArray::from_iter([0u8, 255]);
450        let values = VarBinViewArray::from_iter([Some("one")], DType::Utf8(Nullable));
451        let mut builder = VarBinBuilder::<i32>::new_in(DType::Utf8(Nullable), ctx.allocator());
452        drop(append_dict_to_varbin(
453            codes.as_view(),
454            values.as_view(),
455            Mask::new_true(2),
456            &mut builder,
457        ));
458    }
459
460    #[test]
461    fn append_to_builder_gathers_through_the_dictionary() -> VortexResult<()> {
462        let mut ctx = SESSION.create_execution_ctx();
463        let dict = DictArray::try_new(
464            PrimitiveArray::from_option_iter([Some(0u32), Some(2), None, Some(1), Some(0)])
465                .into_array(),
466            VarBinViewArray::from_iter([Some(LONG), None, Some("short")], DType::Utf8(Nullable))
467                .into_array(),
468        )?;
469
470        let mut builder = VarBinBuilder::<i32>::new_in(DType::Utf8(Nullable), ctx.allocator());
471        dict.append_to_builder(&mut builder, &mut ctx)?;
472
473        let expected = VarBinViewArray::from_iter(
474            [Some(LONG), Some("short"), None, None, Some(LONG)],
475            DType::Utf8(Nullable),
476        );
477        assert_arrays_eq!(builder.finish_into_varbin(), expected, &mut ctx);
478        Ok(())
479    }
480
481    /// The view-builder path gathers views through the codes without materializing the taken
482    /// array, so the result must still match the canonical take — including rows whose code is
483    /// null and rows whose dictionary value is null.
484    #[test]
485    fn append_to_view_builder_gathers_through_the_dictionary() -> VortexResult<()> {
486        let mut ctx = SESSION.create_execution_ctx();
487        let dict = DictArray::try_new(
488            PrimitiveArray::from_option_iter([Some(0u32), Some(2), None, Some(1), Some(0)])
489                .into_array(),
490            VarBinViewArray::from_iter([Some(LONG), None, Some("short")], DType::Utf8(Nullable))
491                .into_array(),
492        )?;
493
494        let mut builder = VarBinViewBuilder::with_capacity_in(
495            DType::Utf8(Nullable),
496            8,
497            vortex_buffer::BufferAllocatorRef::statically_allocated(),
498        );
499        builder.append_value(LONG);
500        dict.append_to_builder(&mut builder, &mut ctx)?;
501
502        let expected = VarBinViewArray::from_iter(
503            [
504                Some(LONG),
505                Some(LONG),
506                Some("short"),
507                None,
508                None,
509                Some(LONG),
510            ],
511            DType::Utf8(Nullable),
512        );
513        assert_arrays_eq!(builder.finish_into_varbinview(), expected, &mut ctx);
514        Ok(())
515    }
516
517    /// Two chunks gathered through the same dictionary into a deduplicating builder must adopt
518    /// the dictionary's data buffers once.
519    #[test]
520    fn append_to_dedup_view_builder_adopts_the_dictionary_once() -> VortexResult<()> {
521        let mut ctx = SESSION.create_execution_ctx();
522        let values = VarBinViewArray::from_iter([Some(LONG), Some("short")], DType::Utf8(Nullable));
523        assert_eq!(values.data_buffers().len(), 1);
524
525        let first = DictArray::try_new(
526            PrimitiveArray::from_option_iter([Some(0u32), Some(1)]).into_array(),
527            values.clone().into_array(),
528        )?;
529        let second = DictArray::try_new(
530            PrimitiveArray::from_option_iter([Some(1u32), Some(0)]).into_array(),
531            values.into_array(),
532        )?;
533
534        let mut builder = VarBinViewBuilder::with_buffer_deduplication_in(
535            DType::Utf8(Nullable),
536            8,
537            vortex_buffer::BufferAllocatorRef::statically_allocated(),
538        );
539        first.append_to_builder(&mut builder, &mut ctx)?;
540        second.append_to_builder(&mut builder, &mut ctx)?;
541        assert_eq!(builder.completed_block_count(), 1);
542
543        let expected = VarBinViewArray::from_iter(
544            [Some(LONG), Some("short"), Some("short"), Some(LONG)],
545            DType::Utf8(Nullable),
546        );
547        assert_arrays_eq!(builder.finish_into_varbinview(), expected, &mut ctx);
548        Ok(())
549    }
550}