Skip to content

Commit 87cf1b4

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 c884d40 commit 87cf1b4

2 files changed

Lines changed: 864 additions & 6 deletions

File tree

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

Lines changed: 294 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -43,17 +43,157 @@ 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

5557
// Benchmark for array_has_any with one scalar arg
5658
bench_array_has_any_scalar(c);
59+
60+
// Array-needle fast-path profile: null patterns, list length, row height.
61+
bench_array_has_array_null_patterns(c);
62+
bench_array_has_array_by_size(c);
63+
bench_array_has_array_by_rows(c);
64+
}
65+
66+
/// Invoke `array_has` once with an array (column) needle -- exercises the
67+
/// `array_has_dispatch_for_array` fast path.
68+
fn run_array_needle_case(
69+
group: &mut criterion::BenchmarkGroup<'_, criterion::measurement::WallTime>,
70+
id: String,
71+
haystack: ArrayRef,
72+
needle: ArrayRef,
73+
rows: usize,
74+
) {
75+
let config_options = Arc::new(ConfigOptions::default());
76+
let return_field: Arc<Field> = Field::new("result", DataType::Boolean, true).into();
77+
let arg_fields: Vec<Arc<Field>> = vec![
78+
Field::new("arr", haystack.data_type().clone(), false).into(),
79+
Field::new("el", needle.data_type().clone(), false).into(),
80+
];
81+
let args = vec![ColumnarValue::Array(haystack), ColumnarValue::Array(needle)];
82+
group.bench_function(id, |b| {
83+
let udf = ArrayHas::new();
84+
b.iter(|| {
85+
black_box(
86+
udf.invoke_with_args(ScalarFunctionArgs {
87+
args: args.clone(),
88+
arg_fields: arg_fields.clone(),
89+
number_rows: rows,
90+
return_field: return_field.clone(),
91+
config_options: config_options.clone(),
92+
})
93+
.unwrap(),
94+
)
95+
});
96+
});
97+
}
98+
99+
/// Array needle, fixed list length (64), across null patterns for i64 and
100+
/// string element types. `not_found` shifts the needle out of the value range;
101+
/// `collision` uses an all-null list with needle 0 (a null slot's backing fill
102+
/// must not count as a match).
103+
fn bench_array_has_array_null_patterns(c: &mut Criterion) {
104+
let (rows, size) = (10_000usize, 64usize);
105+
let s = size as i64;
106+
let mut group = c.benchmark_group("array_has_array_null_patterns");
107+
run_array_needle_case(
108+
&mut group,
109+
"i64/no_nulls".to_string(),
110+
create_int64_list_array(rows, size, 0.0),
111+
create_int64_value_array(rows, s, 0),
112+
rows,
113+
);
114+
run_array_needle_case(
115+
&mut group,
116+
"i64/nulls30_found".to_string(),
117+
create_int64_list_array(rows, size, 0.3),
118+
create_int64_value_array(rows, s, 0),
119+
rows,
120+
);
121+
run_array_needle_case(
122+
&mut group,
123+
"i64/nulls30_not_found".to_string(),
124+
create_int64_list_array(rows, size, 0.3),
125+
create_int64_value_array(rows, s, s),
126+
rows,
127+
);
128+
run_array_needle_case(
129+
&mut group,
130+
"i64/all_null".to_string(),
131+
create_int64_list_array(rows, size, 1.0),
132+
create_int64_value_array(rows, s, 0),
133+
rows,
134+
);
135+
run_array_needle_case(
136+
&mut group,
137+
"i64/collision".to_string(),
138+
create_int64_list_array(rows, size, 1.0),
139+
create_int64_value_array(rows, 1, 0),
140+
rows,
141+
);
142+
run_array_needle_case(
143+
&mut group,
144+
"string/no_nulls".to_string(),
145+
create_string_list_array(rows, size, 0.0),
146+
create_string_value_array(rows, size, "value_"),
147+
rows,
148+
);
149+
run_array_needle_case(
150+
&mut group,
151+
"string/nulls30".to_string(),
152+
create_string_list_array(rows, size, 0.3),
153+
create_string_value_array(rows, size, "value_"),
154+
rows,
155+
);
156+
run_array_needle_case(
157+
&mut group,
158+
"string/all_null".to_string(),
159+
create_string_list_array(rows, size, 1.0),
160+
create_string_value_array(rows, size, "value_"),
161+
rows,
162+
);
163+
group.finish();
164+
}
165+
166+
/// Array needle, i64, 30% element nulls, not found, across list lengths.
167+
fn bench_array_has_array_by_size(c: &mut Criterion) {
168+
let rows = 10_000usize;
169+
let mut group = c.benchmark_group("array_has_array_by_size");
170+
for size in [8usize, 32, 128, 256, 512, 1024] {
171+
let s = size as i64;
172+
run_array_needle_case(
173+
&mut group,
174+
size.to_string(),
175+
create_int64_list_array(rows, size, 0.3),
176+
create_int64_value_array(rows, s, s),
177+
rows,
178+
);
179+
}
180+
group.finish();
181+
}
182+
183+
/// Array needle, i64, 8 elems/row, 30% nulls, not found, across row counts.
184+
fn bench_array_has_array_by_rows(c: &mut Criterion) {
185+
let (size, s) = (8usize, 8i64);
186+
let mut group = c.benchmark_group("array_has_array_by_rows");
187+
for rows in [10_000usize, 100_000, 1_000_000] {
188+
run_array_needle_case(
189+
&mut group,
190+
rows.to_string(),
191+
create_int64_list_array(rows, size, 0.3),
192+
create_int64_value_array(rows, s, s),
193+
rows,
194+
);
195+
}
196+
group.finish();
57197
}
58198

59199
fn bench_array_has(c: &mut Criterion, array_size: usize) {
@@ -119,6 +259,136 @@ fn bench_array_has(c: &mut Criterion, array_size: usize) {
119259
group.finish();
120260
}
121261

262+
/// Benchmarks array_has where the needle is an array (a column with one value
263+
/// per row) rather than a scalar.
264+
fn bench_array_has_array(c: &mut Criterion, array_size: usize) {
265+
let mut group = c.benchmark_group("array_has_array_i64");
266+
let haystack = create_int64_list_array(NUM_ROWS, array_size, NULL_DENSITY);
267+
let config_options = Arc::new(ConfigOptions::default());
268+
let return_field: Arc<Field> = Field::new("result", DataType::Boolean, true).into();
269+
let arg_fields: Vec<Arc<Field>> = vec![
270+
Field::new("arr", haystack.data_type().clone(), false).into(),
271+
Field::new("el", DataType::Int64, false).into(),
272+
];
273+
274+
// Needle values drawn from the same range as the haystack values, so many
275+
// rows find a match (and the inner loop can short-circuit).
276+
let needle_found = create_int64_value_array(NUM_ROWS, array_size as i64, 0);
277+
let args_found = vec![
278+
ColumnarValue::Array(haystack.clone()),
279+
ColumnarValue::Array(needle_found),
280+
];
281+
group.bench_with_input(
282+
BenchmarkId::new("found", array_size),
283+
&array_size,
284+
|b, _| {
285+
let udf = ArrayHas::new();
286+
b.iter(|| {
287+
black_box(
288+
udf.invoke_with_args(ScalarFunctionArgs {
289+
args: args_found.clone(),
290+
arg_fields: arg_fields.clone(),
291+
number_rows: NUM_ROWS,
292+
return_field: return_field.clone(),
293+
config_options: config_options.clone(),
294+
})
295+
.unwrap(),
296+
)
297+
})
298+
},
299+
);
300+
301+
// Needle values outside the haystack range: never matches, so every row
302+
// scans its full element list (worst case for the inner loop).
303+
let needle_not_found =
304+
create_int64_value_array(NUM_ROWS, array_size as i64, array_size as i64);
305+
let args_not_found = vec![
306+
ColumnarValue::Array(haystack.clone()),
307+
ColumnarValue::Array(needle_not_found),
308+
];
309+
group.bench_with_input(
310+
BenchmarkId::new("not_found", array_size),
311+
&array_size,
312+
|b, _| {
313+
let udf = ArrayHas::new();
314+
b.iter(|| {
315+
black_box(
316+
udf.invoke_with_args(ScalarFunctionArgs {
317+
args: args_not_found.clone(),
318+
arg_fields: arg_fields.clone(),
319+
number_rows: NUM_ROWS,
320+
return_field: return_field.clone(),
321+
config_options: config_options.clone(),
322+
})
323+
.unwrap(),
324+
)
325+
})
326+
},
327+
);
328+
329+
group.finish();
330+
}
331+
332+
fn bench_array_has_array_strings(c: &mut Criterion) {
333+
let mut group = c.benchmark_group("array_has_array_strings");
334+
let config_options = Arc::new(ConfigOptions::default());
335+
let return_field: Arc<Field> = Field::new("result", DataType::Boolean, true).into();
336+
337+
let sizes = vec![10, 100, 500];
338+
339+
for &size in &sizes {
340+
let haystack = create_string_list_array(NUM_ROWS, size, NULL_DENSITY);
341+
let arg_fields: Vec<Arc<Field>> = vec![
342+
Field::new("arr", haystack.data_type().clone(), false).into(),
343+
Field::new("el", DataType::Utf8, false).into(),
344+
];
345+
346+
let needle_found = create_string_value_array(NUM_ROWS, size, "value_");
347+
let args_found = vec![
348+
ColumnarValue::Array(haystack.clone()),
349+
ColumnarValue::Array(needle_found),
350+
];
351+
group.bench_with_input(BenchmarkId::new("found", size), &size, |b, _| {
352+
let udf = ArrayHas::new();
353+
b.iter(|| {
354+
black_box(
355+
udf.invoke_with_args(ScalarFunctionArgs {
356+
args: args_found.clone(),
357+
arg_fields: arg_fields.clone(),
358+
number_rows: NUM_ROWS,
359+
return_field: return_field.clone(),
360+
config_options: config_options.clone(),
361+
})
362+
.unwrap(),
363+
)
364+
})
365+
});
366+
367+
let needle_not_found = create_string_value_array(NUM_ROWS, size, "missing_");
368+
let args_not_found = vec![
369+
ColumnarValue::Array(haystack.clone()),
370+
ColumnarValue::Array(needle_not_found),
371+
];
372+
group.bench_with_input(BenchmarkId::new("not_found", size), &size, |b, _| {
373+
let udf = ArrayHas::new();
374+
b.iter(|| {
375+
black_box(
376+
udf.invoke_with_args(ScalarFunctionArgs {
377+
args: args_not_found.clone(),
378+
arg_fields: arg_fields.clone(),
379+
number_rows: NUM_ROWS,
380+
return_field: return_field.clone(),
381+
config_options: config_options.clone(),
382+
})
383+
.unwrap(),
384+
)
385+
})
386+
});
387+
}
388+
389+
group.finish();
390+
}
391+
122392
fn bench_array_has_all(c: &mut Criterion, array_size: usize) {
123393
let mut group = c.benchmark_group("array_has_all");
124394
let haystack = create_int64_list_array(NUM_ROWS, array_size, NULL_DENSITY);
@@ -659,6 +929,30 @@ fn create_int64_list_array(
659929
)
660930
}
661931

932+
/// Create an `Int64Array` of `num_rows` non-null values in `[offset, offset +
933+
/// range)`, used as an array needle for `array_has`.
934+
fn create_int64_value_array(num_rows: usize, range: i64, offset: i64) -> ArrayRef {
935+
let mut rng = StdRng::seed_from_u64(SEED + 2);
936+
let values = (0..num_rows)
937+
.map(|_| Some(rng.random_range(0..range) + offset))
938+
.collect::<Int64Array>();
939+
Arc::new(values)
940+
}
941+
942+
/// Create a `StringArray` of `num_rows` non-null values like "{prefix}{idx}"
943+
/// where `idx` is drawn from `[0, range)`, used as an array needle for
944+
/// `array_has`.
945+
fn create_string_value_array(num_rows: usize, range: usize, prefix: &str) -> ArrayRef {
946+
let mut rng = StdRng::seed_from_u64(SEED + 2);
947+
let values = (0..num_rows)
948+
.map(|_| {
949+
let idx = rng.random_range(0..range);
950+
Some(format!("{prefix}{idx}"))
951+
})
952+
.collect::<StringArray>();
953+
Arc::new(values)
954+
}
955+
662956
/// Like `create_int64_list_array` but values are offset so they won't
663957
/// appear in a standard list array (useful for "not found" benchmarks).
664958
fn create_int64_list_array_with_offset(

0 commit comments

Comments
 (0)