DataFusion's Branchless IN Filter: Why x IN (10, 20, 30) Is Faster Than Building a Hash Table

TL;DR: WHERE status IN ('new', 'pending', 'paid') looks like it should be a hash lookup, but for a short list a hash table is slower: you pay for the table, and the hash is a serial dependency. DataFusion instead compares the input against every value in the list and combines the results with a non-short-circuiting |. The regular, branch-free comparison sequence is something the CPU can vectorise, and for a list of three or ten values that beats a hash lookup outright. The choice of strategy is made per type and per list length, at plan time.

IN lists are everywhere. WHERE id IN (1, 2, 3). WHERE country IN ('US', 'GB', 'DE'). WHERE tenant_id IN (...) with a hundred values. They look like a simple membership test, and Arrow provides arrow::compute::kernels::filter::is_in, which builds a hash table and probes it.

But building a hash table for three values is absurd. The table costs an allocation, a hash per value, a probe per input row, and — crucially — a branch per probe, which the branch predictor cannot learn.

DataFusion’s InListExpr has a whole family of specialised filters for this, and picking the right one is a genuinely interesting piece of engineering. The code lives in datafusion/physical-expr/src/expressions/in_list/ — nine files, about 2,400 lines — and the entry point is a strategy chooser.

The strategy chooser

rust
// datafusion/physical-expr/src/expressions/in_list/strategy.rs
pub(super) fn instantiate_static_filter(
    in_array: ArrayRef,
    needle_data_type: &DataType,
) -> Result<StaticFilterRef> {
    let in_array = flatten_dictionary_haystack(in_array)?;

    let filter = if view_types_match(needle_data_type, in_array.data_type())
        && let Some(filter) = instantiate_byte_view_filter(&in_array)?
    {
        filter
    } else if let Some(filter) = instantiate_fixed_size_binary_filter(&in_array)? {
        filter
    } else if let Some(filter) = instantiate_primitive_filter(&in_array)? {
        filter
    } else {
        Arc::new(ArrayStaticFilter::try_new(in_array)?)
    };

    // Plain inputs can call the concrete filter directly. Dictionary inputs
    // share one adapter across all concrete filter types.
    if matches!(needle_data_type, DataType::Dictionary(_, _)) {
        Ok(Arc::new(DictionaryFilter::new(filter)))
    } else {
        Ok(filter)
    }
}

Read it as a cascade: try the most specific filter that applies, fall back to the generic one. The generic fallback is ArrayStaticFilter — an Arrow-array-backed filter that works for any type at the cost of a linear scan.

Note the order: byte-view, then fixed-size-binary, then primitive, then generic. The specialised ones are tried first because they know the memory layout and can do better.

The dictionary handling is a nice touch. A dictionary-encoded column wraps a value array in an index array. The values are what the IN list matches against, so the filter is built on the flattened values and a DictionaryFilter adapter maps indices back. And the flattening is recursive:

rust
fn flatten_dictionary_haystack(mut in_array: ArrayRef) -> Result<ArrayRef> {
    // Flatten every dictionary layer so the final value type can use a
    // specialized filter.
    while let Some(dictionary) = in_array.as_any_dictionary_opt() {
        in_array = take(dictionary.values().as_ref(), dictionary.keys(), None)?;
    }

    Ok(in_array)
}

A dictionary of a dictionary is a real thing, and this handles it.

The branchless filter

Here is the centrepiece. branchless_filter.rs opens with an explanation that reads like a textbook on micro-optimisation:

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.

The kernel is twelve lines:

rust
#[inline]
#[expect(
    clippy::needless_bitwise_bool,
    reason = "the non-short-circuiting `|` is the point of this branchless kernel"
)]
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))
    })
}

Three things to notice.

const N: usize. The list length is a compile-time constant in this function. The list is stored as &[C; N], a fixed-size array reference, so the loop over the list values is fully unrolled by the compiler: N comparisons, no loop counter, no bounds check on the list.

| not ||. The #[expect(clippy::needless_bitwise_bool, ...)] attribute is a confession: Clippy wants ||, and the code deliberately uses |. With ||, the compiler emits a branch per comparison and the loop over the list is data-dependent. With |, every comparison is executed unconditionally, the results are OR-ed together, and the CPU can issue the comparisons in parallel. The expect attribute with an explanation is the right way to fight the linter here — a #[allow] with no comment would just be a mystery later.

get_unchecked. The input index is unchecked, with a SAFETY comment justifying it: collect_bool guarantees the closure is called for indices in 0..input_values.len(). This is the standard Arrow-kernel idiom — eliminate the bounds check from the innermost loop.

The size limits, and why they are what they are

The maximum list length for the branchless path is not arbitrary, and the source explains each one:

rust
/// 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, ...
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. ...
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.
const BRANCHLESS_MAX_16B: usize = 4;

The 1-byte and 2-byte limits are SIMD limits: 16 bytes fit in one XMM register, 8 two-byte values fit in one XMM register. The 4-byte and 8-byte limits are cache-line limits: 32 × 4 bytes = 128 bytes = one cache line, 16 × 8 bytes = 128 bytes = one cache line. The 16-byte limit is 4 values because the comparisons are so wide that the chain gets unwieldy.

The module header explains the interaction with the bitmap filter:

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.

The bitmap filter

For 1- and 2-byte types, there is a strictly better structure than both the branchless chain and a hash table: a bitmap of the entire value space. 256 possible byte values, 65,536 possible 16-bit values.

rust
struct BitmapFilter<T: BitmapFilterType> {
    null_count: usize,
    bits: T::Storage,
}

fn try_new(in_array: &ArrayRef) -> Result<Self> {
    ...
    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))
}

The membership test is a single bit lookup. The entire filter for a 256-element byte domain is 32 bytes — four cache lines, or one if you are lucky. This is the classic “direct lookup table” optimisation, and it is strictly better than a hash set for small domains: no hashing, no probing, no collisions, one memory access.

The construction handles nulls by iterating only the valid rows via BitIndexIterator — the null entries are simply not set in the bitmap, and their count is remembered so the SQL null semantics can be applied later.

The hash set filter

For 4-byte and 8-byte types, the domain is too large for a bitmap, so the choice is between the branchless chain and a hash set. The hash set wins for long lists:

rust
DataType::Int32 => {
    Arc::new(PrimitiveHashSetFilter::<Int32Type>::try_new(in_array)?)
}
DataType::Int64 => {
    Arc::new(PrimitiveHashSetFilter::<Int64Type>::try_new(in_array)?)
}

and for floats, the set needs an ordered wrapper to be a valid hash map key:

rust
// Float primitive types use ordered wrapper keys for Hash/Eq.
DataType::Float32 => Arc::new(PrimitiveHashSetFilter::<
    Float32Type,
    OrderedFloat32,
>::try_new(in_array)?),

OrderedFloat32 is the standard trick: f32 does not implement Eq or Hash because NaN != NaN and 0.0 != -0.0. Wrapping it in a total-order newtype makes it usable as a key. Note that this is the opposite choice from the branchless filter, which compares floats by their raw bit pattern and deliberately preserves the 0.0 vs -0.0 distinction.

The bit-pattern trick

The branchless filter’s type mapping is one of the more surprising bits of the code:

rust
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!(Float32Type, UInt32Type, BRANCHLESS_MAX_4B);
branchless_filter_type!(Int64Type, UInt64Type, BRANCHLESS_MAX_8B);

Float32 is compared as UInt32. Int64 as UInt64. And the reason is in the module header:

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.

So the filter does not copy the values into a Vec<u32> — it reinterprets the existing Arrow buffer as unsigned integers. branchless_values does this with zero copies:

rust
fn branchless_values<T>(array: &PrimitiveArray<T>) -> ScalarBuffer<BranchlessNative<T>>
where
    T: BranchlessFilterType,
{
    let values = array.values();
    // `values.inner()` already reflects any slice applied to the array.
    ScalarBuffer::<BranchlessNative<T>>::new(values.inner().clone(), 0, values.len())
}

Hmm — one thing to note: the clone of the inner Buffer is cheap (it is a reference-counted Bytes handle), but it is not free, and the values buffer is shared rather than copied. The type-level assert! on the size equality is a compile-time guard against a future edit that maps a type to a different-width comparison type, which would be a memory-safety bug.

The float bit-pattern comparison is not the same as float equality: 0.0 and -0.0 have different bit patterns, so x IN (0.0) would be false for -0.0. For a membership test against a list, the set semantics are preserved (the list contains 0.0; -0.0 is not in it), but the ordering is by bit pattern, not by numeric value. Whether that matters depends on the semantics you want. The comment says the choice is deliberate.

SQL null semantics

Every one of these filters has to reproduce SQL’s three-valued logic: x IN (1, NULL) is NULL (not false) when x is not 1, because the list contains a NULL. And x NOT IN (1, NULL) is NULL for every x.

The filters handle this by separating the membership computation from the null computation:

rust
Ok(build_result_from_contains(
    v.nulls(),          // nulls in the input
    self.null_count > 0, // nulls in the IN list
    negated,
    matches,
))

The membership bitmask is computed first, and the null rules are applied afterwards, in one place, for all filter types. The result.rs module is 111 lines and does exactly that — it is the single source of truth for IN/NOT IN null semantics in the whole engine.

The doc comment in the branchless filter spells out the flow:

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.

The catch

The IN list must be constant. The whole static-filter machinery depends on the list being a compile-time-known array. InListExpr::try_new evaluates the list expressions at plan time; if they are not constant, static_filter is None and the expression falls back to a per-batch evaluation.
The filter is built at plan time and lives as long as the plan. For a plan with a million-element IN list, that is a million elements of memory held for the duration of the query — and the hash set is built once, so it amortises.
The specialisation is per type and per list length. The membership_check_for_len function generates a function pointer per supported length:
rust
```
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, ...),
    _ => unreachable!("list-size limits must be 4, 8, 16, or 32"),
}
```
The comment explains why: “Keeping the length out of BranchlessFilter avoids generating a full copy of the filter for every supported length.” So the kernel is monomorphised per length, but the filter struct is not — the length is a function pointer stored in the struct. A clever compromise between code size and inner-loop efficiency.
The bit-pattern comparison for floats is not numeric equality. It distinguishes 0.0 from -0.0 and different NaN payloads. For IN list membership this is arguably more correct than float equality, but it is a deliberate deviation from == and worth knowing about.
Only primitives, byte views and fixed-size binaries get the good treatment. Strings (Utf8) fall back to ArrayStaticFilter, which does a linear scan with Arrow’s equality kernel. A Utf8 IN list of ten strings is a linear scan per batch.

The general lesson

The lesson is not “avoid hash tables” — it is match the data structure to the domain. A 256-element domain has a perfect data structure: a bitmap. A three-element list has a perfect data structure: three comparisons. A million-element list of 64-bit integers has a perfect data structure: a hash set. DataFusion encodes all three, plus a generic fallback, and picks between them at plan time based on the type and the length.

And the “branchless” trick generalises beyond IN: the same idea — a fixed, regular, data-independent sequence of operations that the CPU can pipeline — is what makes SIMD worthwhile at all. The | is not just shorter than ||; it is the thing that makes the comparison chain vectorisable.