You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@datafusion.apache.org by "kumarUjjawal (via GitHub)" <gi...@apache.org> on 2026/09/07 07:55:42 UTC
[PR] perf: extend compact IN-list pruning to ordered types [datafusion]
kumarUjjawal opened a new pull request, #25012:
URL: https://github.com/apache/datafusion/pull/25012
## Which issue does this PR close?
- Closes #24709
## Rationale for this change
Compact pruning for large `IN` lists only supports string columns.
Other ordered types use one min/max comparison for each literal. Large lists create large expression trees and make pruning more expensive.
These types can use the same compact sorted-domain approach.
## What changes are included in this PR?
This PR adds compact `IN` and `NOT IN` pruning for:
- Variable-length binary types
- Signed and unsigned integers
- Decimal types
- Date and time types
- Timestamp and duration types
- Dictionary-encoded forms of these types
String and binary values share the byte-domain implementation. Primitive types use typed contiguous arrays.
The compact path preserves NULL behavior and dictionary value NULLs. Unsupported types keep the existing per-value fallback.
Floating-point types remain unsupported because of NaN and signed zero. `FixedSizeBinary` and nested types also remain unsupported.
The default `max_in_list_size` value remains 20.
### Benchmarks
With 1,024 literals and 4,096 statistics containers:
- String `IN` evaluation is 37.8x faster.
- String `NOT IN` evaluation is 21.4x faster.
- Int64 `IN` evaluation is 118x faster.
- Int64 `NOT IN` evaluation is 111x faster.
- Predicate construction is 15.9x to 32.1x faster.
Commands:
```shell
cargo bench -p datafusion-pruning --bench string_in_list_pruning
cargo bench -p datafusion-pruning --bench primitive_in_list_pruning
```
## What is the testing strategy for this PR?
The tests cover:
- All supported type families
- Both `IN` and `NOT IN`
- NULL-containing and all-NULL lists
- Dictionary and run-end-encoded values
- Missing, inverted, and truncated statistics
- Parquet row-group and page pruning
- Per-value fallback for unsupported types
- Result equality between compact pruning and the original filter
The following commands passed:
```shell
cargo test -p datafusion-pruning
cargo test -p datafusion --test parquet_integration string_in_list_pruning
cargo test -p datafusion-sqllogictest --test sqllogictests -- information_schema
cargo clippy -p datafusion-pruning -p datafusion --all-targets --all-features -- -D warnings
cargo fmt --all -- --check
```
## Are there any user-facing changes?
Large `IN` and `NOT IN` lists can use compact pruning for more ordered types.
This behavior applies when `datafusion.execution.parquet.max_in_list_size` is set above 20. The default value and SQL results do not change.
This PR does not change public APIs.
--
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] perf: extend compact IN-list pruning to ordered types [datafusion]
Posted by "kumarUjjawal (via GitHub)" <gi...@apache.org>.
kumarUjjawal merged PR #25012:
URL: https://github.com/apache/datafusion/pull/25012
--
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] perf: extend compact IN-list pruning to ordered types [datafusion]
Posted by "kumarUjjawal (via GitHub)" <gi...@apache.org>.
kumarUjjawal commented on code in PR #25012:
URL: https://github.com/apache/datafusion/pull/25012#discussion_r3954734894
##########
datafusion/core/tests/parquet/string_in_list_pruning.rs:
##########
@@ -413,6 +514,118 @@ async fn check_string_not_in_list_with_truncated_bounds(page_pruning: bool) {
assert_eq!(output.counter("output_rows"), ROWS_PER_UNIT);
}
+#[tokio::test]
+async fn ordered_in_list_parquet_pruning() {
Review Comment:
Thank you @kosiew this makes sense
--
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] perf: extend compact IN-list pruning to ordered types [datafusion]
Posted by "kumarUjjawal (via GitHub)" <gi...@apache.org>.
kumarUjjawal commented on PR #25012:
URL: https://github.com/apache/datafusion/pull/25012#issuecomment-5595365601
Thank you @kosiew as always for taking the time and wonderful reviews.
--
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] perf: extend compact IN-list pruning to ordered types [datafusion]
Posted by "kosiew (via GitHub)" <gi...@apache.org>.
kosiew commented on code in PR #25012:
URL: https://github.com/apache/datafusion/pull/25012#discussion_r3954433795
##########
datafusion/core/tests/parquet/string_in_list_pruning.rs:
##########
@@ -413,6 +514,118 @@ async fn check_string_not_in_list_with_truncated_bounds(page_pruning: bool) {
assert_eq!(output.counter("output_rows"), ROWS_PER_UNIT);
}
+#[tokio::test]
+async fn ordered_in_list_parquet_pruning() {
Review Comment:
Could we add one nullable primitive or binary end-to-end case with a NULL member in the list? The unit tests cover the compact filter-only semantics well, but I think an integration case would also be useful to exercise the new Parquet source and full-match path and make sure a compact predicate with NULL does not accidentally bypass the row filter.
--
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] perf: extend compact IN-list pruning to ordered types [datafusion]
Posted by "codecov-commenter (via GitHub)" <gi...@apache.org>.
codecov-commenter commented on PR #25012:
URL: https://github.com/apache/datafusion/pull/25012#issuecomment-5567602178
## [Codecov](https://app.codecov.io/gh/apache/datafusion/pull/25012?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 `83.70098%` with `133 lines` in your changes missing coverage. Please review.
:white_check_mark: Project coverage is 81.71%. Comparing base ([`ca5d10b`](https://app.codecov.io/gh/apache/datafusion/commit/ca5d10b75ff1d1c7a222ebff0205e5132049fe14?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache)) to head ([`1576b03`](https://app.codecov.io/gh/apache/datafusion/commit/1576b03746a7eb9b3a5f788415a67d0902cd3c37?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache)).
:warning: Report is 3 commits behind head on main.
| [Files with missing lines](https://app.codecov.io/gh/apache/datafusion/pull/25012?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | Patch % | Lines |
|---|---|---|
| [datafusion/pruning/src/primitive\_in\_list.rs](https://app.codecov.io/gh/apache/datafusion/pull/25012?src=pr&el=tree&filepath=datafusion%2Fpruning%2Fsrc%2Fprimitive_in_list.rs&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-ZGF0YWZ1c2lvbi9wcnVuaW5nL3NyYy9wcmltaXRpdmVfaW5fbGlzdC5ycw==) | 73.11% | [45 Missing and 5 partials :warning: ](https://app.codecov.io/gh/apache/datafusion/pull/25012?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
| [datafusion/pruning/src/pruning\_predicate.rs](https://app.codecov.io/gh/apache/datafusion/pull/25012?src=pr&el=tree&filepath=datafusion%2Fpruning%2Fsrc%2Fpruning_predicate.rs&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-ZGF0YWZ1c2lvbi9wcnVuaW5nL3NyYy9wcnVuaW5nX3ByZWRpY2F0ZS5ycw==) | 90.36% | [15 Missing and 27 partials :warning: ](https://app.codecov.io/gh/apache/datafusion/pull/25012?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
| [datafusion/pruning/src/string\_in\_list.rs](https://app.codecov.io/gh/apache/datafusion/pull/25012?src=pr&el=tree&filepath=datafusion%2Fpruning%2Fsrc%2Fstring_in_list.rs&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-ZGF0YWZ1c2lvbi9wcnVuaW5nL3NyYy9zdHJpbmdfaW5fbGlzdC5ycw==) | 75.44% | [35 Missing and 6 partials :warning: ](https://app.codecov.io/gh/apache/datafusion/pull/25012?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 #25012 +/- ##
==========================================
+ Coverage 81.69% 81.71% +0.01%
==========================================
Files 1127 1129 +2
Lines 415386 416288 +902
Branches 415386 416288 +902
==========================================
+ Hits 339358 340155 +797
- Misses 56093 56163 +70
- Partials 19935 19970 +35
```
</details>
[:umbrella: View full report in Codecov by Harness](https://app.codecov.io/gh/apache/datafusion/pull/25012?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] perf: extend compact IN-list pruning to ordered types [datafusion]
Posted by "kumarUjjawal (via GitHub)" <gi...@apache.org>.
kumarUjjawal commented on code in PR #25012:
URL: https://github.com/apache/datafusion/pull/25012#discussion_r3954866439
##########
datafusion/core/tests/parquet/string_in_list_pruning.rs:
##########
@@ -413,6 +514,118 @@ async fn check_string_not_in_list_with_truncated_bounds(page_pruning: bool) {
assert_eq!(output.counter("output_rows"), ROWS_PER_UNIT);
}
+#[tokio::test]
+async fn ordered_in_list_parquet_pruning() {
Review Comment:
@kosiew if you get time can you take a look at the latest changes [fce561f](https://github.com/apache/datafusion/pull/25012/commits/fce561f87aa883766c86d27656c7a995ab721cbe)
--
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