This is an automated email from the ASF dual-hosted git repository. github-merge-queue[bot] pushed a commit to branch gh-readonly-queue/main/pr-23537-b16bd3d874a9e11877d7aa4e59e8845ff576c430 in repository https://gitbox.apache.org/repos/asf/datafusion.git
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]
