Skip to content

Commit 49c78ee

Browse files
perf: Optimize array_has() for array needle
`array_has(array, element)` returns, for each row, whether the array contains the element. When the `element` (needle) is an array rather than a scalar -- the needle argument is a column with one value per row, e.g. `array_has(t1.tags, t2.key)` in a join filter -- execution goes through `array_has_dispatch_for_array` (the `ColumnarValue::Array` needle branch), which compared each row by invoking the Arrow `eq` kernel once per row. That kernel allocates a `BooleanArray` and pays downcast and dispatch overhead on every row. (The scalar-needle branch was optimized separately in apache#20374.) Add a fast path for primitive and string element types, preserving the Arrow `eq` kernel semantics (total-order float equality; null elements never match). With all-valid elements each row is a single branchless OR-reduction over the native values. When primitive elements contain nulls -- whose backing values are arbitrary -- the per-element equality bitmap is ANDed with the validity bitmap (one word-parallel op, no per-element branch) before the per-row reduction, so null slots never match regardless of their value. Past a moderate average list length (`NULL_FAST_PATH_MAX_LEN`) this bitmap's extra passes lose to the per-row kernel, so the element-null branch bails to it there; that length is measured over the visible (sliced) region, so a sliced array's hidden child elements don't route a small window to the slow path. The all-valid fold has no such crossover. Nested and other element types keep using the per-row `eq` kernel. What this removes is the fixed per-row kernel overhead, not the element comparison itself, so the gain is largest for short lists and shrinks as lists grow. Criterion microbenchmark, array needle on a 100k-row batch vs the per-row `eq` kernel (NOT end-to-end query time): i64, all-valid elements: ~13x (64-elem lists), ~1.9x at 1024-elem i64, ~30% null elements: ~10x (8-elem) ... ~1x (512-elem); falls back beyond string elements: ~1.45x Every shape improves with no regression. End-to-end impact depends on how much of a query `array_has` accounts for. For a query dominated by an array-needle `array_has` join filter (a `NestedLoopJoinExec` with `filter=array_has(tags, key)` over 3000x3000 rows of 8-element lists) total time drops from 0.95s to 0.059s (~16x, identical results). For a workload where `array_has` is a smaller fraction -- e.g. the ~6% of profile that motivated this (see apache#18070 / apache#18161, which fixed the join's deep-copy but left the per-row `array_has` cost) -- the overall speedup is single-digit percent. Part of apache#18727. Co-Authored-By: Claude Opus 4.8 <[email protected]>
1 parent a0e9887 commit 49c78ee

2 files changed

Lines changed: 726 additions & 6 deletions

File tree

‎datafusion/functions-nested/benches/array_has.rs‎

Lines changed: 156 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -43,12 +43,14 @@ fn criterion_benchmark(c: &mut Criterion) {
4343

4444
for &size in &array_sizes {
4545
bench_array_has(c, size);
46+
bench_array_has_array(c, size);
4647
bench_array_has_all(c, size);
4748
bench_array_has_any(c, size);
4849
}
4950

5051
// Specific benchmarks for string arrays (common use case)
5152
bench_array_has_strings(c);
53+
bench_array_has_array_strings(c);
5254
bench_array_has_all_strings(c);
5355
bench_array_has_any_strings(c);
5456

@@ -119,6 +121,136 @@ fn bench_array_has(c: &mut Criterion, array_size: usize) {
119121
group.finish();
120122
}
121123

124+
/// Benchmarks array_has where the needle is an array (a column with one value
125+
/// per row) rather than a scalar.
126+
fn bench_array_has_array(c: &mut Criterion, array_size: usize) {
127+
let mut group = c.benchmark_group("array_has_array_i64");
128+
let haystack = create_int64_list_array(NUM_ROWS, array_size, NULL_DENSITY);
129+
let config_options = Arc::new(ConfigOptions::default());
130+
let return_field: Arc<Field> = Field::new("result", DataType::Boolean, true).into();
131+
let arg_fields: Vec<Arc<Field>> = vec![
132+
Field::new("arr", haystack.data_type().clone(), false).into(),
133+
Field::new("el", DataType::Int64, false).into(),
134+
];
135+
136+
// Needle values drawn from the same range as the haystack values, so many
137+
// rows find a match (and the inner loop can short-circuit).
138+
let needle_found = create_int64_value_array(NUM_ROWS, array_size as i64, 0);
139+
let args_found = vec![
140+
ColumnarValue::Array(haystack.clone()),
141+
ColumnarValue::Array(needle_found),
142+
];
143+
group.bench_with_input(
144+
BenchmarkId::new("found", array_size),
145+
&array_size,
146+
|b, _| {
147+
let udf = ArrayHas::new();
148+
b.iter(|| {
149+
black_box(
150+
udf.invoke_with_args(ScalarFunctionArgs {
151+
args: args_found.clone(),
152+
arg_fields: arg_fields.clone(),
153+
number_rows: NUM_ROWS,
154+
return_field: return_field.clone(),
155+
config_options: config_options.clone(),
156+
})
157+
.unwrap(),
158+
)
159+
})
160+
},
161+
);
162+
163+
// Needle values outside the haystack range: never matches, so every row
164+
// scans its full element list (worst case for the inner loop).
165+
let needle_not_found =
166+
create_int64_value_array(NUM_ROWS, array_size as i64, array_size as i64);
167+
let args_not_found = vec![
168+
ColumnarValue::Array(haystack.clone()),
169+
ColumnarValue::Array(needle_not_found),
170+
];
171+
group.bench_with_input(
172+
BenchmarkId::new("not_found", array_size),
173+
&array_size,
174+
|b, _| {
175+
let udf = ArrayHas::new();
176+
b.iter(|| {
177+
black_box(
178+
udf.invoke_with_args(ScalarFunctionArgs {
179+
args: args_not_found.clone(),
180+
arg_fields: arg_fields.clone(),
181+
number_rows: NUM_ROWS,
182+
return_field: return_field.clone(),
183+
config_options: config_options.clone(),
184+
})
185+
.unwrap(),
186+
)
187+
})
188+
},
189+
);
190+
191+
group.finish();
192+
}
193+
194+
fn bench_array_has_array_strings(c: &mut Criterion) {
195+
let mut group = c.benchmark_group("array_has_array_strings");
196+
let config_options = Arc::new(ConfigOptions::default());
197+
let return_field: Arc<Field> = Field::new("result", DataType::Boolean, true).into();
198+
199+
let sizes = vec![10, 100, 500];
200+
201+
for &size in &sizes {
202+
let haystack = create_string_list_array(NUM_ROWS, size, NULL_DENSITY);
203+
let arg_fields: Vec<Arc<Field>> = vec![
204+
Field::new("arr", haystack.data_type().clone(), false).into(),
205+
Field::new("el", DataType::Utf8, false).into(),
206+
];
207+
208+
let needle_found = create_string_value_array(NUM_ROWS, size, "value_");
209+
let args_found = vec![
210+
ColumnarValue::Array(haystack.clone()),
211+
ColumnarValue::Array(needle_found),
212+
];
213+
group.bench_with_input(BenchmarkId::new("found", size), &size, |b, _| {
214+
let udf = ArrayHas::new();
215+
b.iter(|| {
216+
black_box(
217+
udf.invoke_with_args(ScalarFunctionArgs {
218+
args: args_found.clone(),
219+
arg_fields: arg_fields.clone(),
220+
number_rows: NUM_ROWS,
221+
return_field: return_field.clone(),
222+
config_options: config_options.clone(),
223+
})
224+
.unwrap(),
225+
)
226+
})
227+
});
228+
229+
let needle_not_found = create_string_value_array(NUM_ROWS, size, "missing_");
230+
let args_not_found = vec![
231+
ColumnarValue::Array(haystack.clone()),
232+
ColumnarValue::Array(needle_not_found),
233+
];
234+
group.bench_with_input(BenchmarkId::new("not_found", size), &size, |b, _| {
235+
let udf = ArrayHas::new();
236+
b.iter(|| {
237+
black_box(
238+
udf.invoke_with_args(ScalarFunctionArgs {
239+
args: args_not_found.clone(),
240+
arg_fields: arg_fields.clone(),
241+
number_rows: NUM_ROWS,
242+
return_field: return_field.clone(),
243+
config_options: config_options.clone(),
244+
})
245+
.unwrap(),
246+
)
247+
})
248+
});
249+
}
250+
251+
group.finish();
252+
}
253+
122254
fn bench_array_has_all(c: &mut Criterion, array_size: usize) {
123255
let mut group = c.benchmark_group("array_has_all");
124256
let haystack = create_int64_list_array(NUM_ROWS, array_size, NULL_DENSITY);
@@ -659,6 +791,30 @@ fn create_int64_list_array(
659791
)
660792
}
661793

794+
/// Create an `Int64Array` of `num_rows` non-null values in `[offset, offset +
795+
/// range)`, used as an array needle for `array_has`.
796+
fn create_int64_value_array(num_rows: usize, range: i64, offset: i64) -> ArrayRef {
797+
let mut rng = StdRng::seed_from_u64(SEED + 2);
798+
let values = (0..num_rows)
799+
.map(|_| Some(rng.random_range(0..range) + offset))
800+
.collect::<Int64Array>();
801+
Arc::new(values)
802+
}
803+
804+
/// Create a `StringArray` of `num_rows` non-null values like "{prefix}{idx}"
805+
/// where `idx` is drawn from `[0, range)`, used as an array needle for
806+
/// `array_has`.
807+
fn create_string_value_array(num_rows: usize, range: usize, prefix: &str) -> ArrayRef {
808+
let mut rng = StdRng::seed_from_u64(SEED + 2);
809+
let values = (0..num_rows)
810+
.map(|_| {
811+
let idx = rng.random_range(0..range);
812+
Some(format!("{prefix}{idx}"))
813+
})
814+
.collect::<StringArray>();
815+
Arc::new(values)
816+
}
817+
662818
/// Like `create_int64_list_array` but values are offset so they won't
663819
/// appear in a standard list array (useful for "not found" benchmarks).
664820
fn create_int64_list_array_with_offset(

0 commit comments

Comments
 (0)