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/07/26 01:44:56 UTC
(datafusion) branch main updated: IN LIST: add branchless filter for small primitive lists (#23014)
This is an automated email from the ASF dual-hosted git repository.
github-merge-queue[bot] pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/datafusion.git
The following commit(s) were added to refs/heads/main by this push:
new e3e2cb2279 IN LIST: add branchless filter for small primitive lists (#23014)
e3e2cb2279 is described below
commit e3e2cb227928ffa498c2845db6ce2aa86ee174b4
Author: Geoffrey Claude <ge...@datadoghq.com>
AuthorDate: Sun Jul 26 03:29:53 2026 +0200
IN LIST: add branchless filter for small primitive lists (#23014)
## Which issue does this PR close?
- Part of #19241.
- Stacked on [#23311](https://github.com/apache/datafusion/pull/23311).
- Next in stack: #23015.
- Extracted from #19390.
## Rationale for this change
For very small `IN` lists, building or probing a hash table can be more
work than just comparing the input value with each constant.
For example, for `x IN (10, 20, 30)`, the fast path can behave like:
```text
x == 10 OR x == 20 OR x == 30
```
Because the list is tiny, those comparisons are cheap. The
implementation stores the constants in a fixed-size array and checks
them with a compact comparison chain.
“Branchless” here means the comparisons are combined without stopping at
the first match. That can be faster for these small fixed-width lists
because the CPU gets a predictable sequence of simple operations instead
of hash-table setup and probe logic.
For primitive values that are not already plain unsigned integers, this
PR keeps the logical Arrow type explicit and uses a matching same-width
comparison representation only inside the branchless filter. For
example, `Float16` uses `UInt16` storage, `Float32` uses `UInt32`
storage, and `TimestampNanosecond` uses `UInt64` storage. `Decimal128`
and `IntervalMonthDayNano` use their own 16-byte native representation.
This preserves bit-pattern equality while relying on Arrow's native
primitive compatibility rules: timestamp timezone metadata and
Decimal128 precision/scale metadata may differ, while incompatible
primitive representations remain rejected.
## What changes are included in this PR?
- Adds a const-generic `BranchlessFilter` for small primitive `IN`
lists.
- Adds thresholds for when this path is used:
- up to 16 values for 1-byte types
- up to 8 values for 2-byte types
- up to 32 values for 4-byte types
- up to 16 values for 8-byte types
- up to 4 values for 16-byte types
- Keeps dispatch concrete and explicit in `strategy.rs`.
- Maps each optimized logical type to the comparison representation used
by the branchless filter:
- `Int8` -> `UInt8`
- `Int16`, `Float16` -> `UInt16`
- `Int32`, `Float32`, `Date32`, `Time32` -> `UInt32`
- `Int64`, `Float64`, `Date64`, `Time64`, `Timestamp`, `Duration` ->
`UInt64`
- `Decimal128`, `IntervalMonthDayNano` -> their native 16-byte
representation
- Leaves larger 1-byte and 2-byte lists on the existing bitmap filters.
- Leaves larger 4-byte and 8-byte lists on the existing hash/generic
paths.
- Leaves wider primitive types such as `Decimal256` and unsupported
complex types on the generic path.
- Keeps the same `IN` / `NOT IN` null behavior as the rest of the stack.
- Adds focused coverage for branchless null handling, signed boundary
values, slices, Float16/Float32/Float64 bit patterns, compatible
timestamp/Decimal128 metadata, incompatible timestamp units,
IntervalMonthDayNano values, and same-width wrong-type probe rejection.
## Are these changes tested?
Yes.
- `cargo fmt --all -- --check`
- `cargo test -p datafusion-physical-expr expressions::in_list --lib`
- `cargo test -p datafusion-physical-expr --bench in_list_strategy
--no-run`
- `cargo clippy --all-targets --all-features -- -D warnings`
## Are there any user-facing changes?
No. This is an internal performance optimization only.
## Local benchmark snapshot
Built and run with `release-nonlto`, filtered to the relevant small
primitive-list rows:
```bash
cargo bench -p datafusion-physical-expr --profile release-nonlto --bench in_list_strategy -- <filter> --save-baseline <baseline>
```
Filters used: `narrow_integer`, `primitive/i32/small_list`,
`primitive/i64/small_list`, `f32/small_list`, `timestamp_ns/small_list`,
and `interval_month_day_nano/small_list`.
Method: directly compared Criterion's raw sample minima (`min(time /
iterations)`) from `sample.json`. Lower is better; changes within +/-5%
are treated as noise.
Compared baselines:
[#23311](https://github.com/apache/datafusion/pull/23311) ->
[#23014](https://github.com/apache/datafusion/pull/23014)
Relevant scope: small primitive-list rows.
Summary: 39 relevant rows, 28 faster, 0 slower, 11 within +/-5%.
Largest relevant deltas:
| Benchmark | Before | After | Change |
|---|---:|---:|---:|
| `timestamp_ns/small_list/list=4/match=50%` | 46.55 us | 3.17 us |
-93.2% (14.69x faster) |
| `f32/small_list/list=4/match=50%` | 33.93 us | 3.04 us | -91.0%
(11.15x faster) |
| `primitive/i32/small_list/list=4/match=50%` | 32.63 us | 3.08 us |
-90.5% (10.58x faster) |
| `primitive/i64/small_list/list=4/match=50%` | 33.55 us | 3.18 us |
-90.5% (10.54x faster) |
| `timestamp_ns/small_list/list=4/match=0%` | 19.57 us | 3.18 us |
-83.8% (6.16x faster) |
| `f32/small_list/list=4/match=0%` | 18.14 us | 3.05 us | -83.2% (5.95x
faster) |
| `primitive/i32/small_list/list=4/match=0%` | 17.00 us | 3.04 us |
-82.1% (5.59x faster) |
| `primitive/i64/small_list/list=4/match=0%` | 17.12 us | 3.22 us |
-81.2% (5.31x faster) |
| `primitive/i32/small_list/list=16/match=50%/NOT_IN` | 31.98 us | 7.26
us | -77.3% (4.41x faster) |
| `nulls/primitive/i32/small_list/list=16/match=50%/nulls=20%` | 29.35
us | 7.32 us | -75.1% (4.01x faster) |
| `timestamp_ns/small_list/list=16/match=50%` | 45.32 us | 11.79 us |
-74.0% (3.84x faster) |
| `nulls/primitive/i32/small_list/list=16/match=50%/nulls=50%` | 25.89
us | 7.31 us | -71.8% (3.54x faster) |
| `nulls/primitive/i32/small_list/list=16/match=50%/nulls=20%/NOT_IN` |
26.05 us | 7.42 us | -71.5% (3.51x faster) |
| `interval_month_day_nano/small_list/list=4/match=50%` | 52.94 us |
15.52 us | -70.7% (3.41x faster) |
| `f32/small_list/list=32/match=50%` | 38.78 us | 13.27 us | -65.8%
(2.92x faster) |
| `primitive/i64/small_list/list=16/match=50%` | 29.46 us | 11.76 us |
-60.1% (2.50x faster) |
<details>
<summary>Full relevant table (39 rows)</summary>
| Benchmark | Before | After | Change |
|---|---:|---:|---:|
| `narrow_integer/u8/list=4/match=0%` | 3.86 us | 2.79 us | -27.8%
(1.38x faster) |
| `narrow_integer/u8/list=4/match=50%` | 3.84 us | 2.78 us | -27.7%
(1.38x faster) |
| `narrow_integer/u8/list=16/match=0%` | 3.88 us | 3.85 us | -0.8%
(within noise) |
| `narrow_integer/u8/list=16/match=50%` | 3.84 us | 3.86 us | +0.5%
(within noise) |
| `narrow_integer/i16/list=4/match=0%` | 3.93 us | 3.18 us | -19.1%
(1.24x faster) |
| `narrow_integer/i16/list=4/match=50%` | 3.92 us | 3.16 us | -19.5%
(1.24x faster) |
| `narrow_integer/i16/list=64/match=0%` | 3.96 us | 3.82 us | -3.5%
(within noise) |
| `narrow_integer/i16/list=64/match=50%` | 3.91 us | 3.80 us | -2.9%
(within noise) |
| `narrow_integer/i16/list=256/match=0%` | 3.90 us | 3.81 us | -2.5%
(within noise) |
| `narrow_integer/i16/list=256/match=50%` | 3.97 us | 3.81 us | -4.1%
(within noise) |
| `narrow_integer/f16/list=4/match=0%` | 3.87 us | 3.16 us | -18.5%
(1.23x faster) |
| `narrow_integer/f16/list=4/match=50%` | 3.94 us | 3.15 us | -20.2%
(1.25x faster) |
| `narrow_integer/f16/list=64/match=0%` | 3.87 us | 3.84 us | -0.6%
(within noise) |
| `narrow_integer/f16/list=64/match=50%` | 3.93 us | 3.85 us | -1.9%
(within noise) |
| `narrow_integer/f16/list=256/match=0%` | 3.90 us | 3.84 us | -1.5%
(within noise) |
| `narrow_integer/f16/list=256/match=50%` | 3.87 us | 3.91 us | +1.2%
(within noise) |
| `nulls/narrow_integer/u8/list=16/match=50%/nulls=20%` | 3.92 us | 4.02
us | +2.5% (within noise) |
| `primitive/i32/small_list/list=4/match=0%` | 17.00 us | 3.04 us |
-82.1% (5.59x faster) |
| `primitive/i32/small_list/list=4/match=50%` | 32.63 us | 3.08 us |
-90.5% (10.58x faster) |
| `primitive/i32/small_list/list=32/match=0%` | 16.34 us | 13.33 us |
-18.5% (1.23x faster) |
| `primitive/i32/small_list/list=32/match=50%` | 31.17 us | 13.31 us |
-57.3% (2.34x faster) |
| `primitive/i32/small_list/list=16/match=50%/NOT_IN` | 31.98 us | 7.26
us | -77.3% (4.41x faster) |
| `nulls/primitive/i32/small_list/list=16/match=50%/nulls=20%` | 29.35
us | 7.32 us | -75.1% (4.01x faster) |
| `nulls/primitive/i32/small_list/list=16/match=50%/nulls=20%/NOT_IN` |
26.05 us | 7.42 us | -71.5% (3.51x faster) |
| `nulls/primitive/i32/small_list/list=16/match=50%/nulls=50%` | 25.89
us | 7.31 us | -71.8% (3.54x faster) |
| `primitive/i64/small_list/list=4/match=0%` | 17.12 us | 3.22 us |
-81.2% (5.31x faster) |
| `primitive/i64/small_list/list=4/match=50%` | 33.55 us | 3.18 us |
-90.5% (10.54x faster) |
| `primitive/i64/small_list/list=16/match=0%` | 16.34 us | 11.93 us |
-27.0% (1.37x faster) |
| `primitive/i64/small_list/list=16/match=50%` | 29.46 us | 11.76 us |
-60.1% (2.50x faster) |
| `f32/small_list/list=4/match=0%` | 18.14 us | 3.05 us | -83.2% (5.95x
faster) |
| `f32/small_list/list=4/match=50%` | 33.93 us | 3.04 us | -91.0%
(11.15x faster) |
| `f32/small_list/list=32/match=0%` | 22.05 us | 13.43 us | -39.1%
(1.64x faster) |
| `f32/small_list/list=32/match=50%` | 38.78 us | 13.27 us | -65.8%
(2.92x faster) |
| `timestamp_ns/small_list/list=4/match=0%` | 19.57 us | 3.18 us |
-83.8% (6.16x faster) |
| `timestamp_ns/small_list/list=4/match=50%` | 46.55 us | 3.17 us |
-93.2% (14.69x faster) |
| `timestamp_ns/small_list/list=16/match=0%` | 19.73 us | 12.07 us |
-38.8% (1.63x faster) |
| `timestamp_ns/small_list/list=16/match=50%` | 45.32 us | 11.79 us |
-74.0% (3.84x faster) |
| `interval_month_day_nano/small_list/list=4/match=0%` | 20.12 us |
13.20 us | -34.4% (1.52x faster) |
| `interval_month_day_nano/small_list/list=4/match=50%` | 52.94 us |
15.52 us | -70.7% (3.41x faster) |
</details>
---------
Co-authored-by: Andrew Lamb <an...@nerdnetworks.org>
---
.../physical-expr/benches/in_list_strategy.rs | 28 +-
.../physical-expr/src/expressions/in_list.rs | 18 +-
.../src/expressions/in_list/primitive_filter.rs | 483 ++++++++++++++++++++-
.../src/expressions/in_list/strategy.rs | 163 ++++++-
4 files changed, 661 insertions(+), 31 deletions(-)
diff --git a/datafusion/physical-expr/benches/in_list_strategy.rs b/datafusion/physical-expr/benches/in_list_strategy.rs
index c70f6da2a4..c69af192b9 100644
--- a/datafusion/physical-expr/benches/in_list_strategy.rs
+++ b/datafusion/physical-expr/benches/in_list_strategy.rs
@@ -37,6 +37,7 @@
//! | Narrow integer cases | Int16, Float16 | larger value domain | 4, 64, 256 |
//! | 32-bit primitive cases | Int32, Float32 | small and large lists | 4, 32, 64, 256 |
//! | 64-bit primitive cases | Int64, TimestampNs | small and large lists | 4, 16, 32, 128 |
+//! | 128-bit interval cases | IntervalMonthDayNano | small lists | 4 |
//! | Utf8 short-string cases | Utf8 | 8-byte strings | 4, 64, 256 |
//! | Utf8 long-string cases | Utf8 | 24-byte strings | 4, 64, 256 |
//! | Utf8View short-string cases | Utf8View | 8-byte strings | 4, 16, 64, 256 |
@@ -45,8 +46,9 @@
//! | Shared-prefix string cases | Utf8, Utf8View | same prefix, different suffix | 16, 32, 64 |
//! | Fixed-size binary cases | FixedSizeBinary(16) | fixed-width binary values | 4, 64, 256, 10000 |
+use arrow::array::types::IntervalMonthDayNano;
use arrow::array::*;
-use arrow::datatypes::{Field, Int32Type, Schema};
+use arrow::datatypes::{Field, Int32Type, IntervalMonthDayNanoType, Schema};
use arrow::record_batch::RecordBatch;
use criterion::{BenchmarkId, Criterion, criterion_group, criterion_main};
use datafusion_common::ScalarValue;
@@ -528,6 +530,28 @@ fn bench_timestamp_ns(c: &mut Criterion) {
}
}
+fn bench_interval_month_day_nano(c: &mut Criterion) {
+ for match_pct in MATCH_RATES {
+ bench_numeric::<IntervalMonthDayNano, IntervalMonthDayNanoArray>(
+ c,
+ "interval_month_day_nano",
+ &format!("small_list/list=4/match={match_pct}%"),
+ &NumericBenchConfig::new(
+ 4,
+ match_pct as f64 / 100.0,
+ |rng| {
+ IntervalMonthDayNanoType::make_value(
+ rng.random_range(-120..=120),
+ rng.random_range(-31..=31),
+ rng.random_range(-1_000_000_000..=1_000_000_000),
+ )
+ },
+ |v| ScalarValue::IntervalMonthDayNano(Some(v)),
+ ),
+ );
+ }
+}
+
// =============================================================================
// UTF8 STRING CASE BENCHMARKS
// =============================================================================
@@ -1049,7 +1073,7 @@ fn bench_fixed_size_binary(c: &mut Criterion) {
criterion_group! {
name = benches;
config = Criterion::default();
- targets = bench_narrow_integer, bench_primitive, bench_f32, bench_timestamp_ns, bench_utf8, bench_utf8view, bench_dictionary, bench_nulls, bench_fixed_size_binary
+ targets = bench_narrow_integer, bench_primitive, bench_f32, bench_timestamp_ns, bench_interval_month_day_nano, bench_utf8, bench_utf8view, bench_dictionary, bench_nulls, bench_fixed_size_binary
}
criterion_main!(benches);
diff --git a/datafusion/physical-expr/src/expressions/in_list.rs b/datafusion/physical-expr/src/expressions/in_list.rs
index 2764083f31..e4ec72285c 100644
--- a/datafusion/physical-expr/src/expressions/in_list.rs
+++ b/datafusion/physical-expr/src/expressions/in_list.rs
@@ -2900,10 +2900,9 @@ mod tests {
#[test]
fn test_in_list_esoteric_types() -> Result<()> {
- // Test esoteric/less common types to validate the transform and mapping flow.
- // These types are reinterpreted to base primitive types (e.g., Timestamp -> UInt64,
- // Interval -> Decimal128, Float16 -> UInt16). We just need to verify basic
- // functionality works - no need for comprehensive null handling tests.
+ // Test less common types covered by IN-list evaluation. Some of these
+ // use specialized filters, and others fall back to the generic path;
+ // this keeps the end-to-end behavior covered either way.
// Helper: simple IN test that expects [Some(true), Some(false)]
let test_type = |data_type: DataType,
@@ -2926,7 +2925,7 @@ mod tests {
Ok(())
};
- // Timestamp types (all units map to Int64 -> UInt64)
+ // Timestamp types
test_type(
DataType::Timestamp(TimeUnit::Second, None),
Arc::new(TimestampSecondArray::from(vec![Some(1000), Some(2000)])),
@@ -2960,7 +2959,7 @@ mod tests {
],
)?;
- // Time32 and Time64 (map to Int32 -> UInt32 and Int64 -> UInt64 respectively)
+ // Time32 and Time64
test_type(
DataType::Time32(TimeUnit::Second),
Arc::new(Time32SecondArray::from(vec![Some(3600), Some(7200)])),
@@ -3006,7 +3005,7 @@ mod tests {
],
)?;
- // Duration types (map to Int64 -> UInt64)
+ // Duration types
test_type(
DataType::Duration(TimeUnit::Second),
Arc::new(DurationSecondArray::from(vec![Some(86400), Some(172800)])),
@@ -3052,7 +3051,7 @@ mod tests {
],
)?;
- // Interval types (map to 16-byte Decimal128Type)
+ // Interval types
test_type(
DataType::Interval(IntervalUnit::YearMonth),
Arc::new(IntervalYearMonthArray::from(vec![Some(12), Some(24)])),
@@ -3114,8 +3113,7 @@ mod tests {
],
)?;
- // Decimal256 (maps to Decimal128Type for 16-byte width)
- // Need to use with_precision_and_scale() to set the metadata
+ // Decimal256. Need to use with_precision_and_scale() to set the metadata.
let precision = 38;
let scale = 10;
test_type(
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 8f8d9bad04..e802e1d024 100644
--- a/datafusion/physical-expr/src/expressions/in_list/primitive_filter.rs
+++ b/datafusion/physical-expr/src/expressions/in_list/primitive_filter.rs
@@ -19,14 +19,15 @@
//!
//! This module provides membership tests for Arrow primitive types.
-use arrow::array::{Array, ArrayRef, AsArray, BooleanArray};
-use arrow::buffer::{BooleanBuffer, NullBuffer};
+use arrow::array::{Array, ArrayRef, AsArray, BooleanArray, PrimitiveArray};
+use arrow::buffer::{BooleanBuffer, NullBuffer, 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 super::result::build_in_list_result;
+use super::result::{build_in_list_result, build_result_from_contains};
use super::static_filter::{StaticFilter, handle_dictionary};
/// Storage for the bits used by [`BitmapFilter`].
@@ -222,6 +223,276 @@ 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)]
@@ -430,7 +701,9 @@ mod tests {
use std::sync::Arc;
use arrow::array::{
- DictionaryArray, Float16Array, Int8Array, Int16Array, UInt8Array, UInt16Array,
+ Decimal128Array, DictionaryArray, Float16Array, Float32Array, Float64Array,
+ Int8Array, Int16Array, IntervalMonthDayNanoArray, TimestampMillisecondArray,
+ TimestampNanosecondArray, UInt8Array, UInt16Array,
};
use half::f16;
@@ -584,4 +857,206 @@ 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 9db90ea4fa..be4dce8dfd 100644
--- a/datafusion/physical-expr/src/expressions/in_list/strategy.rs
+++ b/datafusion/physical-expr/src/expressions/in_list/strategy.rs
@@ -20,7 +20,13 @@ use std::sync::Arc;
use arrow::array::ArrayRef;
use arrow::compute::cast;
use arrow::datatypes::{
- DataType, Float16Type, Int8Type, Int16Type, UInt8Type, UInt16Type,
+ DataType, Date32Type, Date64Type, Decimal128Type, DurationMicrosecondType,
+ DurationMillisecondType, DurationNanosecondType, DurationSecondType, Float16Type,
+ Float32Type, Float64Type, Int8Type, Int16Type, Int32Type, Int64Type,
+ IntervalMonthDayNanoType, IntervalUnit, Time32MillisecondType, Time32SecondType,
+ Time64MicrosecondType, Time64NanosecondType, TimeUnit, TimestampMicrosecondType,
+ TimestampMillisecondType, TimestampNanosecondType, TimestampSecondType, UInt8Type,
+ UInt16Type, UInt32Type, UInt64Type,
};
use datafusion_common::Result;
@@ -28,24 +34,88 @@ use super::array_static_filter::ArrayStaticFilter;
use super::primitive_filter::*;
use super::static_filter::StaticFilter;
-pub(super) fn instantiate_static_filter(
- in_array: ArrayRef,
-) -> Result<Arc<dyn StaticFilter + Send + Sync>> {
+type StaticFilterRef = Arc<dyn StaticFilter + Send + Sync>;
+
+pub(super) fn instantiate_static_filter(in_array: ArrayRef) -> Result<StaticFilterRef> {
+ let in_array = flatten_dictionary_haystack(in_array)?;
+
+ if let Some(filter) = instantiate_branchless_filter(&in_array)? {
+ return Ok(filter);
+ }
+
+ instantiate_standard_filter(in_array)
+}
+
+fn flatten_dictionary_haystack(in_array: ArrayRef) -> Result<ArrayRef> {
// Flatten dictionary-encoded haystacks to their value type so that
// specialized filters (e.g. Int32StaticFilter) are used instead of
// falling through to the generic ArrayStaticFilter.
- let in_array = match in_array.data_type() {
- DataType::Dictionary(_, value_type) => cast(&in_array, value_type.as_ref())?,
- _ => in_array,
- };
match in_array.data_type() {
- DataType::Int8 => Ok(Arc::new(BitmapFilter::<Int8Type>::try_new(&in_array)?)),
- DataType::UInt8 => Ok(Arc::new(BitmapFilter::<UInt8Type>::try_new(&in_array)?)),
- DataType::Int16 => Ok(Arc::new(BitmapFilter::<Int16Type>::try_new(&in_array)?)),
- DataType::UInt16 => Ok(Arc::new(BitmapFilter::<UInt16Type>::try_new(&in_array)?)),
- DataType::Float16 => {
- Ok(Arc::new(BitmapFilter::<Float16Type>::try_new(&in_array)?))
+ DataType::Dictionary(_, value_type) => Ok(cast(&in_array, value_type.as_ref())?),
+ _ => Ok(in_array),
+ }
+}
+
+fn instantiate_branchless_filter(in_array: &ArrayRef) -> Result<Option<StaticFilterRef>> {
+ let non_null_count = in_array.len() - in_array.null_count();
+
+ macro_rules! filter {
+ ($arrow_type:ty) => {
+ branchless_filter::<$arrow_type>(in_array, non_null_count)
+ };
+ }
+
+ match in_array.data_type() {
+ DataType::Int8 => filter!(Int8Type),
+ DataType::UInt8 => filter!(UInt8Type),
+ DataType::Int16 => filter!(Int16Type),
+ DataType::UInt16 => filter!(UInt16Type),
+ DataType::Float16 => filter!(Float16Type),
+ DataType::Int32 => filter!(Int32Type),
+ DataType::UInt32 => filter!(UInt32Type),
+ DataType::Float32 => filter!(Float32Type),
+ DataType::Date32 => filter!(Date32Type),
+ DataType::Time32(unit) => match unit {
+ TimeUnit::Second => filter!(Time32SecondType),
+ TimeUnit::Millisecond => filter!(Time32MillisecondType),
+ _ => Ok(None),
+ },
+ DataType::Int64 => filter!(Int64Type),
+ DataType::UInt64 => filter!(UInt64Type),
+ DataType::Float64 => filter!(Float64Type),
+ DataType::Date64 => filter!(Date64Type),
+ DataType::Time64(unit) => match unit {
+ TimeUnit::Microsecond => filter!(Time64MicrosecondType),
+ TimeUnit::Nanosecond => filter!(Time64NanosecondType),
+ _ => Ok(None),
+ },
+ DataType::Timestamp(unit, _) => match unit {
+ TimeUnit::Second => filter!(TimestampSecondType),
+ TimeUnit::Millisecond => filter!(TimestampMillisecondType),
+ TimeUnit::Microsecond => filter!(TimestampMicrosecondType),
+ TimeUnit::Nanosecond => filter!(TimestampNanosecondType),
+ },
+ DataType::Duration(unit) => match unit {
+ TimeUnit::Second => filter!(DurationSecondType),
+ TimeUnit::Millisecond => filter!(DurationMillisecondType),
+ TimeUnit::Microsecond => filter!(DurationMicrosecondType),
+ TimeUnit::Nanosecond => filter!(DurationNanosecondType),
+ },
+ DataType::Decimal128(_, _) => filter!(Decimal128Type),
+ DataType::Interval(IntervalUnit::MonthDayNano) => {
+ filter!(IntervalMonthDayNanoType)
}
+ _ => Ok(None),
+ }
+}
+
+fn instantiate_standard_filter(in_array: ArrayRef) -> Result<StaticFilterRef> {
+ match in_array.data_type() {
+ DataType::Int8 => bitmap_filter::<Int8Type>(&in_array),
+ DataType::UInt8 => bitmap_filter::<UInt8Type>(&in_array),
+ DataType::Int16 => bitmap_filter::<Int16Type>(&in_array),
+ DataType::UInt16 => bitmap_filter::<UInt16Type>(&in_array),
+ DataType::Float16 => bitmap_filter::<Float16Type>(&in_array),
DataType::Int32 => Ok(Arc::new(Int32StaticFilter::try_new(&in_array)?)),
DataType::Int64 => Ok(Arc::new(Int64StaticFilter::try_new(&in_array)?)),
DataType::UInt32 => Ok(Arc::new(UInt32StaticFilter::try_new(&in_array)?)),
@@ -54,8 +124,71 @@ pub(super) fn instantiate_static_filter(
DataType::Float32 => Ok(Arc::new(Float32StaticFilter::try_new(&in_array)?)),
DataType::Float64 => Ok(Arc::new(Float64StaticFilter::try_new(&in_array)?)),
_ => {
- /* fall through to generic implementation for unsupported types (Struct, etc.) */
+ // Fall through to generic implementation for unsupported types
+ // (Struct, etc.).
Ok(Arc::new(ArrayStaticFilter::try_new(in_array)?))
}
}
}
+
+fn bitmap_filter<T>(in_array: &ArrayRef) -> Result<StaticFilterRef>
+where
+ T: BitmapFilterType,
+{
+ Ok(Arc::new(BitmapFilter::<T>::try_new(in_array)?))
+}
+
+fn branchless_filter<T>(
+ in_array: &ArrayRef,
+ non_null_count: usize,
+) -> Result<Option<StaticFilterRef>>
+where
+ T: BranchlessFilterType,
+ BranchlessNative<T>: Copy + PartialEq + Send + Sync,
+{
+ // Larger lists use the standard filter. `try_new` checks the limit again.
+ if non_null_count > T::MAX_LIST_LEN {
+ return Ok(None);
+ }
+
+ Ok(Some(Arc::new(BranchlessFilter::<T>::try_new(in_array)?)))
+}
+
+#[cfg(test)]
+mod tests {
+ use arrow::array::UInt32Array;
+ use arrow::datatypes::UInt32Type;
+
+ use super::super::primitive_filter::BranchlessFilterType;
+ use super::*;
+
+ fn uint32_array(values: Vec<Option<u32>>) -> ArrayRef {
+ Arc::new(UInt32Array::from(values))
+ }
+
+ #[test]
+ fn branchless_routing_respects_max_list_len() -> Result<()> {
+ let max_len = <UInt32Type as BranchlessFilterType>::MAX_LIST_LEN;
+
+ let values = (0..max_len)
+ .map(|value| Some(value as u32))
+ .collect::<Vec<_>>();
+ assert!(instantiate_branchless_filter(&uint32_array(values))?.is_some());
+
+ let values = (0..=max_len)
+ .map(|value| Some(value as u32))
+ .collect::<Vec<_>>();
+ assert!(instantiate_branchless_filter(&uint32_array(values))?.is_none());
+
+ Ok(())
+ }
+
+ #[test]
+ fn branchless_routing_handles_zero_non_null_values() -> Result<()> {
+ let array = uint32_array(vec![None; 3]);
+
+ assert!(instantiate_branchless_filter(&array)?.is_some());
+
+ Ok(())
+ }
+}
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datafusion.apache.org
For additional commands, e-mail: commits-help@datafusion.apache.org