1use 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 #[prost(optional, bool, tag = "3")]
38 pub(super) is_nullable_codes: Option<bool>,
39 #[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 #[slot(0)]
61 pub codes: ArrayRef,
62 #[slot(1)]
64 pub values: ArrayRef,
65}
66
67#[derive(Debug, Clone)]
68pub struct DictData {
69 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 pub unsafe fn new_unchecked() -> Self {
91 Self {
92 all_values_referenced: false,
93 }
94 }
95
96 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 pub fn new(codes_dtype: &DType) -> Self {
115 Self::try_new(codes_dtype).vortex_expect("DictArray new")
116 }
117
118 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
194const EARLY_EXIT_CHUNK: usize = 2048;
196
197fn 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
222fn 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#[inline]
255fn is_saturated(values: &[bool], cursor: &mut usize, referenced: bool) -> bool {
256 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
274pub 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 pub fn new(codes: ArrayRef, values: ArrayRef) -> Self {
311 Self::try_new(codes, values).vortex_expect("DictArray new")
312 }
313
314 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 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 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 #[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}