Skip to main content

vortex_array/arrays/dict/
array.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4use std::fmt::Display;
5use std::fmt::Formatter;
6
7use num_traits::AsPrimitive;
8use smallvec::smallvec;
9use vortex_buffer::BitBuffer;
10use vortex_error::VortexExpect;
11use vortex_error::VortexResult;
12use vortex_error::vortex_bail;
13use vortex_error::vortex_ensure;
14use vortex_error::vortex_err;
15use vortex_mask::AllOr;
16
17use crate::ArrayRef;
18use crate::ArraySlots;
19use crate::ExecutionCtx;
20use crate::array::Array;
21use crate::array::ArrayParts;
22use crate::array::TypedArrayRef;
23use crate::array_slots;
24use crate::arrays::Dict;
25use crate::arrays::PrimitiveArray;
26use crate::dtype::DType;
27use crate::dtype::PType;
28use crate::match_each_integer_ptype;
29
30#[derive(Clone, prost::Message)]
31pub struct DictMetadata {
32    #[prost(uint32, tag = "1")]
33    pub(super) values_len: u32,
34    #[prost(int32, tag = "2")]
35    pub(super) codes_ptype: i32,
36    // nullable codes are optional since they were added after stabilisation.
37    #[prost(optional, bool, tag = "3")]
38    pub(super) is_nullable_codes: Option<bool>,
39    // all_values_referenced is optional for backward compatibility.
40    // true = all dictionary values are definitely referenced by at least one code.
41    // false/None = unknown whether all values are referenced (conservative default).
42    #[prost(optional, bool, tag = "4")]
43    pub(super) all_values_referenced: Option<bool>,
44}
45
46impl DictMetadata {
47    pub(super) fn get_codes_ptype(&self) -> VortexResult<PType> {
48        PType::try_from(self.codes_ptype).map_err(|_| {
49            vortex_err!(
50                "DictMetadata codes_ptype must be a known PType, got {}",
51                self.codes_ptype
52            )
53        })
54    }
55}
56
57#[array_slots(Dict)]
58pub struct DictSlots {
59    /// The codes array mapping each element to a dictionary entry.
60    #[slot(0)]
61    pub codes: ArrayRef,
62    /// The dictionary values array containing the unique values.
63    #[slot(1)]
64    pub values: ArrayRef,
65}
66
67#[derive(Debug, Clone)]
68pub struct DictData {
69    /// Indicates whether all dictionary values are definitely referenced by at least one code.
70    /// `true` = all values are referenced (computed during encoding).
71    /// `false` = unknown/might have unreferenced values.
72    /// In case this is incorrect never use this to enable memory unsafe behaviour just semantically
73    /// incorrect behaviour.
74    pub(super) all_values_referenced: bool,
75}
76
77impl Display for DictData {
78    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
79        write!(f, "all_values_referenced: {}", self.all_values_referenced)
80    }
81}
82
83impl DictData {
84    /// Build a new `DictArray` without validating the codes or values.
85    ///
86    /// # Safety
87    /// This should be called only when you can guarantee the invariants checked
88    /// by the safe `DictArray::try_new` constructor are valid, for example when
89    /// you are filtering or slicing an existing valid `DictArray`.
90    pub unsafe fn new_unchecked() -> Self {
91        Self {
92            all_values_referenced: false,
93        }
94    }
95
96    /// Set whether all dictionary values are definitely referenced.
97    ///
98    /// # Safety
99    /// The caller must ensure that when setting `all_values_referenced = true`, ALL dictionary
100    /// values are actually referenced by at least one valid code. Setting this incorrectly can
101    /// lead to incorrect query results in operations like min/max.
102    ///
103    /// This is typically only set to `true` during dictionary encoding when we know for certain
104    /// that all values are referenced.
105    pub unsafe fn set_all_values_referenced(mut self, all_values_referenced: bool) -> Self {
106        self.all_values_referenced = all_values_referenced;
107        self
108    }
109
110    /// Build a new `DictArray` from its components, `codes` and `values`.
111    ///
112    /// This constructor will panic if `codes` or `values` do not pass validation for building
113    /// a new `DictArray`. See `DictArray::try_new` for a description of the error conditions.
114    pub fn new(codes_dtype: &DType) -> Self {
115        Self::try_new(codes_dtype).vortex_expect("DictArray new")
116    }
117
118    /// Build a new `DictArray` from its components, `codes` and `values`.
119    ///
120    /// The codes must be integers, and may be nullable. Values can be any
121    /// type, and may also be nullable. This mirrors the nullability of the Arrow `DictionaryArray`.
122    ///
123    /// # Errors
124    ///
125    /// The `codes` **must** be integers, and the maximum code must be less than the length
126    /// of the `values` array. Otherwise, this constructor returns an error.
127    ///
128    /// It is an error to provide a nullable `codes` with non-nullable `values`.
129    pub(crate) fn try_new(codes_dtype: &DType) -> VortexResult<Self> {
130        if !codes_dtype.is_int() {
131            vortex_bail!("expected type: int but instead got {}", codes_dtype);
132        }
133
134        Ok(unsafe { Self::new_unchecked() })
135    }
136}
137
138pub trait DictArrayExt: TypedArrayRef<Dict> + DictArraySlotsExt {
139    #[inline]
140    fn has_all_values_referenced(&self) -> bool {
141        self.all_values_referenced
142    }
143
144    fn validate_all_values_referenced(&self, ctx: &mut ExecutionCtx) -> VortexResult<()> {
145        if self.has_all_values_referenced() {
146            if !self.codes().is_host() {
147                return Ok(());
148            }
149
150            let referenced_mask = self.compute_referenced_values_mask(true, ctx)?;
151            let all_referenced = referenced_mask.true_count() == referenced_mask.len();
152
153            vortex_ensure!(all_referenced, "value in dict not referenced");
154        }
155
156        Ok(())
157    }
158
159    fn compute_referenced_values_mask(
160        &self,
161        referenced: bool,
162        ctx: &mut ExecutionCtx,
163    ) -> VortexResult<BitBuffer> {
164        let codes = self.codes();
165        let codes_validity = codes.validity()?.execute_mask(codes.len(), ctx)?;
166        let codes_primitive = codes.clone().execute::<PrimitiveArray>(ctx)?;
167        let values_len = self.values().len();
168
169        let mut values_vec = vec![!referenced; values_len];
170        let saturated = match codes_validity.bit_buffer() {
171            AllOr::All => match_each_integer_ptype!(codes_primitive.ptype(), |P| {
172                mark_codes(&mut values_vec, referenced, codes_primitive.as_slice::<P>())
173            }),
174            AllOr::None => false,
175            AllOr::Some(mask) => match_each_integer_ptype!(codes_primitive.ptype(), |P| {
176                mark_masked_codes(
177                    &mut values_vec,
178                    referenced,
179                    codes_primitive.as_slice::<P>(),
180                    mask,
181                    codes_validity.true_count(),
182                )
183            }),
184        };
185        if saturated {
186            return Ok(BitBuffer::full(referenced, values_len));
187        }
188
189        Ok(BitBuffer::from(values_vec))
190    }
191}
192impl<T: TypedArrayRef<Dict>> DictArrayExt for T {}
193
194/// Number of codes visited between checks for whether every dictionary value is referenced.
195const EARLY_EXIT_CHUNK: usize = 2048;
196
197/// Sets `values[code]` to `referenced` for every code, returning `true` early once every entry
198/// of `values` is `referenced`, since further codes cannot change the result.
199///
200/// With fewer codes than values not every value can be referenced, so the saturation checks are
201/// skipped entirely.
202fn mark_codes<P: AsPrimitive<usize>>(values: &mut [bool], referenced: bool, codes: &[P]) -> bool {
203    if codes.len() < values.len() {
204        for code in codes {
205            values[code.as_()] = referenced;
206        }
207        return false;
208    }
209
210    let mut cursor = 0;
211    for chunk in codes.chunks(EARLY_EXIT_CHUNK) {
212        for code in chunk {
213            values[code.as_()] = referenced;
214        }
215        if is_saturated(values, &mut cursor, referenced) {
216            return true;
217        }
218    }
219    false
220}
221
222/// Like [`mark_codes`], but only for the codes at the `valid_count` set positions of `mask`.
223fn mark_masked_codes<P: AsPrimitive<usize>>(
224    values: &mut [bool],
225    referenced: bool,
226    codes: &[P],
227    mask: &BitBuffer,
228    valid_count: usize,
229) -> bool {
230    if valid_count < values.len() {
231        mask.set_indices().for_each(|idx| {
232            values[codes[idx].as_()] = referenced;
233        });
234        return false;
235    }
236
237    let mut cursor = 0;
238    for start in (0..codes.len()).step_by(EARLY_EXIT_CHUNK) {
239        let end = (start + EARLY_EXIT_CHUNK).min(codes.len());
240        let codes = &codes[start..end];
241        mask.slice(start..end).set_indices().for_each(|idx| {
242            values[codes[idx].as_()] = referenced;
243        });
244        if is_saturated(values, &mut cursor, referenced) {
245            return true;
246        }
247    }
248    false
249}
250
251/// Advances `cursor` past the entries of `values` equal to `referenced` and returns whether that
252/// is all of them. Callers share one cursor that only moves forward, so repeated checks cost
253/// `O(values.len())` in total.
254#[inline]
255fn is_saturated(values: &[bool], cursor: &mut usize, referenced: bool) -> bool {
256    // Skip whole blocks with a branch-free comparison the compiler can vectorize, then find the
257    // exact stopping point within the first block that is not fully marked.
258    const BLOCK: usize = 32;
259    let rest = &values[*cursor..];
260    let full_blocks = rest
261        .as_chunks::<BLOCK>()
262        .0
263        .iter()
264        .take_while(|block| block.iter().fold(true, |acc, &v| acc & (v == referenced)))
265        .count();
266    *cursor += full_blocks * BLOCK;
267    *cursor += values[*cursor..]
268        .iter()
269        .take_while(|&&v| v == referenced)
270        .count();
271    *cursor == values.len()
272}
273
274/// Concrete parts of a [`DictArray`](super::DictArray) after iterative execution.
275pub struct DictParts {
276    pub dtype: DType,
277    pub codes: ArrayRef,
278    pub values: ArrayRef,
279}
280
281pub trait DictOwnedExt {
282    fn into_parts(self) -> DictParts;
283}
284
285impl DictOwnedExt for Array<Dict> {
286    fn into_parts(self) -> DictParts {
287        match self.try_into_parts() {
288            Ok(array_parts) => {
289                let slots = DictSlots::from_slots(array_parts.slots);
290                DictParts {
291                    dtype: array_parts.dtype,
292                    codes: slots.codes,
293                    values: slots.values,
294                }
295            }
296            Err(array) => {
297                let slots = DictSlotsView::from_slots(array.slots());
298                DictParts {
299                    dtype: array.dtype().clone(),
300                    codes: slots.codes.clone(),
301                    values: slots.values.clone(),
302                }
303            }
304        }
305    }
306}
307
308impl Array<Dict> {
309    /// Build a new `DictArray` from its components, `codes` and `values`.
310    pub fn new(codes: ArrayRef, values: ArrayRef) -> Self {
311        Self::try_new(codes, values).vortex_expect("DictArray new")
312    }
313
314    /// Build a new `DictArray` from its components, `codes` and `values`.
315    pub fn try_new(codes: ArrayRef, values: ArrayRef) -> VortexResult<Self> {
316        let dtype = values
317            .dtype()
318            .union_nullability(codes.dtype().nullability());
319        let len = codes.len();
320        let data = DictData::try_new(codes.dtype())?;
321        Array::try_from_parts(ArrayParts::new(
322            Dict,
323            dtype,
324            len,
325            data,
326            smallvec![Some(codes), Some(values)],
327        ))
328    }
329
330    /// Build a new `DictArray` without validating the codes or values.
331    ///
332    /// # Safety
333    ///
334    /// See [`DictData::new_unchecked`].
335    pub unsafe fn new_unchecked(codes: ArrayRef, values: ArrayRef) -> Self {
336        let dtype = values
337            .dtype()
338            .union_nullability(codes.dtype().nullability());
339        let len = codes.len();
340        let data = unsafe { DictData::new_unchecked() };
341        unsafe {
342            Array::from_parts_unchecked(ArrayParts::new(
343                Dict,
344                dtype,
345                len,
346                data,
347                smallvec![Some(codes), Some(values)],
348            ))
349        }
350    }
351
352    /// Set whether all values in the dictionary are referenced by at least one code.
353    ///
354    /// # Safety
355    ///
356    /// See [`DictData::set_all_values_referenced`].
357    pub unsafe fn set_all_values_referenced(self, all_values_referenced: bool) -> Self {
358        let dtype = self.dtype().clone();
359        let len = self.len();
360        let slots: ArraySlots = self.slots().iter().cloned().collect();
361        let data = unsafe {
362            self.into_data()
363                .set_all_values_referenced(all_values_referenced)
364        };
365        unsafe { Array::from_parts_unchecked(ArrayParts::new(Dict, dtype, len, data, slots)) }
366    }
367}
368
369#[cfg(test)]
370mod test {
371    use std::sync::LazyLock;
372
373    use prost::Message;
374    use rand::RngExt;
375    use rand::SeedableRng;
376    use rand::distr::Distribution;
377    use rand::distr::StandardUniform;
378    use rand::prelude::StdRng;
379    use vortex_buffer::BitBuffer;
380    use vortex_buffer::buffer;
381    use vortex_error::VortexExpect;
382    use vortex_error::VortexResult;
383    use vortex_error::vortex_panic;
384    use vortex_mask::AllOr;
385    use vortex_session::VortexSession;
386
387    use super::DictMetadata;
388    use crate::ArrayRef;
389    use crate::IntoArray;
390    use crate::VortexSessionExecute;
391    use crate::array::VTable;
392    use crate::arrays::ChunkedArray;
393    use crate::arrays::Dict;
394    use crate::arrays::DictArray;
395    use crate::arrays::PrimitiveArray;
396    use crate::arrays::VarBinViewArray;
397    use crate::arrays::dict::DictArrayExt;
398    use crate::assert_arrays_eq;
399    use crate::builders::VarBinBuilder;
400    use crate::builders::builder_with_capacity_in;
401    use crate::dtype::DType;
402    use crate::dtype::NativePType;
403    use crate::dtype::Nullability::NonNullable;
404    use crate::dtype::PType;
405    use crate::dtype::UnsignedPType;
406    use crate::validity::Validity;
407
408    static SESSION: LazyLock<VortexSession> = LazyLock::new(VortexSession::empty);
409
410    #[test]
411    fn nullable_codes_validity() {
412        let dict = DictArray::try_new(
413            PrimitiveArray::new(
414                buffer![0u32, 1, 2, 2, 1],
415                Validity::from(BitBuffer::from(vec![true, false, true, false, true])),
416            )
417            .into_array(),
418            PrimitiveArray::new(buffer![3, 6, 9], Validity::AllValid).into_array(),
419        )
420        .unwrap();
421        let mask = dict
422            .as_ref()
423            .validity()
424            .unwrap()
425            .execute_mask(dict.as_ref().len(), &mut SESSION.create_execution_ctx())
426            .unwrap();
427        let AllOr::Some(indices) = mask.indices() else {
428            vortex_panic!("Expected indices from mask")
429        };
430        assert_eq!(indices, [0, 2, 4]);
431    }
432
433    #[test]
434    fn nullable_values_validity() {
435        let dict = DictArray::try_new(
436            buffer![0u32, 1, 2, 2, 1].into_array(),
437            PrimitiveArray::new(
438                buffer![3, 6, 9],
439                Validity::from(BitBuffer::from(vec![true, false, false])),
440            )
441            .into_array(),
442        )
443        .unwrap();
444        let mask = dict
445            .as_ref()
446            .validity()
447            .unwrap()
448            .execute_mask(dict.as_ref().len(), &mut SESSION.create_execution_ctx())
449            .unwrap();
450        let AllOr::Some(indices) = mask.indices() else {
451            vortex_panic!("Expected indices from mask")
452        };
453        assert_eq!(indices, [0]);
454    }
455
456    #[test]
457    fn nullable_codes_and_values() {
458        let dict = DictArray::try_new(
459            PrimitiveArray::new(
460                buffer![0u32, 1, 2, 2, 1],
461                Validity::from(BitBuffer::from(vec![true, false, true, false, true])),
462            )
463            .into_array(),
464            PrimitiveArray::new(
465                buffer![3, 6, 9],
466                Validity::from(BitBuffer::from(vec![false, true, true])),
467            )
468            .into_array(),
469        )
470        .unwrap();
471        let mask = dict
472            .as_ref()
473            .validity()
474            .unwrap()
475            .execute_mask(dict.as_ref().len(), &mut SESSION.create_execution_ctx())
476            .unwrap();
477        let AllOr::Some(indices) = mask.indices() else {
478            vortex_panic!("Expected indices from mask")
479        };
480        assert_eq!(indices, [2, 4]);
481    }
482
483    #[test]
484    fn nullable_codes_and_non_null_values() {
485        let dict = DictArray::try_new(
486            PrimitiveArray::new(
487                buffer![0u32, 1, 2, 2, 1],
488                Validity::from(BitBuffer::from(vec![true, false, true, false, true])),
489            )
490            .into_array(),
491            PrimitiveArray::new(buffer![3, 6, 9], Validity::NonNullable).into_array(),
492        )
493        .unwrap();
494        let mask = dict
495            .as_ref()
496            .validity()
497            .unwrap()
498            .execute_mask(dict.as_ref().len(), &mut SESSION.create_execution_ctx())
499            .unwrap();
500        let AllOr::Some(indices) = mask.indices() else {
501            vortex_panic!("Expected indices from mask")
502        };
503        assert_eq!(indices, [0, 2, 4]);
504    }
505
506    fn make_dict_primitive_chunks<T: NativePType, Code: UnsignedPType>(
507        len: usize,
508        unique_values: usize,
509        chunk_count: usize,
510    ) -> (ArrayRef, Vec<T>)
511    where
512        StandardUniform: Distribution<T>,
513    {
514        let mut rng = StdRng::seed_from_u64(0);
515
516        let mut expected = Vec::with_capacity(len * chunk_count);
517        let array = (0..chunk_count)
518            .map(|_| {
519                let values = (0..unique_values)
520                    .map(|_| rng.random::<T>())
521                    .collect::<PrimitiveArray>();
522                let codes = (0..len)
523                    .map(|_| {
524                        Code::from(rng.random_range(0..unique_values)).vortex_expect("valid value")
525                    })
526                    .collect::<PrimitiveArray>();
527
528                expected.extend(codes.as_slice::<Code>().iter().map(|code| {
529                    values.as_slice::<T>()[<Code as num_traits::AsPrimitive<usize>>::as_(*code)]
530                }));
531                DictArray::try_new(codes.into_array(), values.into_array())
532                    .vortex_expect("DictArray creation should succeed in arbitrary impl")
533                    .into_array()
534            })
535            .collect::<ChunkedArray>()
536            .into_array();
537        (array, expected)
538    }
539
540    #[test]
541    fn test_dict_utf8_append_to_varbin_builder() -> VortexResult<()> {
542        let values = VarBinViewArray::from_iter_str(["zero", "one", "two"]);
543        let dict = DictArray::try_new(buffer![2u8, 0, 2, 1].into_array(), values.into_array())?;
544        let expected = VarBinViewArray::from_iter_str(["two", "zero", "two", "one"]);
545        let mut ctx = SESSION.create_execution_ctx();
546        let mut builder = VarBinBuilder::<i32>::with_capacity_in(
547            dict.dtype().clone(),
548            dict.len(),
549            ctx.allocator(),
550        );
551
552        dict.into_array()
553            .append_to_builder(&mut builder, &mut ctx)?;
554
555        assert_arrays_eq!(builder.finish_into_varbin(), expected, &mut ctx);
556        Ok(())
557    }
558
559    #[test]
560    fn test_dict_array_from_primitive_chunks() -> VortexResult<()> {
561        let mut ctx = SESSION.create_execution_ctx();
562        let len = 2;
563        let chunk_count = 2;
564        let (array, expected) = make_dict_primitive_chunks::<u64, u64>(len, 2, chunk_count);
565
566        let mut builder = builder_with_capacity_in(
567            &DType::Primitive(PType::U64, NonNullable),
568            len * chunk_count,
569            ctx.allocator(),
570        );
571        array.append_to_builder(builder.as_mut(), &mut SESSION.create_execution_ctx())?;
572
573        let prim_into = builder.finish_into_canonical(&mut ctx).into_primitive();
574
575        let expected = PrimitiveArray::from_iter(expected);
576        assert_arrays_eq!(array, expected, &mut ctx);
577        assert_arrays_eq!(prim_into, expected, &mut ctx);
578        Ok(())
579    }
580
581    #[cfg_attr(miri, ignore)]
582    #[test]
583    fn test_dict_metadata() {
584        use prost::Message;
585
586        use super::DictMetadata;
587        use crate::test_harness::check_metadata;
588
589        check_metadata(
590            "dict.metadata",
591            &DictMetadata {
592                codes_ptype: PType::U64 as i32,
593                values_len: u32::MAX,
594                is_nullable_codes: None,
595                all_values_referenced: None,
596            }
597            .encode_to_vec(),
598        );
599    }
600
601    #[test]
602    fn test_deserialize_rejects_unknown_codes_ptype() -> VortexResult<()> {
603        let metadata = DictMetadata {
604            codes_ptype: 11,
605            ..Default::default()
606        }
607        .encode_to_vec();
608        let children: Vec<ArrayRef> = Vec::new();
609        let result = Dict.deserialize(
610            &DType::Primitive(PType::I32, NonNullable),
611            0,
612            &metadata,
613            &[],
614            &children,
615            &SESSION,
616        );
617        assert!(result.is_err_and(|err| {
618            err.to_string()
619                .contains("DictMetadata codes_ptype must be a known PType, got 11")
620        }));
621
622        let known = DictMetadata {
623            codes_ptype: PType::U32 as i32,
624            ..Default::default()
625        };
626        assert_eq!(known.get_codes_ptype()?, PType::U32);
627
628        Ok(())
629    }
630
631    /// Covers the early exit taken once every value is referenced, including when that happens
632    /// after the first chunk, alongside cases that never saturate.
633    #[rstest::rstest]
634    #[case::saturates_in_first_chunk(16, 5000, 16, None)]
635    #[case::saturates_in_later_chunk(4096, 60_000, 4096, None)]
636    #[case::saturates_unaligned_to_scan_block(4001, 60_000, 4001, None)]
637    #[case::never_saturates(1024, 10_000, 1000, None)]
638    #[case::fewer_codes_than_values(1024, 1000, 1024, None)]
639    #[case::fewer_valid_codes_than_values(1024, 1500, 1024, Some(0.5))]
640    #[case::saturates_with_nulls(64, 10_000, 64, Some(0.5))]
641    #[case::never_saturates_with_nulls(64, 10_000, 63, Some(0.5))]
642    fn referenced_values_mask_matches_reference(
643        #[case] num_values: u32,
644        #[case] num_codes: usize,
645        #[case] referenced_range: u32,
646        #[case] valid_fraction: Option<f64>,
647        #[values(true, false)] referenced: bool,
648    ) -> VortexResult<()> {
649        let mut rng = StdRng::seed_from_u64(0);
650        let codes: Vec<Option<u32>> = (0..num_codes)
651            .map(|_| {
652                valid_fraction
653                    .is_none_or(|f| rng.random_bool(f))
654                    .then(|| rng.random_range(0..referenced_range))
655            })
656            .collect();
657
658        let mut expected = vec![!referenced; num_values as usize];
659        for code in codes.iter().flatten() {
660            expected[*code as usize] = referenced;
661        }
662
663        let codes = match valid_fraction {
664            Some(_) => PrimitiveArray::from_option_iter(codes).into_array(),
665            None => PrimitiveArray::from_iter(codes.into_iter().flatten()).into_array(),
666        };
667        let dict =
668            DictArray::try_new(codes, PrimitiveArray::from_iter(0..num_values).into_array())?;
669        let mut ctx = SESSION.create_execution_ctx();
670        let mask = dict.compute_referenced_values_mask(referenced, &mut ctx)?;
671
672        assert_eq!(mask, BitBuffer::from(expected));
673        Ok(())
674    }
675}