1use 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
67pub 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 .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 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 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
301fn 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
331fn 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 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 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 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 #[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 #[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}