You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datafusion.apache.org by gi...@apache.org on 2026/08/03 18:45:27 UTC
(datafusion) branch gh-readonly-queue/main/pr-23907-62650eff81847928fadaf1d5e8ba2303cb13b819 created (now 28c8afa751)
This is an automated email from the ASF dual-hosted git repository.
github-merge-queue[bot] pushed a change to branch gh-readonly-queue/main/pr-23907-62650eff81847928fadaf1d5e8ba2303cb13b819
in repository https://gitbox.apache.org/repos/asf/datafusion.git
at 28c8afa751 IN LIST: isolate branchless filter implementation (#23907)
This branch includes the following new commits:
new 28c8afa751 IN LIST: isolate branchless filter implementation (#23907)
The 1 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datafusion.apache.org
For additional commands, e-mail: commits-help@datafusion.apache.org
(datafusion) 01/01: IN LIST: isolate branchless filter implementation (#23907)
Posted by gi...@apache.org.
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-23907-62650eff81847928fadaf1d5e8ba2303cb13b819
in repository https://gitbox.apache.org/repos/asf/datafusion.git
commit 28c8afa751e6aeb990699a2087f13840e9ab3351
Author: Geoffrey Claude <ge...@datadoghq.com>
AuthorDate: Mon Aug 3 20:44:59 2026 +0200
IN LIST: isolate branchless filter implementation (#23907)
## Which issue does this PR close?
- Part of #19241.
- Follow-up to #23014.
## Rationale for this change
#23014 added `BranchlessFilter` for small primitive `IN` lists. That
implementation currently sits in `primitive_filter.rs` alongside the
bitmap
and hash-based filters. This PR moves the branchless-specific types,
functions,
and tests into `branchless_filter.rs`.
The module docs explain the direct-comparison path and its per-width
limits.
They also cover why narrow types switch to bitmap filters and how nulls
are
handled.
`BranchlessFilter::try_new` also returns an execution error when the
list is
over its limit. Strategy selection rejects such lists before
constructing the
filter, so hitting that guard means the caller violated an internal
invariant.
This PR reports it as an internal error instead.
## What changes are included in this PR?
- Moves `BranchlessFilter`, its type mappings, size limits, and tests
into
`branchless_filter.rs`.
- Adds module documentation for the comparison strategy, thresholds,
narrow-type bitmap fallback, and null handling.
- Changes the oversized-list guard from an execution error to an
internal
error.
- Leaves routing, thresholds, comparison behavior, and null semantics
unchanged.
## Are these changes tested?
Yes. The existing branchless-filter tests were moved unchanged and
continue to
pass.
- `cargo fmt --all`
- `cargo test -p datafusion-physical-expr expressions::in_list --lib`
- `cargo clippy --all-targets --all-features -- -D warnings`
## Are there any user-facing changes?
No. This only reorganizes internal code and corrects an internal error
classification.
---
.../physical-expr/src/expressions/in_list.rs | 1 +
.../{primitive_filter.rs => branchless_filter.rs} | 608 +++------------------
.../src/expressions/in_list/primitive_filter.rs | 483 +---------------
.../src/expressions/in_list/strategy.rs | 5 +-
4 files changed, 71 insertions(+), 1026 deletions(-)
diff --git a/datafusion/physical-expr/src/expressions/in_list.rs b/datafusion/physical-expr/src/expressions/in_list.rs
index e4ec72285c..874e149b58 100644
--- a/datafusion/physical-expr/src/expressions/in_list.rs
+++ b/datafusion/physical-expr/src/expressions/in_list.rs
@@ -37,6 +37,7 @@ use datafusion_common::{
use datafusion_expr::{ColumnarValue, expr_vec_fmt};
mod array_static_filter;
+mod branchless_filter;
mod primitive_filter;
mod result;
mod static_filter;
diff --git a/datafusion/physical-expr/src/expressions/in_list/primitive_filter.rs b/datafusion/physical-expr/src/expressions/in_list/branchless_filter.rs
similarity index 50%
copy from datafusion/physical-expr/src/expressions/in_list/primitive_filter.rs
copy to datafusion/physical-expr/src/expressions/in_list/branchless_filter.rs
index e802e1d024..cd0cbd0de5 100644
--- a/datafusion/physical-expr/src/expressions/in_list/primitive_filter.rs
+++ b/datafusion/physical-expr/src/expressions/in_list/branchless_filter.rs
@@ -15,214 +15,70 @@
// specific language governing permissions and limitations
// under the License.
-//! Optimized primitive type filters for InList expressions.
+//! Fast membership tests for small, fixed-width primitive `IN` lists.
//!
-//! This module provides membership tests for Arrow primitive types.
+//! # Why use a branchless filter?
+//!
+//! For a short list such as `x IN (10, 20, 30)`, it can be faster to compare
+//! `x` with all three values than to build and search a hash table.
+//!
+//! "Branchless" means that the filter always checks every list value. It
+//! combines the answers with `|`, while `||` would stop at the first match.
+//! This regular sequence of comparisons is easier for the compiler and CPU to
+//! optimize.
+//!
+//! # How does it work?
+//!
+//! When the filter is built, it stores the non-null list values and chooses a
+//! comparison function for that list length. Only this small function is
+//! specialized for each length. The rest of [`BranchlessFilter`] is shared,
+//! which keeps the generated code small.
+//!
+//! Some Arrow types share the same in-memory representation. For example, a
+//! `Float32` and a `UInt32` both use four bytes per value. The filter compares
+//! those stored bits through an unsigned type of the same size, without copying
+//! the value buffer. A bit pattern is simply the bytes Arrow uses to store a
+//! value. Comparing it preserves details such as `0.0` versus `-0.0` and
+//! different NaN values. [`BranchlessFilterType`] defines these safe,
+//! same-sized mappings and checks their sizes at compile time.
+//!
+//! The fast path is intentionally limited to short lists:
+//!
+//! - 16 values for 1-byte types
+//! - 8 values for 2-byte types
+//! - 32 values for 4-byte types
+//! - 16 values for 8-byte types
+//! - 4 values for 16-byte types
+//!
+//! These numbers do not follow one size-based pattern. One- and two-byte
+//! values have an especially efficient next step: every possible bit pattern
+//! fits in a compact bitmap. For a longer list, the bitmap filter turns on one
+//! bit for each listed value, then checks membership with a direct bit lookup.
+//! This becomes a better fit before a 64- or 128-comparison branchless chain
+//! would be useful. Wider types have too many possible values for such a
+//! bitmap, so their limits are tuned separately.
+//!
+//! Larger lists use the standard filter strategy, including bitmap filters for
+//! one- and two-byte types.
+//!
+//! # What about nulls?
+//!
+//! Null list entries are omitted from the comparison chain but counted by the
+//! filter. Evaluation first records which values matched, then
+//! [`build_result_from_contains`] combines it with input nulls, list nulls, and
+//! `NOT IN` to produce the usual SQL null behavior.
+
+use std::mem::size_of;
use arrow::array::{Array, ArrayRef, AsArray, BooleanArray, PrimitiveArray};
-use arrow::buffer::{BooleanBuffer, NullBuffer, ScalarBuffer};
+use arrow::buffer::{BooleanBuffer, ScalarBuffer};
use arrow::datatypes::*;
use arrow::util::bit_iterator::BitIndexIterator;
-use datafusion_common::{HashSet, Result, exec_datafusion_err};
-use std::hash::{Hash, Hasher};
-use std::mem::size_of;
+use datafusion_common::{Result, exec_datafusion_err, internal_datafusion_err};
-use super::result::{build_in_list_result, build_result_from_contains};
+use super::result::build_result_from_contains;
use super::static_filter::{StaticFilter, handle_dictionary};
-/// Storage for the bits used by [`BitmapFilter`].
-///
-/// `BitmapFilter` represents an `IN` list with one bit for each possible
-/// value, so membership checks become direct bit tests. This trait lets the
-/// same filter code use different storage sizes for different integer widths.
-pub(super) trait BitmapStorage: Send + Sync {
- fn new_zeroed() -> Self;
- fn set_bit(&mut self, index: usize);
- fn get_bit(&self, index: usize) -> bool;
-}
-
-// `UInt8` has 256 possible values, 0 through 255. One bit per value takes
-// 256 bits, which fits in four `u64` words.
-impl BitmapStorage for [u64; 4] {
- #[inline]
- fn new_zeroed() -> Self {
- [0u64; 4]
- }
- #[inline]
- fn set_bit(&mut self, index: usize) {
- self[index / 64] |= 1u64 << (index % 64);
- }
- #[inline(always)]
- fn get_bit(&self, index: usize) -> bool {
- (self[index / 64] >> (index % 64)) & 1 != 0
- }
-}
-
-// `UInt16` has 65,536 possible values. One bit per value takes 65,536 bits,
-// which is 1,024 `u64` words, or 8 KiB. Box the array so the filter stores a
-// pointer instead of carrying an 8 KiB array inline.
-impl BitmapStorage for Box<[u64; 1024]> {
- #[inline]
- fn new_zeroed() -> Self {
- Box::new([0u64; 1024])
- }
- #[inline]
- fn set_bit(&mut self, index: usize) {
- self[index / 64] |= 1u64 << (index % 64);
- }
- #[inline(always)]
- fn get_bit(&self, index: usize) -> bool {
- (self[index / 64] >> (index % 64)) & 1 != 0
- }
-}
-
-/// Arrow primitive types supported by [`BitmapFilter`].
-///
-/// Arrow already defines the Rust value type as `T::Native`. This trait only
-/// supplies the bitmap storage size and maps values to their bit-pattern index
-/// for the primitive domains that are small enough to represent with one bit
-/// per possible value.
-pub(super) trait BitmapFilterType:
- ArrowPrimitiveType + Send + Sync + 'static
-{
- type Storage: BitmapStorage;
-
- /// Returns the index in the bitmap to check for this value.
- fn index(value: Self::Native) -> usize;
-}
-
-/// `Int8` has 256 possible bit patterns, so four `u64` words cover the full domain.
-impl BitmapFilterType for Int8Type {
- type Storage = [u64; 4];
-
- #[inline(always)]
- fn index(value: Self::Native) -> usize {
- // Reinterpret the signed value's bit pattern into a bitmap index.
- value as u8 as usize
- }
-}
-
-/// `UInt8` has 256 possible values, so four `u64` words cover the full domain.
-impl BitmapFilterType for UInt8Type {
- type Storage = [u64; 4];
-
- #[inline(always)]
- fn index(value: Self::Native) -> usize {
- value as usize
- }
-}
-
-/// `Int16` has 65,536 possible bit patterns, so 1,024 `u64` words cover the full
-/// domain.
-impl BitmapFilterType for Int16Type {
- type Storage = Box<[u64; 1024]>;
-
- #[inline(always)]
- fn index(value: Self::Native) -> usize {
- // Reinterpret the signed value's bit pattern into a bitmap index.
- value as u16 as usize
- }
-}
-
-/// `UInt16` has 65,536 possible values, so 1,024 `u64` words cover the full
-/// domain.
-impl BitmapFilterType for UInt16Type {
- type Storage = Box<[u64; 1024]>;
-
- #[inline(always)]
- fn index(value: Self::Native) -> usize {
- value as usize
- }
-}
-
-/// `Float16` has 65,536 possible bit patterns, so 1,024 `u64` words cover the
-/// full domain.
-impl BitmapFilterType for Float16Type {
- type Storage = Box<[u64; 1024]>;
-
- #[inline(always)]
- fn index(value: Self::Native) -> usize {
- value.to_bits() as usize
- }
-}
-
-/// `IN` filter backed by one bit per possible value.
-///
-/// Building the filter scans the non-null values in the IN-list and turns on
-/// the bit selected by each value. Evaluating input values checks the same bit
-/// position. Null handling and `NOT IN` inversion are handled by
-/// `build_in_list_result`.
-pub(super) struct BitmapFilter<T: BitmapFilterType> {
- null_count: usize,
- bits: T::Storage,
-}
-
-impl<T> BitmapFilter<T>
-where
- T: BitmapFilterType,
-{
- pub(super) fn try_new(in_array: &ArrayRef) -> Result<Self> {
- let prim_array = in_array.as_primitive_opt::<T>().ok_or_else(|| {
- exec_datafusion_err!("BitmapFilter: expected {} array", T::DATA_TYPE)
- })?;
- let mut bits = T::Storage::new_zeroed();
- let values = prim_array.values();
- match prim_array.nulls() {
- None => {
- for &v in values {
- bits.set_bit(T::index(v));
- }
- }
- Some(nulls) => {
- for i in
- BitIndexIterator::new(nulls.validity(), nulls.offset(), nulls.len())
- {
- bits.set_bit(T::index(values[i]));
- }
- }
- }
- Ok(Self {
- null_count: prim_array.null_count(),
- bits,
- })
- }
-
- #[inline(always)]
- fn check(&self, needle: T::Native) -> bool {
- self.bits.get_bit(T::index(needle))
- }
-}
-
-impl<T> StaticFilter for BitmapFilter<T>
-where
- T: BitmapFilterType,
-{
- fn null_count(&self) -> usize {
- self.null_count
- }
-
- fn contains(&self, v: &dyn Array, negated: bool) -> Result<BooleanArray> {
- handle_dictionary!(self, v, negated);
- let v = v.as_primitive_opt::<T>().ok_or_else(|| {
- exec_datafusion_err!("BitmapFilter: expected {} array", T::DATA_TYPE)
- })?;
- let input_values = v.values();
- Ok(build_in_list_result(
- v.len(),
- v.nulls(),
- self.null_count > 0,
- negated,
- #[inline(always)]
- |i| {
- // SAFETY: `build_in_list_result` invokes this closure for
- // indices in `0..v.len()`, which matches `input_values.len()`.
- let needle = unsafe { *input_values.get_unchecked(i) };
- self.check(needle)
- },
- ))
- }
-}
-
pub(super) type BranchlessNative<T> =
<<T as BranchlessFilterType>::CompareType as ArrowPrimitiveType>::Native;
@@ -355,7 +211,7 @@ where
let non_null_count = in_array.len() - in_array.null_count();
// `try_new` can be called on its own, so check the limit here too.
if non_null_count > T::MAX_LIST_LEN {
- return Err(exec_datafusion_err!(
+ return Err(internal_datafusion_err!(
"BranchlessFilter: supports at most {} non-null values, got {non_null_count}",
T::MAX_LIST_LEN
));
@@ -493,220 +349,19 @@ where
)
}
-/// Wrapper for f32 that implements Hash and Eq using bit comparison.
-/// This treats NaN values as equal to each other when they have the same bit pattern.
-#[derive(Clone, Copy)]
-struct OrderedFloat32(f32);
-
-impl Hash for OrderedFloat32 {
- fn hash<H: Hasher>(&self, state: &mut H) {
- self.0.to_ne_bytes().hash(state);
- }
-}
-
-impl PartialEq for OrderedFloat32 {
- fn eq(&self, other: &Self) -> bool {
- self.0.to_bits() == other.0.to_bits()
- }
-}
-
-impl Eq for OrderedFloat32 {}
-
-impl From<f32> for OrderedFloat32 {
- fn from(v: f32) -> Self {
- Self(v)
- }
-}
-
-/// Wrapper for f64 that implements Hash and Eq using bit comparison.
-/// This treats NaN values as equal to each other when they have the same bit pattern.
-#[derive(Clone, Copy)]
-struct OrderedFloat64(f64);
-
-impl Hash for OrderedFloat64 {
- fn hash<H: Hasher>(&self, state: &mut H) {
- self.0.to_ne_bytes().hash(state);
- }
-}
-
-impl PartialEq for OrderedFloat64 {
- fn eq(&self, other: &Self) -> bool {
- self.0.to_bits() == other.0.to_bits()
- }
-}
-
-impl Eq for OrderedFloat64 {}
-
-impl From<f64> for OrderedFloat64 {
- fn from(v: f64) -> Self {
- Self(v)
- }
-}
-
-// Macro to generate specialized StaticFilter implementations for primitive types
-macro_rules! primitive_static_filter {
- ($Name:ident, $ArrowType:ty) => {
- primitive_static_filter!(
- $Name,
- $ArrowType,
- <$ArrowType as ArrowPrimitiveType>::Native,
- |v| v
- );
- };
- ($Name:ident, $ArrowType:ty, $SetValueType:ty, $to_set_value:expr) => {
- pub(super) struct $Name {
- null_count: usize,
- values: HashSet<$SetValueType>,
- }
-
- impl $Name {
- pub(super) fn try_new(in_array: &ArrayRef) -> Result<Self> {
- let in_array =
- in_array.as_primitive_opt::<$ArrowType>().ok_or_else(|| {
- exec_datafusion_err!(
- "Failed to downcast an array to a '{}' array",
- stringify!($ArrowType)
- )
- })?;
-
- let mut values = HashSet::with_capacity(in_array.len());
- let null_count = in_array.null_count();
-
- for v in in_array.iter().flatten() {
- values.insert(($to_set_value)(v));
- }
-
- Ok(Self { null_count, values })
- }
- }
-
- impl StaticFilter for $Name {
- fn null_count(&self) -> usize {
- self.null_count
- }
-
- fn contains(&self, v: &dyn Array, negated: bool) -> Result<BooleanArray> {
- handle_dictionary!(self, v, negated);
-
- let v = v.as_primitive_opt::<$ArrowType>().ok_or_else(|| {
- exec_datafusion_err!(
- "Failed to downcast an array to a '{}' array",
- stringify!($ArrowType)
- )
- })?;
-
- let haystack_has_nulls = self.null_count > 0;
- let needle_values = v.values();
- let needle_nulls = v.nulls();
- let needle_has_nulls = v.null_count() > 0;
-
- // Truth table for `value [NOT] IN (set)` with SQL three-valued logic:
- // ("-" means the value doesn't affect the result)
- //
- // | needle_null | haystack_null | negated | in set? | result |
- // |-------------|---------------|---------|---------|--------|
- // | true | - | false | - | null |
- // | true | - | true | - | null |
- // | false | true | false | yes | true |
- // | false | true | false | no | null |
- // | false | true | true | yes | false |
- // | false | true | true | no | null |
- // | false | false | false | yes | true |
- // | false | false | false | no | false |
- // | false | false | true | yes | false |
- // | false | false | true | no | true |
-
- // Compute the "contains" result using collect_bool (fast batched approach)
- // This ignores nulls - we handle them separately
- let contains_buffer = if negated {
- BooleanBuffer::collect_bool(needle_values.len(), |i| {
- !self.values.contains(&($to_set_value)(needle_values[i]))
- })
- } else {
- BooleanBuffer::collect_bool(needle_values.len(), |i| {
- self.values.contains(&($to_set_value)(needle_values[i]))
- })
- };
-
- // Compute the null mask
- // Output is null when:
- // 1. needle value is null, OR
- // 2. needle value is not in set AND haystack has nulls
- let result_nulls = match (needle_has_nulls, haystack_has_nulls) {
- (false, false) => {
- // No nulls anywhere
- None
- }
- (true, false) => {
- // Only needle has nulls - just use needle's null mask
- needle_nulls.cloned()
- }
- (false, true) => {
- // Only haystack has nulls - result is null when value not in set
- // Valid (not null) when original "in set" is true
- // For NOT IN: contains_buffer = !original, so validity = !contains_buffer
- let validity = if negated {
- !&contains_buffer
- } else {
- contains_buffer.clone()
- };
- Some(NullBuffer::new(validity))
- }
- (true, true) => {
- // Both have nulls - combine needle nulls with haystack-induced nulls
- let needle_validity =
- needle_nulls.map(|n| n.inner().clone()).unwrap_or_else(
- || BooleanBuffer::new_set(needle_values.len()),
- );
-
- // Valid when original "in set" is true (see above)
- let haystack_validity = if negated {
- !&contains_buffer
- } else {
- contains_buffer.clone()
- };
-
- // Combined validity: valid only where both are valid
- let combined_validity = &needle_validity & &haystack_validity;
- Some(NullBuffer::new(combined_validity))
- }
- };
-
- Ok(BooleanArray::new(contains_buffer, result_nulls))
- }
- }
- };
-}
-
-primitive_static_filter!(Int32StaticFilter, Int32Type);
-primitive_static_filter!(Int64StaticFilter, Int64Type);
-primitive_static_filter!(UInt32StaticFilter, UInt32Type);
-primitive_static_filter!(UInt64StaticFilter, UInt64Type);
-
-// Macro to generate specialized StaticFilter implementations for float types
-// Floats require a wrapper type (OrderedFloat*) to implement Hash/Eq due to NaN semantics
-macro_rules! float_static_filter {
- ($Name:ident, $ArrowType:ty, $OrderedType:ty) => {
- primitive_static_filter!($Name, $ArrowType, $OrderedType, <$OrderedType>::from);
- };
-}
-
-// Generate specialized filters for float types using ordered wrappers
-float_static_filter!(Float32StaticFilter, Float32Type, OrderedFloat32);
-float_static_filter!(Float64StaticFilter, Float64Type, OrderedFloat64);
-
#[cfg(test)]
mod tests {
- use super::*;
use std::sync::Arc;
use arrow::array::{
- Decimal128Array, DictionaryArray, Float16Array, Float32Array, Float64Array,
- Int8Array, Int16Array, IntervalMonthDayNanoArray, TimestampMillisecondArray,
- TimestampNanosecondArray, UInt8Array, UInt16Array,
+ Decimal128Array, Float16Array, Float32Array, Float64Array, Int8Array,
+ IntervalMonthDayNanoArray, TimestampMillisecondArray, TimestampNanosecondArray,
+ UInt8Array, UInt16Array,
};
use half::f16;
+ use super::*;
+
fn assert_contains(
filter: &dyn StaticFilter,
needles: &dyn Array,
@@ -719,145 +374,6 @@ mod tests {
Ok(())
}
- #[test]
- fn bitmap_filter_u8_handles_nulls() -> Result<()> {
- let haystack: ArrayRef = Arc::new(UInt8Array::from(vec![Some(1), None, Some(3)]));
- let filter = BitmapFilter::<UInt8Type>::try_new(&haystack)?;
- let needles = UInt8Array::from(vec![Some(1), Some(2), None, Some(3)]);
-
- assert_contains(&filter, &needles, vec![Some(true), None, None, Some(true)])?;
- assert_eq!(
- filter.contains(&needles, true)?,
- BooleanArray::from(vec![Some(false), None, None, Some(false)])
- );
-
- Ok(())
- }
-
- #[test]
- fn bitmap_filter_u8_handles_dictionary_needles() -> Result<()> {
- let haystack: ArrayRef = Arc::new(UInt8Array::from(vec![Some(1), None, Some(3)]));
- let filter = BitmapFilter::<UInt8Type>::try_new(&haystack)?;
-
- let keys = Int8Array::from(vec![Some(0), Some(1), None, Some(2)]);
- let values = Arc::new(UInt8Array::from(vec![Some(1), Some(2), Some(3)]));
- let needles = DictionaryArray::try_new(keys, values)?;
-
- assert_contains(&filter, &needles, vec![Some(true), None, None, Some(true)])
- }
-
- #[test]
- fn bitmap_filter_i8_handles_signed_boundaries_and_slices() -> Result<()> {
- let haystack: ArrayRef = Arc::new(
- Int8Array::from(vec![Some(99), Some(i8::MIN), None, Some(-1), Some(42)])
- .slice(1, 3),
- );
- let filter = BitmapFilter::<Int8Type>::try_new(&haystack)?;
- let needles =
- Int8Array::from(vec![Some(7), Some(i8::MIN), Some(-1), None]).slice(1, 3);
-
- assert_eq!(
- filter.contains(&needles, false)?,
- BooleanArray::from(vec![Some(true), Some(true), None])
- );
- assert_eq!(
- filter.contains(&needles, true)?,
- BooleanArray::from(vec![Some(false), Some(false), None])
- );
-
- Ok(())
- }
-
- #[test]
- fn bitmap_filter_u16_handles_boundaries_and_nulls() -> Result<()> {
- let haystack: ArrayRef = Arc::new(UInt16Array::from(vec![
- Some(0),
- None,
- Some(1024),
- Some(u16::MAX),
- ]));
- let filter = BitmapFilter::<UInt16Type>::try_new(&haystack)?;
- let needles =
- UInt16Array::from(vec![Some(0), Some(1), Some(1024), Some(u16::MAX), None]);
-
- assert_contains(
- &filter,
- &needles,
- vec![Some(true), None, Some(true), Some(true), None],
- )?;
- assert_eq!(
- filter.contains(&needles, true)?,
- BooleanArray::from(vec![Some(false), None, Some(false), Some(false), None])
- );
-
- Ok(())
- }
-
- #[test]
- fn bitmap_filter_i16_handles_signed_boundaries_and_slices() -> Result<()> {
- let haystack: ArrayRef = Arc::new(
- Int16Array::from(vec![
- Some(123),
- Some(i16::MIN),
- None,
- Some(-1),
- Some(i16::MAX),
- ])
- .slice(1, 4),
- );
- let filter = BitmapFilter::<Int16Type>::try_new(&haystack)?;
- let needles =
- Int16Array::from(vec![Some(0), Some(i16::MIN), Some(7), Some(i16::MAX)])
- .slice(1, 3);
-
- assert_eq!(
- filter.contains(&needles, false)?,
- BooleanArray::from(vec![Some(true), None, Some(true)])
- );
- assert_eq!(
- filter.contains(&needles, true)?,
- BooleanArray::from(vec![Some(false), None, Some(false)])
- );
-
- Ok(())
- }
-
- #[test]
- fn bitmap_filter_f16_handles_bit_patterns_and_slices() -> Result<()> {
- let nan_a = f16::from_bits(0x7e01);
- let nan_b = f16::from_bits(0x7e02);
- let haystack: ArrayRef = Arc::new(
- Float16Array::from(vec![
- Some(f16::from_f32(9.0)),
- Some(f16::from_f32(1.5)),
- None,
- Some(f16::from_f32(-0.0)),
- Some(nan_a),
- ])
- .slice(1, 4),
- );
- let filter = BitmapFilter::<Float16Type>::try_new(&haystack)?;
- let needles = Float16Array::from(vec![
- Some(f16::from_f32(0.0)),
- Some(f16::from_f32(-0.0)),
- Some(nan_a),
- Some(nan_b),
- None,
- ])
- .slice(1, 4);
-
- assert_eq!(
- filter.contains(&needles, false)?,
- BooleanArray::from(vec![Some(true), Some(true), None, None])
- );
- assert_eq!(
- filter.contains(&needles, true)?,
- BooleanArray::from(vec![Some(false), Some(false), None, None])
- );
-
- Ok(())
- }
-
#[test]
fn branchless_filter_u8_handles_nulls() -> Result<()> {
let haystack: ArrayRef = Arc::new(UInt8Array::from(vec![Some(1), None, Some(3)]));
diff --git a/datafusion/physical-expr/src/expressions/in_list/primitive_filter.rs b/datafusion/physical-expr/src/expressions/in_list/primitive_filter.rs
index e802e1d024..8f8d9bad04 100644
--- a/datafusion/physical-expr/src/expressions/in_list/primitive_filter.rs
+++ b/datafusion/physical-expr/src/expressions/in_list/primitive_filter.rs
@@ -19,15 +19,14 @@
//!
//! This module provides membership tests for Arrow primitive types.
-use arrow::array::{Array, ArrayRef, AsArray, BooleanArray, PrimitiveArray};
-use arrow::buffer::{BooleanBuffer, NullBuffer, ScalarBuffer};
+use arrow::array::{Array, ArrayRef, AsArray, BooleanArray};
+use arrow::buffer::{BooleanBuffer, NullBuffer};
use arrow::datatypes::*;
use arrow::util::bit_iterator::BitIndexIterator;
use datafusion_common::{HashSet, Result, exec_datafusion_err};
use std::hash::{Hash, Hasher};
-use std::mem::size_of;
-use super::result::{build_in_list_result, build_result_from_contains};
+use super::result::build_in_list_result;
use super::static_filter::{StaticFilter, handle_dictionary};
/// Storage for the bits used by [`BitmapFilter`].
@@ -223,276 +222,6 @@ where
}
}
-pub(super) type BranchlessNative<T> =
- <<T as BranchlessFilterType>::CompareType as ArrowPrimitiveType>::Native;
-
-/// Maximum list size for branchless lookup on 1-byte primitives.
-///
-/// Sixteen 1-byte values fit in one 128-bit SIMD vector, so this keeps the
-/// branchless list small enough for a single vectorized membership check.
-const BRANCHLESS_MAX_1B: usize = 16;
-
-/// Maximum list size for branchless lookup on 2-byte primitives.
-///
-/// Eight 2-byte values fit in one 128-bit SIMD vector, so this keeps the
-/// branchless list small enough for a single vectorized membership check.
-const BRANCHLESS_MAX_2B: usize = 8;
-
-/// Maximum list size for branchless lookup on 4-byte primitives.
-///
-/// Thirty-two 4-byte values keep the inline list at 128 bytes. Beyond that,
-/// the comparison chain and filter footprint grow enough that the hash/generic
-/// fallback is a better fit.
-const BRANCHLESS_MAX_4B: usize = 32;
-
-/// Maximum list size for branchless lookup on 8-byte primitives.
-///
-/// Sixteen 8-byte values use the same 128-byte inline-list budget as 4-byte
-/// primitives. Larger lists are left to the hash/generic fallback.
-const BRANCHLESS_MAX_8B: usize = 16;
-
-/// Maximum list size for branchless lookup on 16-byte primitives.
-///
-/// These comparisons are wider, so this path is limited to four values.
-/// Larger lists are left to the generic fallback.
-const BRANCHLESS_MAX_16B: usize = 4;
-
-/// Arrow primitive types supported by [`BranchlessFilter`].
-///
-/// `T` is the logical Arrow type accepted by the filter. `CompareType` is the
-/// same-width type used for the fixed comparison chain. Signed integers,
-/// floats, and temporal values use an unsigned comparison type so they compare
-/// by their raw bit pattern.
-pub(super) trait BranchlessFilterType:
- ArrowPrimitiveType + Send + Sync + 'static
-{
- type CompareType: ArrowPrimitiveType + Send + Sync + 'static;
-
- /// Maximum number of non-null IN-list values to handle with
- /// [`BranchlessFilter`] for this primitive type.
- const MAX_LIST_LEN: usize;
-}
-
-macro_rules! branchless_filter_type {
- ($logical:ty, $compare:ty, $max_len:expr) => {
- // The branchless filter reads the same Arrow value buffer as the
- // comparison type. That is only valid when both native types have the
- // same width, so catch any bad mapping here at compile time.
- const _: () = assert!(
- size_of::<<$logical as ArrowPrimitiveType>::Native>()
- == size_of::<<$compare as ArrowPrimitiveType>::Native>(),
- "BranchlessFilterType::CompareType must use the same native width"
- );
-
- impl BranchlessFilterType for $logical {
- type CompareType = $compare;
- const MAX_LIST_LEN: usize = $max_len;
- }
- };
-}
-
-branchless_filter_type!(Int8Type, UInt8Type, BRANCHLESS_MAX_1B);
-branchless_filter_type!(UInt8Type, UInt8Type, BRANCHLESS_MAX_1B);
-branchless_filter_type!(Int16Type, UInt16Type, BRANCHLESS_MAX_2B);
-branchless_filter_type!(UInt16Type, UInt16Type, BRANCHLESS_MAX_2B);
-branchless_filter_type!(Float16Type, UInt16Type, BRANCHLESS_MAX_2B);
-
-branchless_filter_type!(Int32Type, UInt32Type, BRANCHLESS_MAX_4B);
-branchless_filter_type!(UInt32Type, UInt32Type, BRANCHLESS_MAX_4B);
-branchless_filter_type!(Float32Type, UInt32Type, BRANCHLESS_MAX_4B);
-branchless_filter_type!(Date32Type, UInt32Type, BRANCHLESS_MAX_4B);
-branchless_filter_type!(Time32SecondType, UInt32Type, BRANCHLESS_MAX_4B);
-branchless_filter_type!(Time32MillisecondType, UInt32Type, BRANCHLESS_MAX_4B);
-
-branchless_filter_type!(Int64Type, UInt64Type, BRANCHLESS_MAX_8B);
-branchless_filter_type!(UInt64Type, UInt64Type, BRANCHLESS_MAX_8B);
-branchless_filter_type!(Float64Type, UInt64Type, BRANCHLESS_MAX_8B);
-branchless_filter_type!(Date64Type, UInt64Type, BRANCHLESS_MAX_8B);
-branchless_filter_type!(Time64MicrosecondType, UInt64Type, BRANCHLESS_MAX_8B);
-branchless_filter_type!(Time64NanosecondType, UInt64Type, BRANCHLESS_MAX_8B);
-branchless_filter_type!(TimestampSecondType, UInt64Type, BRANCHLESS_MAX_8B);
-branchless_filter_type!(TimestampMillisecondType, UInt64Type, BRANCHLESS_MAX_8B);
-branchless_filter_type!(TimestampMicrosecondType, UInt64Type, BRANCHLESS_MAX_8B);
-branchless_filter_type!(TimestampNanosecondType, UInt64Type, BRANCHLESS_MAX_8B);
-branchless_filter_type!(DurationSecondType, UInt64Type, BRANCHLESS_MAX_8B);
-branchless_filter_type!(DurationMillisecondType, UInt64Type, BRANCHLESS_MAX_8B);
-branchless_filter_type!(DurationMicrosecondType, UInt64Type, BRANCHLESS_MAX_8B);
-branchless_filter_type!(DurationNanosecondType, UInt64Type, BRANCHLESS_MAX_8B);
-
-branchless_filter_type!(Decimal128Type, Decimal128Type, BRANCHLESS_MAX_16B);
-branchless_filter_type!(
- IntervalMonthDayNanoType,
- IntervalMonthDayNanoType,
- BRANCHLESS_MAX_16B
-);
-
-/// Checks each input value against the `IN`-list values.
-type MembershipCheck<C> = fn(in_list_values: &[C], input_values: &[C]) -> BooleanBuffer;
-
-/// A branchless filter for fixed-width primitive `IN` lists up to
-/// `T::MAX_LIST_LEN` values.
-///
-/// The filter stores the non-null `IN`-list values in a slice and chooses a
-/// comparison function for that length. Keeping the length out of
-/// `BranchlessFilter` avoids generating a full copy of the filter for every
-/// supported length.
-pub(super) struct BranchlessFilter<T: BranchlessFilterType> {
- expected_data_type: DataType,
- null_count: usize,
- in_list_values: Box<[BranchlessNative<T>]>,
- check_values: MembershipCheck<BranchlessNative<T>>,
-}
-
-impl<T> BranchlessFilter<T>
-where
- T: BranchlessFilterType,
- BranchlessNative<T>: Copy + PartialEq,
-{
- pub(super) fn try_new(in_array: &ArrayRef) -> Result<Self> {
- let in_array = in_array.as_primitive_opt::<T>().ok_or_else(|| {
- exec_datafusion_err!("BranchlessFilter: expected {} array", T::DATA_TYPE)
- })?;
- let non_null_count = in_array.len() - in_array.null_count();
- // `try_new` can be called on its own, so check the limit here too.
- if non_null_count > T::MAX_LIST_LEN {
- return Err(exec_datafusion_err!(
- "BranchlessFilter: supports at most {} non-null values, got {non_null_count}",
- T::MAX_LIST_LEN
- ));
- }
-
- let all_values = branchless_values::<T>(in_array);
- let mut in_list_values = Vec::with_capacity(non_null_count);
-
- match in_array.nulls() {
- None => {
- in_list_values.extend(all_values.iter().copied());
- }
- Some(nulls) => {
- for row in
- BitIndexIterator::new(nulls.validity(), nulls.offset(), nulls.len())
- {
- in_list_values.push(all_values[row]);
- }
- }
- }
-
- debug_assert_eq!(in_list_values.len(), non_null_count);
- let in_list_values = in_list_values.into_boxed_slice();
- let check_values = membership_check_for_len::<T>(in_list_values.len());
-
- Ok(Self {
- expected_data_type: in_array.data_type().clone(),
- null_count: in_array.null_count(),
- in_list_values,
- check_values,
- })
- }
-}
-
-impl<T> StaticFilter for BranchlessFilter<T>
-where
- T: BranchlessFilterType,
- BranchlessNative<T>: Copy + PartialEq + Send + Sync,
-{
- fn null_count(&self) -> usize {
- self.null_count
- }
-
- fn contains(&self, v: &dyn Array, negated: bool) -> Result<BooleanArray> {
- handle_dictionary!(self, v, negated);
-
- // Arrow compatibility ignores timestamp timezone and decimal precision/scale
- // while still requiring the same primitive representation.
- if !PrimitiveArray::<T>::is_compatible(v.data_type()) {
- return Err(exec_datafusion_err!(
- "BranchlessFilter: expected {} array, got {}",
- self.expected_data_type,
- v.data_type()
- ));
- }
-
- let v = v.as_primitive_opt::<T>().ok_or_else(|| {
- exec_datafusion_err!("BranchlessFilter: expected {} array", T::DATA_TYPE)
- })?;
- let input_values = branchless_values::<T>(v);
- let matches =
- (self.check_values)(self.in_list_values.as_ref(), input_values.as_ref());
- Ok(build_result_from_contains(
- v.nulls(),
- self.null_count > 0,
- negated,
- matches,
- ))
- }
-}
-
-/// Picks the comparison function for `len` non-null `IN`-list values.
-///
-/// A length of zero is used when the list contains only nulls. The comparisons
-/// return false, and the caller then applies the usual SQL null behavior.
-fn membership_check_for_len<T>(len: usize) -> MembershipCheck<BranchlessNative<T>>
-where
- T: BranchlessFilterType,
- BranchlessNative<T>: Copy + PartialEq,
-{
- macro_rules! choose {
- ($($n:literal),* $(,)?) => {
- match len {
- $($n => check_values::<BranchlessNative<T>, $n>,)*
- _ => unreachable!("list length exceeds the configured limit"),
- }
- };
- }
-
- // Avoid creating checks for lengths a type does not support.
- match T::MAX_LIST_LEN {
- 4 => choose!(0, 1, 2, 3, 4),
- 8 => choose!(0, 1, 2, 3, 4, 5, 6, 7, 8),
- 16 => choose!(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16),
- 32 => choose!(
- 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21,
- 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32,
- ),
- _ => unreachable!("list-size limits must be 4, 8, 16, or 32"),
- }
-}
-
-#[inline]
-fn check_values<C, const N: usize>(
- in_list_values: &[C],
- input_values: &[C],
-) -> BooleanBuffer
-where
- C: Copy + PartialEq,
-{
- let in_list_values: &[C; N] = in_list_values
- .try_into()
- .expect("comparison length matches IN-list values");
-
- BooleanBuffer::collect_bool(input_values.len(), |i| {
- // SAFETY: `collect_bool` invokes this closure for indices in
- // `0..input_values.len()`.
- let input_value = unsafe { *input_values.get_unchecked(i) };
- // `|` checks every list value; `||` would stop after the first match.
- in_list_values
- .iter()
- .fold(false, |acc, &value| acc | (value == input_value))
- })
-}
-
-fn branchless_values<T>(array: &PrimitiveArray<T>) -> ScalarBuffer<BranchlessNative<T>>
-where
- T: BranchlessFilterType,
-{
- let data = array.to_data();
- ScalarBuffer::<BranchlessNative<T>>::new(
- data.buffers()[0].clone(),
- data.offset(),
- data.len(),
- )
-}
-
/// Wrapper for f32 that implements Hash and Eq using bit comparison.
/// This treats NaN values as equal to each other when they have the same bit pattern.
#[derive(Clone, Copy)]
@@ -701,9 +430,7 @@ mod tests {
use std::sync::Arc;
use arrow::array::{
- Decimal128Array, DictionaryArray, Float16Array, Float32Array, Float64Array,
- Int8Array, Int16Array, IntervalMonthDayNanoArray, TimestampMillisecondArray,
- TimestampNanosecondArray, UInt8Array, UInt16Array,
+ DictionaryArray, Float16Array, Int8Array, Int16Array, UInt8Array, UInt16Array,
};
use half::f16;
@@ -857,206 +584,4 @@ mod tests {
Ok(())
}
-
- #[test]
- fn branchless_filter_u8_handles_nulls() -> Result<()> {
- let haystack: ArrayRef = Arc::new(UInt8Array::from(vec![Some(1), None, Some(3)]));
- let filter = BranchlessFilter::<UInt8Type>::try_new(&haystack)?;
- let needles = UInt8Array::from(vec![Some(1), Some(2), None, Some(3)]);
-
- assert_contains(&filter, &needles, vec![Some(true), None, None, Some(true)])?;
- assert_eq!(
- filter.contains(&needles, true)?,
- BooleanArray::from(vec![Some(false), None, None, Some(false)])
- );
-
- Ok(())
- }
-
- #[test]
- fn branchless_filter_all_null_list_preserves_sql_null_semantics() -> Result<()> {
- let haystack: ArrayRef = Arc::new(UInt8Array::from(vec![None, None]));
- let filter = BranchlessFilter::<UInt8Type>::try_new(&haystack)?;
- let needles = UInt8Array::from(vec![Some(1), None]);
- let expected = BooleanArray::from(vec![None, None]);
-
- assert_eq!(filter.contains(&needles, false)?, expected);
- assert_eq!(filter.contains(&needles, true)?, expected);
-
- Ok(())
- }
-
- #[test]
- fn branchless_filter_i8_handles_signed_boundaries_and_slices() -> Result<()> {
- let haystack: ArrayRef = Arc::new(
- Int8Array::from(vec![Some(99), Some(i8::MIN), None, Some(-1), Some(42)])
- .slice(1, 3),
- );
- let filter = BranchlessFilter::<Int8Type>::try_new(&haystack)?;
- let needles =
- Int8Array::from(vec![Some(7), Some(i8::MIN), Some(-1), None]).slice(1, 3);
-
- assert_eq!(
- filter.contains(&needles, false)?,
- BooleanArray::from(vec![Some(true), Some(true), None])
- );
- assert_eq!(
- filter.contains(&needles, true)?,
- BooleanArray::from(vec![Some(false), Some(false), None])
- );
-
- let wrong_type = UInt8Array::from(vec![Some(128), Some(u8::MAX)]);
- let err = filter.contains(&wrong_type, false).unwrap_err().to_string();
- assert!(err.contains("expected Int8 array, got UInt8"), "{err}");
-
- Ok(())
- }
-
- #[test]
- fn branchless_filter_f16_handles_bit_patterns_and_slices() -> Result<()> {
- let nan_a = f16::from_bits(0x7e01);
- let nan_b = f16::from_bits(0x7e02);
- let haystack: ArrayRef = Arc::new(
- Float16Array::from(vec![
- Some(f16::from_f32(9.0)),
- Some(f16::from_f32(-0.0)),
- Some(nan_a),
- None,
- ])
- .slice(1, 3),
- );
- let filter = BranchlessFilter::<Float16Type>::try_new(&haystack)?;
- let needles = Float16Array::from(vec![
- Some(f16::from_f32(0.0)),
- Some(f16::from_f32(-0.0)),
- Some(nan_a),
- Some(nan_b),
- None,
- ]);
-
- assert_eq!(
- filter.contains(&needles, false)?,
- BooleanArray::from(vec![None, Some(true), Some(true), None, None])
- );
- assert_eq!(
- filter.contains(&needles, true)?,
- BooleanArray::from(vec![None, Some(false), Some(false), None, None])
- );
-
- let wrong_type = UInt16Array::from(vec![Some(0x8000), Some(0x7e01)]);
- let err = filter.contains(&wrong_type, false).unwrap_err().to_string();
- assert!(err.contains("expected Float16 array, got UInt16"), "{err}");
-
- Ok(())
- }
-
- #[test]
- fn branchless_filter_floats_use_bit_equality() -> Result<()> {
- let nan_a = f32::from_bits(0x7fc0_0001);
- let nan_b = f32::from_bits(0x7fc0_0002);
- let haystack: ArrayRef =
- Arc::new(Float32Array::from(vec![Some(-0.0), Some(nan_a)]));
- let filter = BranchlessFilter::<Float32Type>::try_new(&haystack)?;
- let needles =
- Float32Array::from(vec![Some(0.0), Some(-0.0), Some(nan_a), Some(nan_b)]);
-
- assert_eq!(
- filter.contains(&needles, false)?,
- BooleanArray::from(vec![Some(false), Some(true), Some(true), Some(false)])
- );
-
- let nan_a = f64::from_bits(0x7ff8_0000_0000_0001);
- let nan_b = f64::from_bits(0x7ff8_0000_0000_0002);
- let haystack: ArrayRef =
- Arc::new(Float64Array::from(vec![Some(-0.0), Some(nan_a)]));
- let filter = BranchlessFilter::<Float64Type>::try_new(&haystack)?;
- let needles =
- Float64Array::from(vec![Some(0.0), Some(-0.0), Some(nan_a), Some(nan_b)]);
-
- assert_eq!(
- filter.contains(&needles, false)?,
- BooleanArray::from(vec![Some(false), Some(true), Some(true), Some(false)])
- );
-
- Ok(())
- }
-
- #[test]
- fn branchless_filter_timestamp_uses_physical_compatibility() -> Result<()> {
- let haystack: ArrayRef = Arc::new(
- TimestampNanosecondArray::from(vec![Some(1), Some(3)]).with_timezone("UTC"),
- );
- let filter = BranchlessFilter::<TimestampNanosecondType>::try_new(&haystack)?;
- let needles = TimestampNanosecondArray::from(vec![Some(1), Some(2), None])
- .with_timezone("UTC");
-
- assert_contains(&filter, &needles, vec![Some(true), Some(false), None])?;
-
- let different_timezone = TimestampNanosecondArray::from(vec![Some(1), Some(2)])
- .with_timezone("Europe/Paris");
- assert_contains(&filter, &different_timezone, vec![Some(true), Some(false)])?;
-
- let different_unit = TimestampMillisecondArray::from(vec![Some(1)]);
- let err = filter
- .contains(&different_unit, false)
- .unwrap_err()
- .to_string();
- assert!(err.contains("Timestamp(ns"), "{err}");
- assert!(err.contains("Timestamp(ms"), "{err}");
-
- Ok(())
- }
-
- #[test]
- fn branchless_filter_decimal128_handles_precision_scale_and_nulls() -> Result<()> {
- let haystack: ArrayRef = Arc::new(
- Decimal128Array::from(vec![Some(12345), None, Some(-700), Some(42)])
- .with_precision_and_scale(10, 2)?,
- );
- let filter = BranchlessFilter::<Decimal128Type>::try_new(&haystack)?;
- let needles =
- Decimal128Array::from(vec![Some(12345), Some(999), None, Some(-700)])
- .with_precision_and_scale(10, 2)?;
-
- assert_contains(&filter, &needles, vec![Some(true), None, None, Some(true)])?;
- assert_eq!(
- filter.contains(&needles, true)?,
- BooleanArray::from(vec![Some(false), None, None, Some(false)])
- );
-
- let compatible_metadata =
- Decimal128Array::from(vec![Some(12345)]).with_precision_and_scale(11, 3)?;
- assert_contains(&filter, &compatible_metadata, vec![Some(true)])?;
-
- Ok(())
- }
-
- #[test]
- fn branchless_filter_interval_month_day_nano_handles_nulls() -> Result<()> {
- let one_month = IntervalMonthDayNanoType::make_value(1, 0, 0);
- let two_days = IntervalMonthDayNanoType::make_value(0, 2, 0);
- let three_nanos = IntervalMonthDayNanoType::make_value(0, 0, 3);
- let absent = IntervalMonthDayNanoType::make_value(4, 5, 6);
- let haystack: ArrayRef = Arc::new(IntervalMonthDayNanoArray::from(vec![
- Some(one_month),
- None,
- Some(two_days),
- Some(three_nanos),
- ]));
- let filter = BranchlessFilter::<IntervalMonthDayNanoType>::try_new(&haystack)?;
- let needles = IntervalMonthDayNanoArray::from(vec![
- Some(one_month),
- Some(absent),
- None,
- Some(three_nanos),
- ]);
-
- assert_contains(&filter, &needles, vec![Some(true), None, None, Some(true)])?;
- assert_eq!(
- filter.contains(&needles, true)?,
- BooleanArray::from(vec![Some(false), None, None, Some(false)])
- );
-
- Ok(())
- }
}
diff --git a/datafusion/physical-expr/src/expressions/in_list/strategy.rs b/datafusion/physical-expr/src/expressions/in_list/strategy.rs
index be4dce8dfd..d5ca8154a9 100644
--- a/datafusion/physical-expr/src/expressions/in_list/strategy.rs
+++ b/datafusion/physical-expr/src/expressions/in_list/strategy.rs
@@ -31,6 +31,9 @@ use arrow::datatypes::{
use datafusion_common::Result;
use super::array_static_filter::ArrayStaticFilter;
+use super::branchless_filter::{
+ BranchlessFilter, BranchlessFilterType, BranchlessNative,
+};
use super::primitive_filter::*;
use super::static_filter::StaticFilter;
@@ -159,7 +162,7 @@ mod tests {
use arrow::array::UInt32Array;
use arrow::datatypes::UInt32Type;
- use super::super::primitive_filter::BranchlessFilterType;
+ use super::super::branchless_filter::BranchlessFilterType;
use super::*;
fn uint32_array(values: Vec<Option<u32>>) -> ArrayRef {
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datafusion.apache.org
For additional commands, e-mail: commits-help@datafusion.apache.org