geoffreyclaude opened a new pull request, #24102: URL: https://github.com/apache/datafusion/pull/24102
## Which issue does this PR close? - Part of #19241. - Standalone adaptation of [#23018](https://github.com/apache/datafusion/pull/23018), based directly on `main`. - Can be reviewed independently alongside [#24088](https://github.com/apache/datafusion/pull/24088). - Extracted from #19390. ## Rationale for this change `FixedSizeBinary(1)`, `(2)`, `(4)`, `(8)`, and `(16)` values occupy fixed-width buffer slots matching native integer widths. Reinterpreting each slot as an equal-width primitive is a bijection over its byte pattern, so equality and hashing preserve opaque byte equality. This lets `IN LIST` use the same strategies that are effective for primitives: bitmap membership for widths 1 and 2, and branchless comparisons or standard hash lookup for widths 4, 8, and 16. ## What changes are included in this PR? - Reuses bitmap filters for widths 1 and 2. - Reuses the existing branchless comparison thresholds for widths 4, 8, and 16. - Uses the standard DataFusion `HashSet`, keyed by the exact native-width representation, for larger lists. - Reinterprets normally aligned Arrow buffers without copying and safely copies valid unaligned buffers with `read_unaligned`. - Requires concrete `FixedSizeBinary` arrays with the exact configured width. - Keeps unsupported widths and custom haystacks on `ArrayStaticFilter`; wrong-width or custom needles return errors. - Covers every supported width, both sides of each strategy threshold, slices, dictionaries, nulls, aligned and unaligned buffers, and end-to-end `InListExpr` evaluation. - Adds a 20-row benchmark matrix spanning bitmap, branchless, and hash-set paths with miss-only and 50%-hit workloads. ## Are these changes tested? Yes. - `cargo fmt --all` - `cargo test -p datafusion-physical-expr --lib expressions::in_list` (76 passed) - `cargo clippy -p datafusion-physical-expr --all-targets --all-features -- -D warnings` - `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` The full-workspace `cargo clippy --all-targets --all-features -- -D warnings` currently stops on an existing Rust 1.97 `uninlined_format_args` warning in generated `datafusion/proto-common/src/generated/pbjson.rs`, unchanged from the compared `main` commit. Strict Clippy for the modified package passes. ## Are there any user-facing changes? No. This is an internal performance optimization only. ## Local benchmark snapshot Built and run in separate target directories after other compilation completed, using identical benchmark source and filtering to the fixed-size binary rows: ```bash cargo bench --target-dir <target-dir> \ -p datafusion-physical-expr \ --bench in_list_strategy -- fixed_size_binary --noplot ``` Method: Criterion defaults (3-second warm-up, 5-second measurement, 100 samples), comparing median point estimates. Filter construction remains outside the timed loop. Lower is better; changes within +/-5% are treated as noise. Compared baselines: [`main` at `426b351513`](https://github.com/apache/datafusion/commit/426b351513be6317734aa2e425ac72ddde790fb4) -> this PR Relevant scope: `FixedSizeBinary(1)`, `(2)`, `(4)`, `(8)`, and `(16)` across bitmap, branchless, and standard `HashSet` paths. Summary: 20 relevant rows, 20 faster, 0 slower, 0 within +/-5%. Geometric-mean time decreased by 75.1%. By path, geometric-mean time decreased by 90.8% for bitmap rows, 87.5% for branchless rows, and 43.7% for standard `HashSet` rows. Miss-only rows decreased by 66.6%; 50%-hit rows decreased by 81.4%. Largest relevant deltas: | Benchmark | Before | After | Change | |---|---:|---:|---:| | `fixed_size_binary/fsb4/list=4/match=50%` | 64.90 us | 3.01 us | -95.4% (21.56x faster) | | `fixed_size_binary/fsb8/list=4/match=50%` | 63.68 us | 3.17 us | -95.0% (20.06x faster) | | `fixed_size_binary/fsb2/list=64/match=50%` | 75.27 us | 3.99 us | -94.7% (18.88x faster) | | `fixed_size_binary/fsb1/list=16/match=50%` | 67.73 us | 3.87 us | -94.3% (17.48x faster) | | `fixed_size_binary/fsb4/list=4/match=0%` | 24.16 us | 3.04 us | -87.4% (7.95x faster) | | `fixed_size_binary/fsb8/list=4/match=0%` | 23.79 us | 3.18 us | -86.6% (7.49x faster) | | `fixed_size_binary/fsb2/list=64/match=0%` | 25.79 us | 3.91 us | -84.8% (6.60x faster) | | `fixed_size_binary/fsb1/list=16/match=0%` | 24.78 us | 3.86 us | -84.4% (6.41x faster) | | `fixed_size_binary/fsb16/list=4/match=50%` | 63.97 us | 12.23 us | -80.9% (5.23x faster) | | `fixed_size_binary/fsb4/list=64/match=50%` | 63.93 us | 29.89 us | -53.2% (2.14x faster) | <details> <summary>Full relevant table (20 rows)</summary> | Benchmark | Before | After | Change | |---|---:|---:|---:| | `fixed_size_binary/fsb1/list=16/match=0%` | 24.78 us | 3.86 us | -84.4% (6.41x faster) | | `fixed_size_binary/fsb1/list=16/match=50%` | 67.73 us | 3.87 us | -94.3% (17.48x faster) | | `fixed_size_binary/fsb2/list=64/match=0%` | 25.79 us | 3.91 us | -84.8% (6.60x faster) | | `fixed_size_binary/fsb2/list=64/match=50%` | 75.27 us | 3.99 us | -94.7% (18.88x faster) | | `fixed_size_binary/fsb4/list=4/match=0%` | 24.16 us | 3.04 us | -87.4% (7.95x faster) | | `fixed_size_binary/fsb4/list=4/match=50%` | 64.90 us | 3.01 us | -95.4% (21.56x faster) | | `fixed_size_binary/fsb4/list=64/match=0%` | 23.48 us | 13.03 us | -44.5% (1.80x faster) | | `fixed_size_binary/fsb4/list=64/match=50%` | 63.93 us | 29.89 us | -53.2% (2.14x faster) | | `fixed_size_binary/fsb8/list=4/match=0%` | 23.79 us | 3.18 us | -86.6% (7.49x faster) | | `fixed_size_binary/fsb8/list=4/match=50%` | 63.68 us | 3.17 us | -95.0% (20.06x faster) | | `fixed_size_binary/fsb8/list=64/match=0%` | 24.67 us | 14.34 us | -41.9% (1.72x faster) | | `fixed_size_binary/fsb8/list=64/match=50%` | 60.78 us | 31.78 us | -47.7% (1.91x faster) | | `fixed_size_binary/fsb16/list=4/match=0%` | 23.74 us | 12.22 us | -48.5% (1.94x faster) | | `fixed_size_binary/fsb16/list=4/match=50%` | 63.97 us | 12.23 us | -80.9% (5.23x faster) | | `fixed_size_binary/fsb16/list=64/match=0%` | 24.60 us | 15.37 us | -37.5% (1.60x faster) | | `fixed_size_binary/fsb16/list=64/match=50%` | 62.24 us | 32.29 us | -48.1% (1.93x faster) | | `fixed_size_binary/fsb16/list=256/match=0%` | 24.94 us | 15.43 us | -38.1% (1.62x faster) | | `fixed_size_binary/fsb16/list=256/match=50%` | 60.58 us | 34.50 us | -43.1% (1.76x faster) | | `fixed_size_binary/fsb16/list=10000/match=0%` | 26.58 us | 18.14 us | -31.7% (1.46x faster) | | `fixed_size_binary/fsb16/list=10000/match=50%` | 61.26 us | 31.75 us | -48.2% (1.93x 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]
