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::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
66pub 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 .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
276fn 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
306fn 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 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 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 #[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 #[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}