Skip to content

Commit 3d0c124

Browse files
authored
Dict: gather dictionary values straight into a VarBinBuilder (#9098)
Materialize dictionary values straight into VarBinBuilder instead of copying Signed-off-by: Robert Kruszewski <[email protected]> Signed-off-by: Robert Kruszewski <[email protected]>
1 parent 3d37216 commit 3d0c124

2 files changed

Lines changed: 153 additions & 62 deletions

File tree

‎vortex-array/src/arrays/dict/execute.rs‎

Lines changed: 51 additions & 59 deletions
Original file line numberDiff line numberDiff line change
@@ -5,11 +5,12 @@
55
66
use vortex_error::VortexExpect;
77
use vortex_error::VortexResult;
8+
use vortex_error::vortex_bail;
89

10+
use crate::ArrayView;
911
use crate::Canonical;
1012
use crate::CanonicalView;
1113
use crate::ExecutionCtx;
12-
use crate::IntoArray;
1314
use crate::arrays::Bool;
1415
use crate::arrays::BoolArray;
1516
use crate::arrays::Decimal;
@@ -20,6 +21,7 @@ use crate::arrays::FixedSizeList;
2021
use crate::arrays::FixedSizeListArray;
2122
use crate::arrays::ListView;
2223
use crate::arrays::ListViewArray;
24+
use crate::arrays::Null;
2325
use crate::arrays::NullArray;
2426
use crate::arrays::Primitive;
2527
use crate::arrays::PrimitiveArray;
@@ -38,148 +40,138 @@ use crate::arrays::variant::VariantArraySlotsExt;
3840
/// by looking up each code in the values array.
3941
pub(crate) fn take_canonical(
4042
values: CanonicalView,
41-
codes: &PrimitiveArray,
43+
codes: ArrayView<'_, Primitive>,
4244
ctx: &mut ExecutionCtx,
4345
) -> VortexResult<Canonical> {
44-
let values = Canonical::from(values);
4546
Ok(match values {
46-
Canonical::Null(a) => Canonical::Null(take_null(&a, codes)),
47-
Canonical::Bool(a) => Canonical::Bool(take_bool(&a, codes, ctx)?),
48-
Canonical::Primitive(a) => Canonical::Primitive(take_primitive(&a, codes, ctx)),
49-
Canonical::Decimal(a) => Canonical::Decimal(take_decimal(&a, codes, ctx)),
50-
Canonical::VarBinView(a) => Canonical::VarBinView(take_varbinview(&a, codes, ctx)),
51-
Canonical::List(a) => Canonical::List(take_listview(&a, codes, ctx)),
52-
Canonical::Map(_) => vortex_error::vortex_bail!("Map arrays don't support take"),
53-
Canonical::FixedSizeList(a) => {
54-
Canonical::FixedSizeList(take_fixed_size_list(&a, codes, ctx))
47+
CanonicalView::Null(a) => Canonical::Null(take_null(a, codes)),
48+
CanonicalView::Bool(a) => Canonical::Bool(take_bool(a, codes, ctx)?),
49+
CanonicalView::Primitive(a) => Canonical::Primitive(take_primitive(a, codes, ctx)),
50+
CanonicalView::Decimal(a) => Canonical::Decimal(take_decimal(a, codes, ctx)),
51+
CanonicalView::VarBinView(a) => Canonical::VarBinView(take_varbinview(a, codes, ctx)),
52+
CanonicalView::List(a) => Canonical::List(take_listview(a, codes, ctx)),
53+
CanonicalView::Map(_) => vortex_bail!("Map arrays don't support take"),
54+
CanonicalView::FixedSizeList(a) => {
55+
Canonical::FixedSizeList(take_fixed_size_list(a, codes, ctx))
5556
}
56-
Canonical::Struct(a) => Canonical::Struct(take_struct(&a, codes)),
57-
Canonical::Union(_) => {
57+
CanonicalView::Struct(a) => Canonical::Struct(take_struct(a, codes)),
58+
CanonicalView::Union(_) => {
5859
todo!(
5960
"TODO(connor)[Union]: implement dictionary execution after Union take supports \
6061
nullable indices and outer null propagation"
6162
)
6263
}
63-
Canonical::Extension(a) => Canonical::Extension(take_extension(&a, codes, ctx)),
64-
Canonical::Variant(a) => {
65-
let indices = codes.clone().into_array();
64+
CanonicalView::Extension(a) => Canonical::Extension(take_extension(a, codes, ctx)),
65+
CanonicalView::Variant(a) => {
66+
let indices = codes.array().clone();
6667
let taken_core_storage = a.core_storage().take(indices.clone())?;
6768
let taken_shredded = a
6869
.shredded()
69-
.map(|shredded| shredded.take(indices.clone()))
70+
.map(|shredded| shredded.take(indices))
7071
.transpose()?;
7172
Canonical::Variant(VariantArray::try_new(taken_core_storage, taken_shredded)?)
7273
}
7374
})
7475
}
7576

7677
/// Take for NullArray is trivial - just create a new NullArray with the new length.
77-
fn take_null(_array: &NullArray, codes: &PrimitiveArray) -> NullArray {
78+
fn take_null(_array: ArrayView<'_, Null>, codes: ArrayView<'_, Primitive>) -> NullArray {
7879
NullArray::new(codes.len())
7980
}
8081

81-
// TODO(joe): use dict_bool_take
8282
fn take_bool(
83-
array: &BoolArray,
84-
codes: &PrimitiveArray,
83+
array: ArrayView<'_, Bool>,
84+
codes: ArrayView<'_, Primitive>,
8585
ctx: &mut ExecutionCtx,
8686
) -> VortexResult<BoolArray> {
87-
let codes_ref = codes.clone().into_array();
88-
let array = array.as_view();
89-
Ok(<Bool as TakeExecute>::take(array, &codes_ref, ctx)?
87+
let codes_ref = codes.array();
88+
Ok(<Bool as TakeExecute>::take(array, codes_ref, ctx)?
9089
.vortex_expect("take bool should not return None")
9190
.as_::<Bool>()
9291
.into_owned())
9392
}
9493

9594
fn take_primitive(
96-
array: &PrimitiveArray,
97-
codes: &PrimitiveArray,
95+
array: ArrayView<'_, Primitive>,
96+
codes: ArrayView<'_, Primitive>,
9897
ctx: &mut ExecutionCtx,
9998
) -> PrimitiveArray {
100-
let codes_ref = codes.clone().into_array();
101-
let array = array.as_view();
102-
<Primitive as TakeExecute>::take(array, &codes_ref, ctx)
99+
let codes_ref = codes.array();
100+
<Primitive as TakeExecute>::take(array, codes_ref, ctx)
103101
.vortex_expect("take primitive array")
104102
.vortex_expect("take primitive should not return None")
105103
.as_::<Primitive>()
106104
.into_owned()
107105
}
108106

109107
fn take_decimal(
110-
array: &DecimalArray,
111-
codes: &PrimitiveArray,
108+
array: ArrayView<'_, Decimal>,
109+
codes: ArrayView<'_, Primitive>,
112110
ctx: &mut ExecutionCtx,
113111
) -> DecimalArray {
114-
let codes_ref = codes.clone().into_array();
115-
let array = array.as_view();
116-
<Decimal as TakeExecute>::take(array, &codes_ref, ctx)
112+
let codes_ref = codes.array();
113+
<Decimal as TakeExecute>::take(array, codes_ref, ctx)
117114
.vortex_expect("take decimal array")
118115
.vortex_expect("take decimal should not return None")
119116
.as_::<Decimal>()
120117
.into_owned()
121118
}
122119

123120
fn take_varbinview(
124-
array: &VarBinViewArray,
125-
codes: &PrimitiveArray,
121+
array: ArrayView<'_, VarBinView>,
122+
codes: ArrayView<'_, Primitive>,
126123
ctx: &mut ExecutionCtx,
127124
) -> VarBinViewArray {
128-
let codes_ref = codes.clone().into_array();
129-
let array = array.as_view();
130-
<VarBinView as TakeExecute>::take(array, &codes_ref, ctx)
125+
let codes_ref = codes.array();
126+
<VarBinView as TakeExecute>::take(array, codes_ref, ctx)
131127
.vortex_expect("take varbinview array")
132128
.vortex_expect("take varbinview should not return None")
133129
.as_::<VarBinView>()
134130
.into_owned()
135131
}
136132

137133
fn take_listview(
138-
array: &ListViewArray,
139-
codes: &PrimitiveArray,
134+
array: ArrayView<'_, ListView>,
135+
codes: ArrayView<'_, Primitive>,
140136
ctx: &mut ExecutionCtx,
141137
) -> ListViewArray {
142-
let codes_ref = codes.clone().into_array();
143-
let array = array.as_view();
144-
<ListView as TakeExecute>::take(array, &codes_ref, ctx)
138+
let codes_ref = codes.array();
139+
<ListView as TakeExecute>::take(array, codes_ref, ctx)
145140
.vortex_expect("take listview execute")
146141
.vortex_expect("ListView TakeExecute should not return None")
147142
.as_::<ListView>()
148143
.into_owned()
149144
}
150145

151146
fn take_fixed_size_list(
152-
array: &FixedSizeListArray,
153-
codes: &PrimitiveArray,
147+
array: ArrayView<'_, FixedSizeList>,
148+
codes: ArrayView<'_, Primitive>,
154149
ctx: &mut ExecutionCtx,
155150
) -> FixedSizeListArray {
156-
let codes_ref = codes.clone().into_array();
157-
let array = array.as_view();
158-
<FixedSizeList as TakeExecute>::take(array, &codes_ref, ctx)
151+
let codes_ref = codes.array();
152+
<FixedSizeList as TakeExecute>::take(array, codes_ref, ctx)
159153
.vortex_expect("take fixed size list array")
160154
.vortex_expect("take fixed size list should not return None")
161155
.as_::<FixedSizeList>()
162156
.into_owned()
163157
}
164158

165-
fn take_struct(array: &StructArray, codes: &PrimitiveArray) -> StructArray {
166-
let codes_ref = codes.clone().into_array();
167-
let array = array.as_view();
168-
<Struct as TakeReduce>::take(array, &codes_ref)
159+
fn take_struct(array: ArrayView<'_, Struct>, codes: ArrayView<'_, Primitive>) -> StructArray {
160+
let codes_ref = codes.array();
161+
<Struct as TakeReduce>::take(array, codes_ref)
169162
.vortex_expect("take struct array")
170163
.vortex_expect("take struct should not return None")
171164
.as_::<Struct>()
172165
.into_owned()
173166
}
174167

175168
fn take_extension(
176-
array: &ExtensionArray,
177-
codes: &PrimitiveArray,
169+
array: ArrayView<'_, Extension>,
170+
codes: ArrayView<'_, Primitive>,
178171
ctx: &mut ExecutionCtx,
179172
) -> ExtensionArray {
180-
let codes_ref = codes.clone().into_array();
181-
let array = array.as_view();
182-
<Extension as TakeExecute>::take(array, &codes_ref, ctx)
173+
let codes_ref = codes.array();
174+
<Extension as TakeExecute>::take(array, codes_ref, ctx)
183175
.vortex_expect("take extension storage")
184176
.vortex_expect("take extension should not return None")
185177
.as_::<Extension>()

‎vortex-array/src/arrays/dict/vtable/mod.rs‎

Lines changed: 102 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -3,13 +3,16 @@
33

44
use std::hash::Hasher;
55

6+
use num_traits::AsPrimitive;
67
use prost::Message;
78
use smallvec::smallvec;
89
use vortex_error::VortexResult;
910
use vortex_error::vortex_bail;
1011
use vortex_error::vortex_ensure;
1112
use vortex_error::vortex_err;
1213
use vortex_error::vortex_panic;
14+
use vortex_mask::AllOr;
15+
use vortex_mask::Mask;
1316
use vortex_session::VortexSession;
1417
use vortex_session::registry::CachedId;
1518

@@ -24,6 +27,7 @@ use crate::ArrayEq;
2427
use crate::ArrayHash;
2528
use crate::ArrayRef;
2629
use crate::Canonical;
30+
use crate::CanonicalView;
2731
use crate::EqMode;
2832
use crate::IntoArray;
2933
use crate::array::Array;
@@ -34,17 +38,22 @@ use crate::array::VTable;
3438
use crate::array::with_empty_buffers;
3539
use crate::arrays::ConstantArray;
3640
use crate::arrays::Primitive;
41+
use crate::arrays::VarBinView;
3742
use crate::arrays::dict::DictArrayExt;
3843
use crate::arrays::dict::DictArraySlotsExt;
3944
use crate::arrays::dict::compute::rules::PARENT_RULES;
4045
use crate::arrays::dict::execute::take_canonical;
4146
use crate::buffer::BufferHandle;
4247
use crate::builders::ArrayBuilder;
48+
use crate::builders::VarBinBuilder;
4349
use crate::dtype::DType;
4450
use crate::dtype::Nullability;
51+
use crate::dtype::OffsetBuilderPType;
4552
use crate::dtype::PType;
4653
use crate::executor::ExecutionCtx;
4754
use crate::executor::ExecutionResult;
55+
use crate::match_each_integer_ptype;
56+
use crate::match_each_varbin_builder;
4857
use crate::require_child;
4958
use crate::scalar::Scalar;
5059
use crate::serde::ArrayChildren;
@@ -205,7 +214,7 @@ impl VTable for Dict {
205214

206215
Ok(ExecutionResult::done(take_canonical(
207216
values.as_::<AnyCanonical>(),
208-
&codes.downcast::<Primitive>(),
217+
codes.as_::<Primitive>(),
209218
ctx,
210219
)?))
211220
}
@@ -222,8 +231,15 @@ impl VTable for Dict {
222231
)
223232
&& !codes.validity()?.definitely_all_null()
224233
{
225-
let codes = codes.into_owned();
226-
let canonical = take_canonical(values, &codes, ctx)?.into_array();
234+
if let CanonicalView::VarBinView(values) = values
235+
&& let Some(result) = match_each_varbin_builder!(builder, |builder| {
236+
let validity = array.validity()?.execute_mask(array.len(), ctx)?;
237+
append_dict_to_varbin(codes, values, validity, builder)
238+
})
239+
{
240+
return result;
241+
}
242+
let canonical = take_canonical(values, codes, ctx)?.into_array();
227243
canonical.append_to_builder(builder, ctx)?;
228244
return Ok(());
229245
}
@@ -245,3 +261,86 @@ impl VTable for Dict {
245261
PARENT_RULES.evaluate(array, parent, child_idx)
246262
}
247263
}
264+
265+
/// Gathers the dictionary values straight into `builder`.
266+
///
267+
/// The canonical route first takes the values to full logical length, which allocates and then
268+
/// re-reads a views buffer proportional to the row count. The dictionary is usually far smaller
269+
/// than the column, so resolving each code against it in place skips that intermediate entirely
270+
/// and leaves one `memcpy` per row as the only work.
271+
fn append_dict_to_varbin<O: OffsetBuilderPType>(
272+
codes: ArrayView<'_, Primitive>,
273+
values: ArrayView<'_, VarBinView>,
274+
validity: Mask,
275+
builder: &mut VarBinBuilder<O>,
276+
) -> VortexResult<()>
277+
where
278+
usize: AsPrimitive<O>,
279+
{
280+
let len = codes.as_ref().len();
281+
282+
// Resolve the dictionary's storage once so that looking up a code is an O(1) read.
283+
let views = values.views();
284+
let buffers = values
285+
.data_buffers()
286+
.iter()
287+
.map(|buffer| buffer.as_host().as_slice())
288+
.collect::<Vec<_>>();
289+
290+
match_each_integer_ptype!(codes.ptype(), |C| {
291+
let codes = codes.as_slice::<C>();
292+
let view = |row: usize| &views[AsPrimitive::<usize>::as_(codes[row])];
293+
294+
// Both passes below resolve a row through its code, so the byte total comes from the same
295+
// walk over the valid rows that the copy will make.
296+
let num_bytes = match validity.bit_buffer() {
297+
AllOr::All => (0..len).map(|row| view(row).len() as usize).sum(),
298+
AllOr::None => {
299+
builder.push_nulls(len);
300+
return Ok(());
301+
}
302+
AllOr::Some(bits) => {
303+
let mut total = 0;
304+
bits.for_each_set_index(|row| total += view(row).len() as usize);
305+
total
306+
}
307+
};
308+
309+
builder.append_valid_slices(num_bytes, &validity, |row| view(row).bytes(&buffers))
310+
})
311+
}
312+
313+
#[cfg(test)]
314+
mod tests {
315+
use super::*;
316+
use crate::VortexSessionExecute;
317+
use crate::array_session;
318+
use crate::arrays::PrimitiveArray;
319+
use crate::arrays::VarBinViewArray;
320+
use crate::arrays::dict::DictArray;
321+
use crate::assert_arrays_eq;
322+
use crate::dtype::Nullability::Nullable;
323+
324+
const LONG: &str = "a string that is far too long to be inlined in a view";
325+
326+
#[test]
327+
fn append_to_builder_gathers_through_the_dictionary() -> VortexResult<()> {
328+
let mut ctx = array_session().create_execution_ctx();
329+
let dict = DictArray::try_new(
330+
PrimitiveArray::from_option_iter([Some(0u32), Some(2), None, Some(1), Some(0)])
331+
.into_array(),
332+
VarBinViewArray::from_iter([Some(LONG), None, Some("short")], DType::Utf8(Nullable))
333+
.into_array(),
334+
)?;
335+
336+
let mut builder = VarBinBuilder::<i32>::new(DType::Utf8(Nullable));
337+
dict.append_to_builder(&mut builder, &mut ctx)?;
338+
339+
let expected = VarBinViewArray::from_iter(
340+
[Some(LONG), Some("short"), None, None, Some(LONG)],
341+
DType::Utf8(Nullable),
342+
);
343+
assert_arrays_eq!(builder.finish_into_varbin(), expected, &mut ctx);
344+
Ok(())
345+
}
346+
}

0 commit comments

Comments
 (0)