geoffreyclaude opened a new pull request, #24088: URL: https://github.com/apache/datafusion/pull/24088
## Which issue does this PR close? - Part of #19241. - Standalone alternative to [#23016](https://github.com/apache/datafusion/pull/23016), based directly on `main`. - Leaves the existing [#23015](https://github.com/apache/datafusion/pull/23015) -> [#23016](https://github.com/apache/datafusion/pull/23016) -> [#23018](https://github.com/apache/datafusion/pull/23018) stack unchanged while this version is iterated. - Extracted from #19390. ## Rationale for this change Arrow `Utf8View` and `BinaryView` arrays store each value in a 128-bit view. Values up to 12 bytes are fully inline. Longer values keep their length and four-byte prefix in the view and store the remaining bytes separately. That representation allows cheap rejection without hashing or comparing complete strings. Inline values can be matched exactly from the view itself; long candidates are always confirmed against their full bytes before reporting a match. ## What changes are included in this PR? - Adds branchless matching for all-inline lists up to four values. - Adds a standard DataFusion `HashSet<u128>` for larger inline lists. - Adds a mixed byte-view filter that uses a standard `HashSet<u128>` of view keys for rejection and a native `HashTable` for exact long-value confirmation. - Specializes only measured winning shapes and keeps all-long or inline-dominant mixed lists on the generic fallback. - Requires exact byte-view physical types after recursively unwrapping dictionary expression types. - Skips membership work for null needles while preserving `IN` and `NOT IN` semantics. - Covers slices, dictionaries, `Utf8View`, `BinaryView`, nulls, physical-type routing, and long-prefix collisions. ## Are these changes tested? Yes. - `cargo fmt --all` - `cargo test -p datafusion-physical-expr --lib expressions::in_list` - `cargo clippy --all-targets --all-features -- -D warnings` - `./dev/rust_lint.sh` - `RUST_BACKTRACE=1 cargo test --profile ci --exclude datafusion-examples --exclude datafusion-benchmarks --exclude datafusion-cli --workspace --lib --tests --bins --features avro,json,backtrace,extended_tests,recursive_protection,parquet_encryption` ## Are there any user-facing changes? No. This is an internal performance optimization only. ## Local benchmark snapshot Built and run in separate target directories, using identical benchmark source and filtering to the relevant byte-view rows: ```bash cargo bench --target-dir <target-dir> -p datafusion-physical-expr --bench in_list_strategy -- <filter> ``` Filters used: `utf8view/short_8b` (also matching `nulls/utf8view/short_8b`), `utf8view/len_12b`, and `utf8view/mixed_len`. Method: directly compared Criterion median point estimates. Filter construction remains outside the timed loop. Lower is better; changes within +/-5% are treated as noise. Compared baselines: [`main` at `db0c31bfe1`](https://github.com/apache/datafusion/commit/db0c31bfe16628ed6118ea3fc5d4002c8f2365fb) -> this PR Relevant scope: all-inline `Utf8View` rows, mixed inline/long shapes, the inline-dominant fallback, and nullable inline views. `BinaryView` uses the same physical view representation and filter implementation. Summary: 23 relevant rows, 20 faster, 0 slower, 3 within +/-5%. The inline-dominant mixed rows remain within noise, supporting the conservative fallback for that shape. Largest relevant deltas: | Benchmark | Before | After | Change | |---|---:|---:|---:| | `utf8view/short_8b/list=4/match=50%` | 50.11 us | 12.54 us | -75.0% (4.00x faster) | | `nulls/utf8view/short_8b/list=16/match=50%/nulls=50%` | 62.02 us | 20.98 us | -66.2% (2.96x faster) | | `nulls/utf8view/short_8b/list=16/match=50%/nulls=20%/NOT_IN` | 57.65 us | 33.52 us | -41.9% (1.72x faster) | | `nulls/utf8view/short_8b/list=16/match=50%/nulls=20%` | 54.89 us | 32.17 us | -41.4% (1.71x faster) | | `utf8view/short_8b/list=4/match=0%` | 18.72 us | 12.48 us | -33.3% (1.50x faster) | | `utf8view/mixed_len/list=16/match=0%` | 44.91 us | 30.53 us | -32.0% (1.47x faster) | | `utf8view/len_12b/list=64/match=50%` | 51.20 us | 35.17 us | -31.3% (1.46x faster) | | `utf8view/mixed_len/list=64/match=0%` | 43.96 us | 30.91 us | -29.7% (1.42x faster) | | `utf8view/mixed_len/inline=2%/list=64/match=0%` | 45.80 us | 32.81 us | -28.4% (1.40x faster) | | `utf8view/short_8b/list=64/match=50%` | 52.41 us | 38.47 us | -26.6% (1.36x faster) | <details> <summary>Full relevant table (23 rows)</summary> | Benchmark | Before | After | Change | |---|---:|---:|---:| | `utf8view/short_8b/list=4/match=0%` | 18.72 us | 12.48 us | -33.3% (1.50x faster) | | `utf8view/short_8b/list=4/match=50%` | 50.11 us | 12.54 us | -75.0% (4.00x faster) | | `utf8view/short_8b/list=16/match=0%` | 19.50 us | 16.18 us | -17.0% (1.20x faster) | | `utf8view/short_8b/list=16/match=50%` | 51.56 us | 38.94 us | -24.5% (1.32x faster) | | `utf8view/short_8b/list=64/match=0%` | 19.62 us | 16.78 us | -14.5% (1.17x faster) | | `utf8view/short_8b/list=64/match=50%` | 52.41 us | 38.47 us | -26.6% (1.36x faster) | | `utf8view/short_8b/list=256/match=0%` | 19.58 us | 17.27 us | -11.8% (1.13x faster) | | `utf8view/short_8b/list=256/match=50%` | 52.05 us | 38.48 us | -26.1% (1.35x faster) | | `utf8view/len_12b/list=16/match=0%` | 18.57 us | 14.97 us | -19.4% (1.24x faster) | | `utf8view/len_12b/list=16/match=50%` | 48.84 us | 39.33 us | -19.5% (1.24x faster) | | `utf8view/len_12b/list=64/match=0%` | 18.73 us | 16.04 us | -14.4% (1.17x faster) | | `utf8view/len_12b/list=64/match=50%` | 51.20 us | 35.17 us | -31.3% (1.46x faster) | | `utf8view/mixed_len/list=16/match=0%` | 44.91 us | 30.53 us | -32.0% (1.47x faster) | | `utf8view/mixed_len/list=16/match=50%` | 113.85 us | 86.18 us | -24.3% (1.32x faster) | | `utf8view/mixed_len/list=64/match=0%` | 43.96 us | 30.91 us | -29.7% (1.42x faster) | | `utf8view/mixed_len/list=64/match=50%` | 117.51 us | 91.15 us | -22.4% (1.29x faster) | | `utf8view/mixed_len/inline=2%/list=64/match=0%` | 45.80 us | 32.81 us | -28.4% (1.40x faster) | | `utf8view/mixed_len/inline=2%/list=64/match=50%` | 111.82 us | 107.16 us | -4.2% (within noise) | | `utf8view/mixed_len/inline=98%/list=64/match=0%` | 23.27 us | 22.59 us | -2.9% (within noise) | | `utf8view/mixed_len/inline=98%/list=64/match=50%` | 59.50 us | 59.42 us | -0.1% (within noise) | | `nulls/utf8view/short_8b/list=16/match=50%/nulls=20%` | 54.89 us | 32.17 us | -41.4% (1.71x faster) | | `nulls/utf8view/short_8b/list=16/match=50%/nulls=20%/NOT_IN` | 57.65 us | 33.52 us | -41.9% (1.72x faster) | | `nulls/utf8view/short_8b/list=16/match=50%/nulls=50%` | 62.02 us | 20.98 us | -66.2% (2.96x faster) | </details> -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
