You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@datafusion.apache.org by "geoffreyclaude (via GitHub)" <gi...@apache.org> on 2026/08/08 08:46:09 UTC
[PR] IN LIST: optimize large integer filters [datafusion]
geoffreyclaude opened a new pull request, #24181:
URL: https://github.com/apache/datafusion/pull/24181
## Which issue does this PR close?
- Part of #19241.
- Stacked on [#24088](https://github.com/apache/datafusion/pull/24088) and [#24102](https://github.com/apache/datafusion/pull/24102), which follow [#23014](https://github.com/apache/datafusion/pull/23014).
- Extracted from #19390.
## Rationale for this change
Large constant integer `IN` lists perform a hash lookup for every input row. Reducing that lookup cost speeds up these filters.
## What changes are included in this PR?
- Adds a private immutable set for `Int32`, `UInt32`, `Int64`, and `UInt64`.
- Stores two values directly in each bucket and sends additional collisions to an overflow table, reusing the computed hash.
- Replaces float wrapper types with `to_bits()` keys in the standard `HashSet`.
- Reuses `build_in_list_result` for null and negation handling.
## Are these changes tested?
Yes. Tests cover collisions, slices, nulls, dictionary arrays, and float bit equality.
## 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 compilation completed, using the existing `in_list_strategy` benchmark:
```bash
cargo bench --target-dir <target-dir> \
-p datafusion-physical-expr \
--bench in_list_strategy -- 'primitive/i(32|64)/large_list|f32/large_list' --noplot
```
Criterion defaults were used, comparing median point estimates. Filter construction is outside the timed loop. Lower is better.
Compared baselines: exact combined heads of [#24088](https://github.com/apache/datafusion/pull/24088) and [#24102](https://github.com/apache/datafusion/pull/24102) -> this PR
10 of 11 cases improved, with a 35.3% geometric-mean time reduction.
| Benchmark | Before | After | Change |
|---|---:|---:|---:|
| `f32 / 64 / miss` | 15.94 us | 14.89 us | -6.6% |
| `f32 / 64 / 50% hit` | 41.03 us | 30.13 us | -26.6% |
| `i32 / 64 / miss` | 15.81 us | 14.17 us | -10.3% |
| `i32 / 64 / 50% hit` | 35.36 us | 15.62 us | -55.8% |
| `i32 / 256 / miss` | 16.48 us | 13.62 us | -17.4% |
| `i32 / 256 / 50% hit` | 33.51 us | 15.18 us | -54.7% |
| `i64 / 32 / miss` | 14.57 us | 15.65 us | +7.5% |
| `i64 / 32 / 50% hit` | 37.08 us | 13.11 us | -64.6% |
| `i64 / 128 / miss` | 16.07 us | 15.22 us | -5.3% |
| `i64 / 128 / 50% hit` | 35.14 us | 17.17 us | -51.1% |
| `nullable i32 / 64 / 50% hit / 20% null` | 29.60 us | 13.68 us | -53.8% |
The baseline and this PR were measured without competing Cargo or rustc processes.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] IN LIST: optimize large integer filters [datafusion]
Posted by "codecov-commenter (via GitHub)" <gi...@apache.org>.
codecov-commenter commented on PR #24181:
URL: https://github.com/apache/datafusion/pull/24181#issuecomment-5225468277
## [Codecov](https://app.codecov.io/gh/apache/datafusion/pull/24181?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) Report
:x: Patch coverage is `87.38739%` with `84 lines` in your changes missing coverage. Please review.
:white_check_mark: Project coverage is 81.07%. Comparing base ([`426b351`](https://app.codecov.io/gh/apache/datafusion/commit/426b351513be6317734aa2e425ac72ddde790fb4?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache)) to head ([`01d4451`](https://app.codecov.io/gh/apache/datafusion/commit/01d4451821f14e1f3bf153cefb41247cf31a7466?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache)).
:warning: Report is 30 commits behind head on main.
| [Files with missing lines](https://app.codecov.io/gh/apache/datafusion/pull/24181?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | Patch % | Lines |
|---|---|---|
| [...rc/expressions/in\_list/fixed\_size\_binary\_filter.rs](https://app.codecov.io/gh/apache/datafusion/pull/24181?src=pr&el=tree&filepath=datafusion%2Fphysical-expr%2Fsrc%2Fexpressions%2Fin_list%2Ffixed_size_binary_filter.rs&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-ZGF0YWZ1c2lvbi9waHlzaWNhbC1leHByL3NyYy9leHByZXNzaW9ucy9pbl9saXN0L2ZpeGVkX3NpemVfYmluYXJ5X2ZpbHRlci5ycw==) | 84.72% | [15 Missing and 27 partials :warning: ](https://app.codecov.io/gh/apache/datafusion/pull/24181?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
| [...l-expr/src/expressions/in\_list/byte\_view\_filter.rs](https://app.codecov.io/gh/apache/datafusion/pull/24181?src=pr&el=tree&filepath=datafusion%2Fphysical-expr%2Fsrc%2Fexpressions%2Fin_list%2Fbyte_view_filter.rs&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-ZGF0YWZ1c2lvbi9waHlzaWNhbC1leHByL3NyYy9leHByZXNzaW9ucy9pbl9saXN0L2J5dGVfdmlld19maWx0ZXIucnM=) | 85.31% | [9 Missing and 17 partials :warning: ](https://app.codecov.io/gh/apache/datafusion/pull/24181?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
| [...atafusion/physical-expr/src/expressions/in\_list.rs](https://app.codecov.io/gh/apache/datafusion/pull/24181?src=pr&el=tree&filepath=datafusion%2Fphysical-expr%2Fsrc%2Fexpressions%2Fin_list.rs&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-ZGF0YWZ1c2lvbi9waHlzaWNhbC1leHByL3NyYy9leHByZXNzaW9ucy9pbl9saXN0LnJz) | 76.31% | [2 Missing and 7 partials :warning: ](https://app.codecov.io/gh/apache/datafusion/pull/24181?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
| [...l-expr/src/expressions/in\_list/primitive\_filter.rs](https://app.codecov.io/gh/apache/datafusion/pull/24181?src=pr&el=tree&filepath=datafusion%2Fphysical-expr%2Fsrc%2Fexpressions%2Fin_list%2Fprimitive_filter.rs&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-ZGF0YWZ1c2lvbi9waHlzaWNhbC1leHByL3NyYy9leHByZXNzaW9ucy9pbl9saXN0L3ByaW1pdGl2ZV9maWx0ZXIucnM=) | 88.37% | [0 Missing and 5 partials :warning: ](https://app.codecov.io/gh/apache/datafusion/pull/24181?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
| [.../physical-expr/src/expressions/in\_list/strategy.rs](https://app.codecov.io/gh/apache/datafusion/pull/24181?src=pr&el=tree&filepath=datafusion%2Fphysical-expr%2Fsrc%2Fexpressions%2Fin_list%2Fstrategy.rs&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-ZGF0YWZ1c2lvbi9waHlzaWNhbC1leHByL3NyYy9leHByZXNzaW9ucy9pbl9saXN0L3N0cmF0ZWd5LnJz) | 92.85% | [0 Missing and 2 partials :warning: ](https://app.codecov.io/gh/apache/datafusion/pull/24181?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
<details><summary>Additional details and impacted files</summary>
```diff
@@ Coverage Diff @@
## main #24181 +/- ##
==========================================
+ Coverage 80.91% 81.07% +0.15%
==========================================
Files 1102 1109 +7
Lines 377102 382818 +5716
Branches 377102 382818 +5716
==========================================
+ Hits 305143 310374 +5231
- Misses 53769 54075 +306
- Partials 18190 18369 +179
```
</details>
[:umbrella: View full report in Codecov by Harness](https://app.codecov.io/gh/apache/datafusion/pull/24181?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache).
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache).
<details><summary> :rocket: New features to boost your workflow: </summary>
- :snowflake: [Test Analytics](https://docs.codecov.com/docs/test-analytics): Detect flaky tests, report on failures, and find test suite problems.
- :package: [JS Bundle Analysis](https://docs.codecov.com/docs/javascript-bundle-analysis): Save yourself from yourself by tracking and limiting bundle sizes in JS merges.
</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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] IN LIST: index 32- and 64-bit integers by byte [datafusion]
Posted by "geoffreyclaude (via GitHub)" <gi...@apache.org>.
geoffreyclaude closed pull request #24181: IN LIST: index 32- and 64-bit integers by byte
URL: https://github.com/apache/datafusion/pull/24181
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org