perf: extend compact IN-list pruning to ordered types by kumarUjjawal · Pull Request #25012 · apache/datafusion

kumarUjjawal · 2026-09-07T07:55:40Z

Which issue does this PR close?

Closes Extend compact IN-list pruning beyond string types #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:

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:

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.

codecov-commenter · 2026-09-07T08:20:39Z

Codecov Report

❌ Patch coverage is 83.70098% with 133 lines in your changes missing coverage. Please review.
✅ Project coverage is 81.73%. Comparing base (ca5d10b) to head (fce561f).
⚠️ Report is 20 commits behind head on main.

Files with missing lines	Patch %	Lines
datafusion/pruning/src/primitive_in_list.rs	73.11%	45 Missing and 5 partials ⚠️
datafusion/pruning/src/pruning_predicate.rs	90.36%	15 Missing and 27 partials ⚠️
datafusion/pruning/src/string_in_list.rs	75.44%	35 Missing and 6 partials ⚠️

Additional details and impacted files

@@            Coverage Diff             @@
##             main   #25012      +/-   ##
==========================================
+ Coverage   81.69%   81.73%   +0.03%     
==========================================
  Files        1127     1129       +2     
  Lines      415386   417153    +1767     
  Branches   415386   417153    +1767     
==========================================
+ Hits       339358   340948    +1590     
- Misses      56093    56175      +82     
- Partials    19935    20030      +95

☔ View full report in Codecov by Harness.
📢 Have feedback on the report? Share it here.

🚀 New features to boost your workflow:

❄️ Test Analytics: Detect flaky tests, report on failures, and find test suite problems.
📦 JS Bundle Analysis: Save yourself from yourself by tracking and limiting bundle sizes in JS merges.

kosiew

@kumarUjjawal, thanks for working on this. The compact sorted-domain approach looks like a nice extension of the existing string pruning optimization to ordered primitive, temporal, decimal, and binary types. I also appreciate the unit, Parquet integration, benchmark, and configuration coverage. I just have one non-blocking suggestion around end-to-end NULL coverage.

kosiew · 2026-09-08T04:53:38Z

 }

+#[tokio::test]
+async fn ordered_in_list_parquet_pruning() {


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.

Thank you @kosiew this makes sense

@kosiew if you get time can you take a look at the latest changes fce561f

kosiew

@kumarUjjawal,

Thanks for the follow-up. The new nullable Int64 case includes a NULL member in the list and verifies the full Parquet path, including row filtering, compact-predicate selection, limit behavior, and pruning metrics.

I also checked the follow-up diff and did not find any new issues beyond the previously reviewed changes.

Looks good to me. Thanks for taking care of this!

kumarUjjawal · 2026-09-09T03:32:25Z

Thank you @kosiew as always for taking the time and wonderful reviews.

## Which issue does this PR close? - Closes apache#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. Backport provenance: - Upstream PR: apache#25012 - Upstream commit: f3f420b - Upstream self-tests and all additions/removals retained; only unavoidable fork patch context resolved. - Any fork-specific adaptation is kept in a separate following commit. Signed-off-by: discord9 <[email protected]>

perf: extend compact IN-list pruning to ordered types

1576b03

github-actions Bot added documentation Improvements or additions to documentation core Core DataFusion crate sqllogictest SQL Logic Tests (.slt) common Related to common crate labels Sep 7, 2026

kumarUjjawal requested a review from kosiew September 7, 2026 07:56

kosiew approved these changes Sep 8, 2026

View reviewed changes

test: cover primitive IN-list NULL semantics

fce561f

kosiew approved these changes Sep 9, 2026

View reviewed changes

kumarUjjawal added this pull request to the merge queue Sep 9, 2026

Merged via the queue into apache:main with commit f3f420b Sep 9, 2026
40 checks passed

kumarUjjawal deleted the feat/compact-in-list-more-types branch September 9, 2026 03:41

goutamadwant mentioned this pull request Sep 14, 2026

refactor: separate compact IN-list pruning threshold from the default cap #25044

Open

nuno-faria added the v56.0.0 label Oct 3, 2026

This was referenced Nov 6, 2026

perf: backport JOIN dynamic-filter and compact pruning optimizations GreptimeTeam/datafusion#39

Merged

fix: backport complete join pruning and aggregate NULL-bound recovery (reviewable history) GreptimeTeam/datafusion#40

Closed

Navigation Menu

Repository navigation

perf: extend compact IN-list pruning to ordered types - #25012

perf: extend compact IN-list pruning to ordered types#25012
kumarUjjawal merged 2 commits into
apache:mainfrom
kumarUjjawal:feat/compact-in-list-more-types

kumarUjjawal commented Sep 7, 2026

Uh oh!

codecov-commenter commented Sep 7, 2026 •

edited

Loading

Uh oh!

kosiew left a comment

Uh oh!

kosiew Sep 8, 2026

Uh oh!

kumarUjjawal Sep 8, 2026

Uh oh!

kumarUjjawal Sep 8, 2026

Uh oh!

kosiew left a comment

Uh oh!

kumarUjjawal commented Sep 9, 2026

Uh oh!

Uh oh!

Reviewers

Uh oh!

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants

Conversation

kumarUjjawal commented Sep 7, 2026

Which issue does this PR close?

Rationale for this change

What changes are included in this PR?

Benchmarks

What is the testing strategy for this PR?

Are there any user-facing changes?

Uh oh!

codecov-commenter commented Sep 7, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Codecov Report

Uh oh!

kosiew left a comment

Choose a reason for hiding this comment

Uh oh!

kosiew Sep 8, 2026

Choose a reason for hiding this comment

Uh oh!

kumarUjjawal Sep 8, 2026

Choose a reason for hiding this comment

Uh oh!

kumarUjjawal Sep 8, 2026

Choose a reason for hiding this comment

Uh oh!

kosiew left a comment

Choose a reason for hiding this comment

Uh oh!

kumarUjjawal commented Sep 9, 2026

Uh oh!

Uh oh!

Reviewers

Uh oh!

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants

codecov-commenter commented Sep 7, 2026 •

edited

Loading