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