Skip to content

Commit b33a1c0

Browse files
committed
perf, chore: Consolidate and optimize get_field and map_extract
`map[key]` (aka `get_field`) and `map_extract(map, key)` collectively had three ways to lookup keys in a map: (1): `get_field` used a per-batch `eq` kernel for scalar keys. This is efficient for maps with many entries where `key` is not found, but slower for maps in which the key can be found quickly (because `eq` does not allow early-stopping). On my local machine, `eq` only beats a comparator-based approach if the latter required touching more than 60% of the keys in a row. (2): `get_field` used a comparator-based approach for nested keys. (3): `map_extract` used a comparator-based approach for all keys. Conceptually, these two functions only differ in how the result is represented, so it makes sense to consolidate them. We can also adopt a hybrid strategy that gets the best of the previous approaches for most inputs: * Start with a comparator-based approach. * After the first row, remember the index at which the matching key was found, and check that index first for subsequent rows. This takes advantage of the observation that most map rows have their keys in the same order. * After 32 rows, check whether the comparator looked at more than 75% of the entries in those rows. If it did, the early stopping that the comparator approach allows is not useful and we switch to an `eq` kernel for the remainder of the batch (as long as the map key is not a nested type). Add `datafusion_functions::utils::map_lookup`, which returns for each map row the index of the first matching entry or null, and build both functions on it with `take`. The lookup scans each row with a comparator, which stops at the first match, and tries the position where the previous row matched first, since rows in a batch usually share key order; a hit then usually costs one comparison wherever the key sits. A miss has no match to stop at, so every entry of the row is compared at the comparator's higher per-comparison cost. After sampling 32 rows, if most of them missed, the remaining entries are compared with one vectorized `eq` instead, which does the same full comparison more cheaply. A lookup key that differs from the map key type only in dictionary encoding is cast rather than rejected. `map_extract` now passes a scalar key through as a single row instead of expanding it to the batch size. `map[key]` reports a mismatched key type as an execution error instead of an Arrow comparison error, and a null map row that still carries entries yields NULL, as it already did from `map_extract`. Closes apache#25083
1 parent d029ea1 commit b33a1c0

4 files changed

Lines changed: 469 additions & 212 deletions

File tree

‎datafusion/functions-nested/src/map_extract.rs‎

Lines changed: 30 additions & 72 deletions
Original file line numberDiff line numberDiff line change
@@ -17,20 +17,19 @@
1717

1818
//! [`ScalarUDFImpl`] definitions for map_extract functions.
1919
20-
use crate::utils::{get_map_entry_field, make_scalar_function};
21-
use arrow::array::{
22-
Array, ArrayRef, ListArray, MapArray, MutableArrayData, make_array, new_empty_array,
23-
};
20+
use crate::utils::get_map_entry_field;
21+
use arrow::array::{Array, ArrayRef, ListArray, MapArray, UInt32Array};
2422
use arrow::buffer::OffsetBuffer;
25-
use arrow::compute::SortOptions;
23+
use arrow::compute::take;
2624
use arrow::datatypes::{DataType, Field};
27-
use arrow_ord::ord::make_comparator;
2825
use datafusion_common::utils::take_function_args;
2926
use datafusion_common::{Result, cast::as_map_array, exec_err};
27+
use datafusion_expr::function::Hint;
3028
use datafusion_expr::{
3129
ColumnarValue, Documentation, ScalarFunctionArgs, ScalarUDFImpl, Signature,
3230
Volatility,
3331
};
32+
use datafusion_functions::utils::{make_scalar_function, map_lookup};
3433
use datafusion_macros::user_doc;
3534
use std::sync::Arc;
3635

@@ -119,7 +118,11 @@ impl ScalarUDFImpl for MapExtract {
119118
}
120119

121120
fn invoke_with_args(&self, args: ScalarFunctionArgs) -> Result<ColumnarValue> {
122-
make_scalar_function(map_extract_inner)(&args.args)
121+
// A scalar key is passed through as a single row rather than expanded
122+
// to the batch size; the lookup applies it to every map row.
123+
make_scalar_function(map_extract_inner, vec![Hint::Pad, Hint::AcceptsSingular])(
124+
&args.args,
125+
)
123126
}
124127

125128
fn aliases(&self) -> &[String] {
@@ -149,79 +152,34 @@ fn general_map_extract_inner(
149152
map_array: &MapArray,
150153
query_keys_array: &dyn Array,
151154
) -> Result<ArrayRef> {
152-
let keys = map_array.keys();
153-
let values = map_array.values();
154-
let field = Arc::new(Field::new_list_field(map_array.value_type().clone(), true));
155-
let map_offsets = map_array.value_offsets();
156-
if map_offsets.first() == map_offsets.last() {
157-
return Ok(Arc::new(ListArray::new(
158-
field,
159-
OffsetBuffer::new_zeroed(map_array.len()),
160-
new_empty_array(values.data_type()),
161-
map_array.nulls().cloned(),
162-
)));
163-
}
164-
165-
// Compare keys by index using a single comparator for the batch.
166-
let compare =
167-
make_comparator(keys.as_ref(), query_keys_array, SortOptions::default())?;
168-
let mut offsets = Vec::with_capacity(map_array.len() + 1);
169-
offsets.push(0_i32);
170-
171-
let original_data = values.to_data();
172-
// There is at most one output value per map row.
173-
let mut mutable = MutableArrayData::new(
174-
vec![&original_data],
175-
false,
176-
map_array.len().min(values.len()),
177-
);
178-
179-
for (row_index, offset_window) in map_offsets.windows(2).enumerate() {
180-
let start = offset_window[0] as usize;
181-
let end = offset_window[1] as usize;
182-
let mut offset = offsets[row_index];
183-
184-
if map_array.is_valid(row_index)
185-
&& let Some(index) = (start..end).find(|&i| compare(i, row_index).is_eq())
186-
{
187-
mutable.try_extend(0, index, index + 1)?;
188-
offset += 1;
189-
}
190-
191-
// A missing key results in an empty list.
192-
offsets.push(offset);
193-
}
194-
195-
let data = mutable.freeze();
196-
155+
let indices = map_lookup(map_array, query_keys_array)?;
156+
// Each matched row contributes one list element. Every other row is an
157+
// empty list, or NULL when the map itself is NULL.
158+
let lengths = indices.iter().map(|index| usize::from(index.is_some()));
159+
let mut matched = Vec::with_capacity(indices.len() - indices.null_count());
160+
matched.extend(indices.iter().flatten());
161+
let values = take(
162+
map_array.values().as_ref(),
163+
&UInt32Array::from(matched),
164+
None,
165+
)?;
197166
Ok(Arc::new(ListArray::new(
198-
field,
199-
OffsetBuffer::<i32>::new(offsets.into()),
200-
make_array(data),
167+
Arc::new(Field::new_list_field(map_array.value_type().clone(), true)),
168+
OffsetBuffer::from_lengths(lengths),
169+
values,
201170
map_array.nulls().cloned(),
202171
)))
203172
}
204173

205174
fn map_extract_inner(args: &[ArrayRef]) -> Result<ArrayRef> {
206175
let [map_arg, key_arg] = take_function_args("map_extract", args)?;
207-
208-
let map_array = match map_arg.data_type() {
209-
DataType::Map(_, _) => as_map_array(&map_arg)?,
210-
DataType::Null => return Ok(Arc::clone(map_arg)),
211-
_ => return exec_err!("The first argument in map_extract must be a map"),
212-
};
213-
214-
let key_type = map_array.key_type();
215-
216-
if key_type != key_arg.data_type() {
217-
return exec_err!(
218-
"The key type {} does not match the map key type {}",
219-
key_arg.data_type(),
220-
key_type
221-
);
176+
match map_arg.data_type() {
177+
DataType::Map(_, _) => {
178+
general_map_extract_inner(as_map_array(map_arg.as_ref())?, key_arg.as_ref())
179+
}
180+
DataType::Null => Ok(Arc::clone(map_arg)),
181+
_ => exec_err!("The first argument in map_extract must be a map"),
222182
}
223-
224-
general_map_extract_inner(map_array, key_arg)
225183
}
226184

227185
#[cfg(test)]

‎datafusion/functions/src/core/getfield.rs‎

Lines changed: 10 additions & 136 deletions
Original file line numberDiff line numberDiff line change
@@ -17,11 +17,8 @@
1717

1818
use std::sync::{Arc, OnceLock};
1919

20-
use arrow::array::{
21-
Array, Capacities, MutableArrayData, Scalar, cast::AsArray, make_array,
22-
make_comparator,
23-
};
24-
use arrow::compute::SortOptions;
20+
use arrow::array::{Array, cast::AsArray};
21+
use arrow::compute::take;
2522
use arrow::datatypes::{DataType, Field, FieldRef};
2623

2724
use datafusion_common::cast::{as_map_array, as_struct_array};
@@ -38,6 +35,7 @@ use datafusion_macros::user_doc;
3835

3936
use super::named_struct::NamedStructFunc;
4037
use super::r#struct::StructFunc;
38+
use crate::utils::map_lookup;
4139

4240
#[user_doc(
4341
doc_section(label = "Other Functions"),
@@ -99,89 +97,6 @@ impl Default for GetFieldFunc {
9997
}
10098
}
10199

102-
/// Process a map array with a non-nested key type by comparing the single
103-
/// lookup key against every map key with the `eq` kernel, then scanning the
104-
/// result for each row.
105-
///
106-
/// `eq` does not support nested types, so list, struct, and map keys go
107-
/// through [`process_map_with_nested_key`] instead.
108-
fn process_map_array(
109-
array: &dyn Array,
110-
key_array: Arc<dyn Array>,
111-
) -> Result<ColumnarValue> {
112-
let map_array = as_map_array(array)?;
113-
let be_compared = Scalar::new(key_array);
114-
let keys = arrow::compute::kernels::cmp::eq(&be_compared, map_array.keys())?;
115-
116-
let original_data = map_array.entries().column(1).to_data();
117-
let capacity = Capacities::Array(original_data.len());
118-
let mut mutable =
119-
MutableArrayData::with_capacities(vec![&original_data], true, capacity);
120-
121-
let offsets = map_array.value_offsets();
122-
// Scan the comparison result in place: slicing it per entry would allocate
123-
// a new array for every row of the map. Map keys are non-null by
124-
// definition, so the comparison result carries no nulls to check here.
125-
let matches = keys.values();
126-
127-
for entry in 0..map_array.len() {
128-
let start = offsets[entry] as usize;
129-
let end = offsets[entry + 1] as usize;
130-
131-
let matched = (start..end).find(|&i| matches.value(i));
132-
133-
match matched {
134-
Some(i) => mutable.try_extend(0, i, i + 1)?,
135-
None => mutable.try_extend_nulls(1)?,
136-
}
137-
}
138-
139-
let data = mutable.freeze();
140-
let data = make_array(data);
141-
Ok(ColumnarValue::Array(data))
142-
}
143-
144-
/// Process a map array with a nested key type by iterating through entries
145-
/// and using a comparator for key matching.
146-
///
147-
/// This specialized version is used when the key type is nested (e.g., struct, list).
148-
fn process_map_with_nested_key(
149-
array: &dyn Array,
150-
key_array: &dyn Array,
151-
) -> Result<ColumnarValue> {
152-
let map_array = as_map_array(array)?;
153-
154-
let comparator =
155-
make_comparator(map_array.keys().as_ref(), key_array, SortOptions::default())?;
156-
157-
let original_data = map_array.entries().column(1).to_data();
158-
let capacity = Capacities::Array(original_data.len());
159-
let mut mutable =
160-
MutableArrayData::with_capacities(vec![&original_data], true, capacity);
161-
162-
for entry in 0..map_array.len() {
163-
let start = map_array.value_offsets()[entry] as usize;
164-
let end = map_array.value_offsets()[entry + 1] as usize;
165-
166-
let mut found_match = false;
167-
for i in start..end {
168-
if comparator(i, 0).is_eq() {
169-
mutable.try_extend(0, i, i + 1)?;
170-
found_match = true;
171-
break;
172-
}
173-
}
174-
175-
if !found_match {
176-
mutable.try_extend_nulls(1)?;
177-
}
178-
}
179-
180-
let data = mutable.freeze();
181-
let data = make_array(data);
182-
Ok(ColumnarValue::Array(data))
183-
}
184-
185100
/// Extract a single field from a struct or map array
186101
fn extract_single_field(base: ColumnarValue, name: ScalarValue) -> Result<ColumnarValue> {
187102
let arrays = ColumnarValue::values_to_arrays(&[base])?;
@@ -209,14 +124,11 @@ fn extract_single_field(base: ColumnarValue, name: ScalarValue) -> Result<Column
209124
))
210125
}
211126
(DataType::Map(_, _), key, _) => {
212-
// The lookup key is a single scalar. `eq` does not support nested
213-
// key types, so those are matched with a comparator instead.
214-
let key_array = key.to_array()?;
215-
if key_array.data_type().is_nested() {
216-
process_map_with_nested_key(&array, key_array.as_ref())
217-
} else {
218-
process_map_array(&array, key_array)
219-
}
127+
// The lookup key is a single scalar
128+
let map_array = as_map_array(array.as_ref())?;
129+
let indices = map_lookup(map_array, key.to_array()?.as_ref())?;
130+
let values = take(map_array.values().as_ref(), &indices, None)?;
131+
Ok(ColumnarValue::Array(values))
220132
}
221133
(DataType::Struct(_), _, Some(k)) => {
222134
let as_struct_array = as_struct_array(&array)?;
@@ -656,11 +568,8 @@ impl ScalarUDFImpl for GetFieldFunc {
656568
#[cfg(test)]
657569
mod tests {
658570
use super::*;
659-
use arrow::array::{
660-
ArrayRef, Int32Array, Int32Builder, ListArray, ListBuilder, MapBuilder,
661-
StructArray,
662-
};
663-
use arrow::datatypes::{Fields, Int32Type};
571+
use arrow::array::{ArrayRef, Int32Array, StructArray};
572+
use arrow::datatypes::Fields;
664573

665574
#[test]
666575
fn test_get_field_utf8view_key() -> Result<()> {
@@ -698,41 +607,6 @@ mod tests {
698607
Ok(())
699608
}
700609

701-
#[test]
702-
fn test_get_field_map_list_key() -> Result<()> {
703-
// One map row with two list keys. The lookup key matches the second
704-
// entry, so the match is not at the first entry of the row.
705-
let mut builder = MapBuilder::new(
706-
None,
707-
ListBuilder::new(Int32Builder::new()),
708-
Int32Builder::new(),
709-
);
710-
builder.keys().append_value([Some(1), Some(2)]);
711-
builder.values().append_value(1);
712-
builder.keys().append_value([Some(3), Some(4)]);
713-
builder.values().append_value(2);
714-
builder.append(true)?;
715-
let base = ColumnarValue::Array(Arc::new(builder.finish()));
716-
717-
let list_key = |values: Vec<i32>| {
718-
ScalarValue::List(Arc::new(
719-
ListArray::from_iter_primitive::<Int32Type, _, _>([Some(
720-
values.into_iter().map(Some),
721-
)]),
722-
))
723-
};
724-
725-
let result = extract_single_field(base.clone(), list_key(vec![3, 4]))?;
726-
let expected = Int32Array::from(vec![Some(2)]);
727-
assert_eq!(result.into_array(1)?.as_ref(), &expected as &dyn Array);
728-
729-
let result = extract_single_field(base, list_key(vec![9, 9]))?;
730-
let expected = Int32Array::from(vec![None]);
731-
assert_eq!(result.into_array(1)?.as_ref(), &expected as &dyn Array);
732-
733-
Ok(())
734-
}
735-
736610
#[test]
737611
fn test_get_field_dict_encoded_struct() -> Result<()> {
738612
use arrow::array::{DictionaryArray, StringArray, UInt32Array};

0 commit comments

Comments
 (0)