Further improve performance of IN list evaluation

[geoffreyclaude]

Summary

IN LIST evaluates expressions like:

x IN (1, 3, 7)

The list on the right is constant, so DataFusion can build a lookup structure once and reuse it for every input row. This matters for dynamic filter pushdown, where these checks can run millions of times during large scans.

The goal of this stack is to pick a lookup strategy that matches the data type and list size, instead of sending every common case through the same generic comparator-based path.

The SQL behavior should stay the same, including IN, NOT IN, dictionaries, slices, and null handling. These are internal performance optimizations.

Current Stack

Review order follows this list:

• IN LIST: clean up generic static filtering #21927: clean up and optimize the generic static-filter fallback
• IN LIST: add UInt8 bitmap filter #23011: use a tiny bitmap checklist for UInt8
• IN LIST: add UInt16 bitmap filter #23012: extend bitmap lookup to UInt16
• IN LIST: unify bitmap filter implementations #23035: unify the UInt8 and UInt16 bitmap filter implementations
• IN LIST: reinterpret small-width types for bitmap filters #23013: let compatible signed 1-byte and 2-byte values reuse those bitmaps without copying
• IN LIST: add branchless filter for small primitive lists #23014: use direct comparisons for very small primitive lists
• IN LIST: add direct-probe hash filter for large primitive lists #23015: use a compact direct-probe lookup table for larger primitive lists
• IN LIST: add string-view filters for Utf8View and BinaryView #23016: use length/prefix rejection for Utf8View and BinaryView
• IN LIST: reinterpret FixedSizeBinary for primitive fast paths #23018: let supported FixedSizeBinary widths reuse the primitive fast paths (now stacked directly on IN LIST: add string-view filters for Utf8View and BinaryView #23016)

How The Optimizations Work

The stack is a sequence of small lookup improvements. Each PR keeps the same result semantics, but makes a common membership check cheaper.

Bitmap Lookup

For small integer domains, the IN list can be represented as a bitmap.

For UInt8, there are only 256 possible values. If the list contains 42, set bit 42. To check an input row with value 42, read bit 42.

That turns membership into one indexed bit test.

Reusing The Same Bytes

Some Arrow types have different meanings but the same physical width. For example, Int8 and UInt8 are both one byte wide.

The bitmap only cares about the exact bits, so compatible values can reuse the same lookup storage without copying the array. This is the “zero-copy reinterpretation” part of the stack.

Tiny Lists

For very small primitive lists, comparing directly can be cheaper than hashing.

For example:

x IN (10, 20, 30)

can be checked like:

x == 10 OR x == 20 OR x == 30

That is the branchless small-list path.

Larger Primitive Lists

Once primitive lists get larger, direct comparison is no longer the best fit. The stack then switches to a compact purpose-built lookup table for fixed-width primitive values.

This is still hash-table-style lookup, but it is simpler than the generic fallback because primitive values can be stored and probed directly.

Strings And Binary Views

Strings and binary values can be expensive to compare byte-for-byte. The string/view PRs first ask a cheaper question:

Could this value possibly match anything in the IN list?

Length and prefix checks can reject many non-matches quickly. If a value still looks like a possible match, long values are verified with exact byte comparison before returning true.

Fixed-Size Binary

FixedSizeBinary(1), (2), (4), (8), and (16) have fixed-width byte layouts that match the primitive-width optimizations above.

Those values can reuse the bitmap, branchless, and direct-probe paths internally. Other fixed-size binary widths stay on the generic fallback.

Expected Impact

Reference benchmarks from #19390 show the largest wins in areas where the old path did much more work than necessary:

Area	Why it can be faster
UInt8 / UInt16	one bitmap bit test per input value
Small primitive lists	direct comparisons avoid hash-table overhead
Larger primitive lists	compact fixed-width lookup avoids the generic comparator path
Date, timestamp, float, and signed integer paths	same-width values can reuse primitive fast paths
Utf8View / BinaryView	length and prefix checks reject many non-matches cheaply
FixedSizeBinary supported widths	fixed-width byte values can reuse primitive lookup machinery

The detailed benchmark numbers live in #19390 and have been refreshed in the dedicated PRs as review changes the stack. #23017 was closed because its local benchmark snapshot did not justify the added regular Utf8 / LargeUtf8 path.

Implementation Plan

• Land IN LIST: clean up generic static filtering #21927 to clean up and optimize the generic static-filter fallback
• Land IN LIST: add UInt8 bitmap filter #23011 to add bitmap filters for 1-byte values
• Land IN LIST: add UInt16 bitmap filter #23012 to extend bitmap filters to 2-byte values
• Land IN LIST: unify bitmap filter implementations #23035 to unify the bitmap filter implementations
• Land IN LIST: reinterpret small-width types for bitmap filters #23013 to add zero-copy reinterpretation for compatible fixed-width values
• Land IN LIST: add branchless filter for small primitive lists #23014 to add branchless filters for small primitive lists
• Land IN LIST: add direct-probe hash filter for large primitive lists #23015 to add direct-probe hash filters for larger primitive lists
• Land IN LIST: add string-view filters for Utf8View and BinaryView #23016 to add optimized filters for Utf8View / BinaryView
• Land IN LIST: reinterpret FixedSizeBinary for primitive fast paths #23018 to add FixedSizeBinary reinterpretation for supported widths
• Drop IN LIST: add two-stage filter for Utf8 and LargeUtf8 #23017 after local benchmarks showed regressions for regular Utf8 / LargeUtf8

Additional Context

• Follow-up to Restore IN_LIST performance -- Implement specialized StaticFilters for different data types #18824
• Original reference implementation: Optimize IN performance with specialized implementations #19390
• Thresholds are benchmark-driven and may be adjusted during review

[adriangb]

Amazing plan!

[Dandandan]

What about slice::contains? Seems like it should be somewhere between the const-sized approach and binary search in terms of threshold window.

[adriangb]

There is a related bit of work to untangle with is the ScalarValue references that InListExpr is forced to use even if we are starting from an array. It uses these to look up in bloom filters, do predicate pruning, etc. We could make all of the relevant APIs work with an enum of Vec<ScalarValue> (heterogenous lists) or ArrayRefs (homogenous lists) and that would avoid converting array -> ScalarValue and then in some places back to an array (deep in pruning code iirc). Some of this is planning time / build time stuff so it is amortized over the data scans, but some of it happens for each file opened. It's not as big as for each row, but it adds up.

A second thing is that col IN (...) is inefficient when it hits a bloom filter on col if the list is large because it loops over the values in the list. I'm not sure how or where we would do this but in theory we could build a bloom filter out of the InListExpr and then do a binary operation between that bloom filter and Parque's bloom filter instead of looping over each item in the list and looking it up in the columns bloom filter. At the very least if we did the point above and pushed down an array we could probably be more efficient about converting all of the values into something we can look up in the bloom filter (currently it goes through ScalarValue).

[geoffreyclaude]

What about slice::contains? Seems like it should be somewhere between the const-sized approach and binary search in terms of threshold window.

It loses all the time against the branchless and the binary search. slice::contains is just a wrapper around:

self.iter().any(|y| y == x)

So it needs to do bounds checks and can't optimize for the small arrays.

[Dandandan]

What about slice::contains? Seems like it should be somewhere between the const-sized approach and binary search in terms of threshold window.

It loses all the time against the branchless and the binary search. slice::contains is just a wrapper around:

self.iter().any(|y| y == x)
So it needs to do bounds checks and can't optimize for the small arrays.

Hmm interesting. I would have thought it would be faster somwehere in between.
Note it is not equal to self.iter().any(|y| y == x), slice::contains is specialized for primitive types to create unrolled/vectorized code.

[geoffreyclaude]

@Dandandan See geoffreyclaude#14 for an in-depth micro benchmark and analysis of the different search algorithms.

TL;DR: It's always branchless up to the SIMD limit, then hashset.

Slice Search Benchmark

[geoffreyclaude]

I've opened #19376 as a preliminary PR to extend the benchmarks.

[alamb]

2. Type Normalization

Note you can potentially use the RowFormat for this purpose - https://docs.rs/arrow-row/latest/arrow_row/, perhaps as a fallback when more general methods aren't available

It handles pretty much every arrow type

The downside is that the input needs to be first converted into row format