Skip to content

Commit 65b67ba

Browse files
Optimize IN LIST for byte view arrays with standard hash sets
1 parent db0c31b commit 65b67ba

4 files changed

Lines changed: 504 additions & 12 deletions

File tree

‎datafusion/physical-expr/src/expressions/in_list.rs‎

Lines changed: 20 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -38,6 +38,7 @@ use datafusion_expr::{ColumnarValue, expr_vec_fmt};
3838

3939
mod array_static_filter;
4040
mod branchless_filter;
41+
mod byte_view_filter;
4142
mod primitive_filter;
4243
mod result;
4344
mod static_filter;
@@ -215,7 +216,7 @@ impl InListExpr {
215216
expr,
216217
list,
217218
negated,
218-
Some(instantiate_static_filter(array)?),
219+
Some(instantiate_static_filter(array, &expr_data_type)?),
219220
))
220221
}
221222

@@ -242,7 +243,7 @@ impl InListExpr {
242243

243244
// Try to create a static filter if all list expressions are constants
244245
let static_filter = match try_evaluate_constant_list(&list, schema)? {
245-
Some(in_array) => Some(instantiate_static_filter(in_array)?),
246+
Some(in_array) => Some(instantiate_static_filter(in_array, &expr_data_type)?),
246247
None => None, // Non-constant expressions, fall back to dynamic evaluation
247248
};
248249

@@ -3576,6 +3577,23 @@ mod tests {
35763577
)?
35773578
);
35783579

3580+
// Utf8View in_array, Utf8View and Dict(Utf8View) needles
3581+
let utf8view_in =
3582+
Arc::new(StringViewArray::from(vec!["a", "b", "c"])) as ArrayRef;
3583+
let utf8view_needle =
3584+
Arc::new(StringViewArray::from(vec!["a", "d", "b"])) as ArrayRef;
3585+
assert_eq!(
3586+
expected,
3587+
eval_in_list_from_array(
3588+
Arc::clone(&utf8view_needle),
3589+
Arc::clone(&utf8view_in),
3590+
)?
3591+
);
3592+
assert_eq!(
3593+
expected,
3594+
eval_in_list_from_array(wrap_in_dict(utf8view_needle), utf8view_in)?
3595+
);
3596+
35793597
// Struct in_array, Struct needle: multi-column join
35803598
let struct_fields = Fields::from(vec![
35813599
Field::new("c0", DataType::Utf8, true),

‎datafusion/physical-expr/src/expressions/in_list/branchless_filter.rs‎

Lines changed: 13 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -71,7 +71,7 @@
7171
use std::mem::size_of;
7272

7373
use arrow::array::{Array, ArrayRef, AsArray, BooleanArray, PrimitiveArray};
74-
use arrow::buffer::{BooleanBuffer, ScalarBuffer};
74+
use arrow::buffer::{BooleanBuffer, NullBuffer, ScalarBuffer};
7575
use arrow::datatypes::*;
7676
use arrow::util::bit_iterator::BitIndexIterator;
7777
use datafusion_common::{Result, exec_datafusion_err, internal_datafusion_err};
@@ -244,6 +244,17 @@ where
244244
check_values,
245245
})
246246
}
247+
248+
#[inline]
249+
pub(super) fn contains_slice(
250+
&self,
251+
input_values: &[BranchlessNative<T>],
252+
nulls: Option<&NullBuffer>,
253+
negated: bool,
254+
) -> BooleanArray {
255+
let matches = (self.check_values)(self.in_list_values.as_ref(), input_values);
256+
build_result_from_contains(nulls, self.null_count > 0, negated, matches)
257+
}
247258
}
248259

249260
impl<T> StaticFilter for BranchlessFilter<T>
@@ -272,14 +283,7 @@ where
272283
exec_datafusion_err!("BranchlessFilter: expected {} array", T::DATA_TYPE)
273284
})?;
274285
let input_values = branchless_values::<T>(v);
275-
let matches =
276-
(self.check_values)(self.in_list_values.as_ref(), input_values.as_ref());
277-
Ok(build_result_from_contains(
278-
v.nulls(),
279-
self.null_count > 0,
280-
negated,
281-
matches,
282-
))
286+
Ok(self.contains_slice(input_values.as_ref(), v.nulls(), negated))
283287
}
284288
}
285289

0 commit comments

Comments
 (0)