Skip to content

Commit 64871d9

Browse files
authored
perf: Improve efficiency of array_has_any on sliced lists (#25427)
## Which issue does this PR close? - Closes #25426. ## Rationale for this change When one argument of `array_has_any` is a scalar and the element type is not a string, the fast path `array_has_any_with_scalar_general` row-converts the list column's full child array, which does a lot of unnecessary work for sliced lists. Benchmarks: - array_has_any_scalar/i64_no_match_sliced/1: 4.14 ms -> 167.4 µs, −96.0% - array_has_any_scalar/i64_no_match_sliced/10: 4.11 ms -> 125.9 µs, −96.9% - array_has_any_scalar/i64_no_match_sliced/100: 4.25 ms -> 257.8 µs, −93.9% - array_has_any_scalar/i64_no_match_sliced/1000: 4.12 ms -> 141.1 µs, −96.6% Results on unsliced inputs were unchanged, within run-to-run noise. ## What changes are included in this PR? * Improve `array_has_any_with_scalar_general` to only touch the visible portion of the input list * Add a benchmark * Add unit tests for correct behavior on sliced lists ## What is the testing strategy for this PR? Existing tests pass, new tests added. Benchmark confirms that the inefficiency has been addressed. ## Are there any user-facing changes? No.
1 parent bacbf2a commit 64871d9

2 files changed

Lines changed: 139 additions & 32 deletions

File tree

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

Lines changed: 36 additions & 25 deletions
Original file line numberDiff line numberDiff line change
@@ -913,31 +913,42 @@ fn bench_array_has_any_scalar(c: &mut Criterion) {
913913
Field::new("second", list_type_i64.clone(), false).into(),
914914
];
915915

916-
for &scalar_size in &scalar_sizes {
917-
let scalar_arg = create_int64_scalar_list(scalar_size, array_size as i64);
918-
let args = vec![
919-
ColumnarValue::Array(first_arr_i64.clone()),
920-
ColumnarValue::Scalar(scalar_arg),
921-
];
922-
group.bench_with_input(
923-
BenchmarkId::new("i64_no_match", scalar_size),
924-
&scalar_size,
925-
|b, _| {
926-
let udf = ArrayHasAny::new();
927-
b.iter(|| {
928-
black_box(
929-
udf.invoke_with_args(ScalarFunctionArgs {
930-
args: args.clone(),
931-
arg_fields: arg_fields_i64.clone(),
932-
number_rows: NUM_ROWS,
933-
return_field: return_field.clone(),
934-
config_options: config_options.clone(),
935-
})
936-
.unwrap(),
937-
)
938-
})
939-
},
940-
);
916+
// The same number of visible rows, sliced from the middle of a backing
917+
// array that is 100 times larger.
918+
let backing_rows = NUM_ROWS * 100;
919+
let sliced_arr_i64 = create_int64_list_array(backing_rows, array_size, NULL_DENSITY)
920+
.slice(backing_rows / 2, NUM_ROWS);
921+
922+
for (name, arr) in [
923+
("i64_no_match", &first_arr_i64),
924+
("i64_no_match_sliced", &sliced_arr_i64),
925+
] {
926+
for &scalar_size in &scalar_sizes {
927+
let scalar_arg = create_int64_scalar_list(scalar_size, array_size as i64);
928+
let args = vec![
929+
ColumnarValue::Array(arr.clone()),
930+
ColumnarValue::Scalar(scalar_arg),
931+
];
932+
group.bench_with_input(
933+
BenchmarkId::new(name, scalar_size),
934+
&scalar_size,
935+
|b, _| {
936+
let udf = ArrayHasAny::new();
937+
b.iter(|| {
938+
black_box(
939+
udf.invoke_with_args(ScalarFunctionArgs {
940+
args: args.clone(),
941+
arg_fields: arg_fields_i64.clone(),
942+
number_rows: NUM_ROWS,
943+
return_field: return_field.clone(),
944+
config_options: config_options.clone(),
945+
})
946+
.unwrap(),
947+
)
948+
})
949+
},
950+
);
951+
}
941952
}
942953

943954
// String benchmarks

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

Lines changed: 103 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -966,10 +966,17 @@ fn array_has_any_with_scalar_general(
966966
};
967967

968968
let col_list: ArrayWrapper = col_arr.as_ref().try_into()?;
969-
let col_rows = converter.convert_columns(&[Arc::clone(col_list.values())])?;
970969
let col_offsets: Vec<usize> = col_list.offsets().collect();
971970
let col_nulls = col_list.nulls();
972971

972+
// For efficiency with sliced arrays, only convert the visible elements,
973+
// not the entire underlying buffer. Indices into `col_rows` are therefore
974+
// relative to `elem_start`.
975+
let elem_start = col_offsets[0];
976+
let elem_end = col_offsets[col_list.len()];
977+
let visible_values = col_list.values().slice(elem_start, elem_end - elem_start);
978+
let col_rows = converter.convert_columns(&[visible_values])?;
979+
973980
let mut result = BooleanBufferBuilder::new(col_list.len());
974981
let num_scalar = scalar_rows.num_rows();
975982

@@ -984,8 +991,8 @@ fn array_has_any_with_scalar_general(
984991
result.append(false);
985992
continue;
986993
}
987-
let start = col_offsets[i];
988-
let end = col_offsets[i + 1];
994+
let start = col_offsets[i] - elem_start;
995+
let end = col_offsets[i + 1] - elem_start;
989996
let found =
990997
(start..end).any(|j| scalar_set.contains(col_rows.row(j).as_ref()));
991998
result.append(found);
@@ -997,8 +1004,8 @@ fn array_has_any_with_scalar_general(
9971004
result.append(false);
9981005
continue;
9991006
}
1000-
let start = col_offsets[i];
1001-
let end = col_offsets[i + 1];
1007+
let start = col_offsets[i] - elem_start;
1008+
let end = col_offsets[i + 1] - elem_start;
10021009
let found = (start..end)
10031010
.any(|j| (0..num_scalar).any(|k| col_rows.row(j) == scalar_rows.row(k)));
10041011
result.append(found);
@@ -1216,8 +1223,8 @@ mod tests {
12161223
use arrow::datatypes::Int32Type;
12171224
use arrow::{
12181225
array::{
1219-
Array, ArrayRef, AsArray, FixedSizeListArray, Int32Array, ListArray,
1220-
create_array,
1226+
Array, ArrayRef, AsArray, FixedSizeListArray, Int32Array, LargeListArray,
1227+
ListArray, create_array,
12211228
},
12221229
buffer::OffsetBuffer,
12231230
datatypes::{DataType, Field, Schema},
@@ -1683,4 +1690,93 @@ mod tests {
16831690
vec![Some(true), Some(false)]
16841691
);
16851692
}
1693+
1694+
/// Invoke `array_has_any` with an array haystack and a scalar list of
1695+
/// `Int32` elements.
1696+
fn invoke_array_has_any_scalar(haystack: ArrayRef, scalar: Vec<i32>) -> ArrayRef {
1697+
let num_rows = haystack.len();
1698+
let haystack_type = haystack.data_type().clone();
1699+
let scalar = SingleRowListArrayBuilder::new(Arc::new(Int32Array::from(scalar)))
1700+
.build_list_scalar();
1701+
let scalar_type = scalar.data_type();
1702+
ArrayHasAny::new()
1703+
.invoke_with_args(ScalarFunctionArgs {
1704+
args: vec![
1705+
ColumnarValue::Array(haystack),
1706+
ColumnarValue::Scalar(scalar),
1707+
],
1708+
arg_fields: vec![
1709+
Arc::new(Field::new("haystack", haystack_type, true)),
1710+
Arc::new(Field::new("scalar", scalar_type, true)),
1711+
],
1712+
number_rows: num_rows,
1713+
return_field: Arc::new(Field::new("return", DataType::Boolean, true)),
1714+
config_options: Arc::new(ConfigOptions::default()),
1715+
})
1716+
.unwrap()
1717+
.into_array(num_rows)
1718+
.unwrap()
1719+
}
1720+
1721+
#[test]
1722+
fn test_array_has_any_scalar_sliced() {
1723+
// The scalar path only row-converts the visible elements of a sliced
1724+
// haystack, so its per-row element ranges must be relative to the
1725+
// start of the visible range. 1 and 70 appear only in sliced-away rows.
1726+
let full = ListArray::from_iter_primitive::<Int32Type, _, _>(vec![
1727+
Some(vec![Some(1), Some(2)]),
1728+
Some(vec![Some(10), None, Some(30)]),
1729+
None,
1730+
Some(vec![]),
1731+
Some(vec![Some(50), Some(60)]),
1732+
Some(vec![Some(70)]),
1733+
]);
1734+
let sliced: ArrayRef = Arc::new(full.slice(1, 4));
1735+
1736+
// At most `SCALAR_SMALL_THRESHOLD` scalar elements: linear scan.
1737+
let result = invoke_array_has_any_scalar(Arc::clone(&sliced), vec![1, 70, 60]);
1738+
assert_eq!(
1739+
result.as_boolean().iter().collect::<Vec<_>>(),
1740+
vec![Some(false), None, Some(false), Some(true)]
1741+
);
1742+
let result = invoke_array_has_any_scalar(Arc::clone(&sliced), vec![30]);
1743+
assert_eq!(
1744+
result.as_boolean().iter().collect::<Vec<_>>(),
1745+
vec![Some(true), None, Some(false), Some(false)]
1746+
);
1747+
1748+
// More than `SCALAR_SMALL_THRESHOLD` scalar elements: HashSet lookup.
1749+
let large_scalar = vec![1, 70, 60, 101, 102, 103, 104, 105, 106, 107];
1750+
let result = invoke_array_has_any_scalar(sliced, large_scalar);
1751+
assert_eq!(
1752+
result.as_boolean().iter().collect::<Vec<_>>(),
1753+
vec![Some(false), None, Some(false), Some(true)]
1754+
);
1755+
1756+
// Sliced FixedSizeList (width 2; rows 1..=2 of
1757+
// [[1,2],[11,12],[21,22],[31,32]] visible).
1758+
let field = Arc::new(Field::new("item", DataType::Int32, true));
1759+
let fsl_values = Arc::new(Int32Array::from(vec![1, 2, 11, 12, 21, 22, 31, 32]));
1760+
let fsl: ArrayRef =
1761+
Arc::new(FixedSizeListArray::new(field, 2, fsl_values, None).slice(1, 2));
1762+
let result = invoke_array_has_any_scalar(fsl, vec![1, 22, 31]);
1763+
assert_eq!(
1764+
result.as_boolean().iter().collect::<Vec<_>>(),
1765+
vec![Some(false), Some(true)]
1766+
);
1767+
1768+
// Sliced LargeList; 1 and 70 appear only in sliced-away rows.
1769+
let large = LargeListArray::from_iter_primitive::<Int32Type, _, _>(vec![
1770+
Some(vec![Some(1), Some(2)]),
1771+
Some(vec![Some(10), None, Some(30)]),
1772+
Some(vec![Some(50), Some(60)]),
1773+
Some(vec![Some(70)]),
1774+
]);
1775+
let large: ArrayRef = Arc::new(large.slice(1, 2));
1776+
let result = invoke_array_has_any_scalar(large, vec![1, 70, 60]);
1777+
assert_eq!(
1778+
result.as_boolean().iter().collect::<Vec<_>>(),
1779+
vec![Some(false), Some(true)]
1780+
);
1781+
}
16861782
}

0 commit comments

Comments
 (0)