This is an automated email from the ASF dual-hosted git repository.
github-merge-queue[bot] pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/datafusion.git
The following commit(s) were added to refs/heads/main by this push:
new ca028900cc perf: optimize `get_field` (#23537)
ca028900cc is described below
commit ca028900cc1d99a1caac4e7f0b73d7aac4d8d31c
Author: Andy Grove <[email protected]>
AuthorDate: Fri Jul 17 10:04:51 2026 -0600
perf: optimize `get_field` (#23537)
## Which issue does this PR close?
N/A
## Rationale for this change
Optimize existing function.
## What changes are included in this PR?
Removed the per-row `BooleanArray::slice` allocation in map key lookup
by scanning the key-comparison bitmap in place over each row's offset
range.
## Are these changes tested?
Existing tests.
Benchmark (criterion):
- get_field_map_1024_entries_16_last: 6.23% faster (base 42011ns -> cand
39394ns)
- get_field_map_1024_entries_4_missing: 12.267% faster (base 19070ns ->
cand 16730ns)
- get_field_map_8192_entries_4_last: 8.122% faster (base 168450ns ->
cand 154769ns)
- get_field_map_1024_entries_4_last: 11.166% faster (base 23229ns ->
cand 20635ns)
- get_field_map_1024_entries_4_first: 15.396% faster (base 20877ns ->
cand 17663ns)
Full criterion output:
```text
get_field_map_1024_entries_4_first
time: [17.664 µs 17.701 µs 17.756 µs]
change: [−15.807% −15.396% −14.964%] (p = 0.00 <
0.05)
Performance has improved.
Found 6 outliers among 100 measurements (6.00%)
4 (4.00%) high mild
2 (2.00%) high severe
get_field_map_1024_entries_4_last
time: [20.450 µs 20.499 µs 20.546 µs]
change: [−11.535% −11.166% −10.793%] (p = 0.00 <
0.05)
Performance has improved.
Found 6 outliers among 100 measurements (6.00%)
2 (2.00%) low mild
4 (4.00%) high mild
get_field_map_1024_entries_16_last
time: [39.406 µs 39.460 µs 39.516 µs]
change: [−6.9089% −6.2297% −5.5570%] (p = 0.00 <
0.05)
Performance has improved.
Found 11 outliers among 100 measurements (11.00%)
6 (6.00%) low severe
2 (2.00%) high mild
3 (3.00%) high severe
get_field_map_1024_entries_4_missing
time: [16.755 µs 16.775 µs 16.796 µs]
change: [−12.675% −12.267% −11.888%] (p = 0.00 <
0.05)
Performance has improved.
Found 6 outliers among 100 measurements (6.00%)
4 (4.00%) high mild
2 (2.00%) high severe
get_field_map_8192_entries_4_last
time: [154.23 µs 154.92 µs 155.72 µs]
change: [−8.5962% −8.1217% −7.6240%] (p = 0.00 <
0.05)
Performance has improved.
Found 12 outliers among 100 measurements (12.00%)
11 (11.00%) high mild
1 (1.00%) high severe
```
## Are there any user-facing changes?
No
<!--
If there are user-facing changes then we may require documentation to be
updated before approving the PR.
-->
<!--
If there are any breaking changes to public APIs, please add the `api
change` label.
-->
---
datafusion/functions/Cargo.toml | 4 ++
datafusion/functions/benches/get_field.rs | 95 +++++++++++++++++++++++++++++++
datafusion/functions/src/core/getfield.rs | 24 ++++----
3 files changed, 111 insertions(+), 12 deletions(-)
diff --git a/datafusion/functions/Cargo.toml b/datafusion/functions/Cargo.toml
index d31a83e598..d2fe027350 100644
--- a/datafusion/functions/Cargo.toml
+++ b/datafusion/functions/Cargo.toml
@@ -350,6 +350,10 @@ harness = false
name = "regexp_count"
required-features = ["regex_expressions"]
+[[bench]]
+harness = false
+name = "get_field"
+
[[bench]]
harness = false
name = "crypto"
diff --git a/datafusion/functions/benches/get_field.rs
b/datafusion/functions/benches/get_field.rs
new file mode 100644
index 0000000000..8a5fd0a1e2
--- /dev/null
+++ b/datafusion/functions/benches/get_field.rs
@@ -0,0 +1,95 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+extern crate criterion;
+
+use arrow::array::{ArrayRef, Int32Builder, MapBuilder, StringBuilder};
+use arrow::datatypes::{DataType, Field};
+use criterion::{Criterion, criterion_group, criterion_main};
+use datafusion_common::ScalarValue;
+use datafusion_common::config::ConfigOptions;
+use datafusion_expr::{ColumnarValue, ScalarFunctionArgs};
+use datafusion_functions::core::get_field;
+use std::hint::black_box;
+use std::sync::Arc;
+
+/// A map array with `size` rows, each holding `entries` key/value pairs.
+/// Every tenth row is null.
+fn map_array(size: usize, entries: usize) -> ArrayRef {
+ let mut builder = MapBuilder::new(None, StringBuilder::new(),
Int32Builder::new());
+ for row in 0..size {
+ if row % 10 == 0 {
+ builder.append(false).unwrap();
+ continue;
+ }
+ for entry in 0..entries {
+ builder.keys().append_value(format!("key_{entry}"));
+ builder.values().append_value((row * entry) as i32);
+ }
+ builder.append(true).unwrap();
+ }
+ Arc::new(builder.finish())
+}
+
+fn bench_get_field(
+ c: &mut Criterion,
+ name: &str,
+ size: usize,
+ entries: usize,
+ key: &str,
+) {
+ let udf = get_field();
+ let args = vec![
+ ColumnarValue::Array(map_array(size, entries)),
+ ColumnarValue::Scalar(ScalarValue::Utf8(Some(key.to_string()))),
+ ];
+ let arg_fields = vec![
+ Field::new("map", args[0].data_type(), true).into(),
+ Field::new("key", DataType::Utf8, false).into(),
+ ];
+ let config_options = Arc::new(ConfigOptions::default());
+
+ c.bench_function(name, |b| {
+ b.iter(|| {
+ black_box(
+ udf.invoke_with_args(ScalarFunctionArgs {
+ args: args.clone(),
+ arg_fields: arg_fields.clone(),
+ number_rows: size,
+ return_field: Field::new("f", DataType::Int32,
true).into(),
+ config_options: Arc::clone(&config_options),
+ })
+ .unwrap(),
+ )
+ })
+ });
+}
+
+fn criterion_benchmark(c: &mut Criterion) {
+ // First key: the match is found immediately, so the per-row overhead
+ // dominates.
+ bench_get_field(c, "get_field_map_1024_entries_4_first", 1024, 4, "key_0");
+ // Last key: every entry of the row is compared before the match.
+ bench_get_field(c, "get_field_map_1024_entries_4_last", 1024, 4, "key_3");
+ bench_get_field(c, "get_field_map_1024_entries_16_last", 1024, 16,
"key_15");
+ // Key that is not present in any row.
+ bench_get_field(c, "get_field_map_1024_entries_4_missing", 1024, 4,
"key_9");
+ bench_get_field(c, "get_field_map_8192_entries_4_last", 8192, 4, "key_3");
+}
+
+criterion_group!(benches, criterion_benchmark);
+criterion_main!(benches);
diff --git a/datafusion/functions/src/core/getfield.rs
b/datafusion/functions/src/core/getfield.rs
index 70fc8bb0ea..6ec874fb67 100644
--- a/datafusion/functions/src/core/getfield.rs
+++ b/datafusion/functions/src/core/getfield.rs
@@ -129,22 +129,22 @@ fn process_map_array(
let mut mutable =
MutableArrayData::with_capacities(vec![&original_data], true,
capacity);
+ let offsets = map_array.value_offsets();
+ // Scan the comparison result in place: slicing it per entry would allocate
+ // a new array for every row of the map. Map keys are non-null by
+ // definition, so the comparison result carries no nulls to check here.
+ let matches = keys.values();
+
for entry in 0..map_array.len() {
- let start = map_array.value_offsets()[entry] as usize;
- let end = map_array.value_offsets()[entry + 1] as usize;
+ let start = offsets[entry] as usize;
+ let end = offsets[entry + 1] as usize;
- let maybe_matched = keys
- .slice(start, end - start)
- .iter()
- .enumerate()
- .find(|(_, t)| t.unwrap());
+ let matched = (start..end).find(|&i| matches.value(i));
- if maybe_matched.is_none() {
- mutable.try_extend_nulls(1)?;
- continue;
+ match matched {
+ Some(i) => mutable.try_extend(0, i, i + 1)?,
+ None => mutable.try_extend_nulls(1)?,
}
- let (match_offset, _) = maybe_matched.unwrap();
- mutable.try_extend(0, start + match_offset, start + match_offset + 1)?;
}
let data = mutable.freeze();
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
