sunchao opened a new pull request, #24526:
URL: https://github.com/apache/datafusion/pull/24526
## Why are the changes needed?
### Which issue does this PR close?
Related to #8668 and #8609; follows #24074. This is a focused implementation
for positive literal string lists, not a claim to support every large `IN`
expression.
This draft is stacked on the companion Parquet statistics-order fix
(`10aafae8e925e11dc7f8c96d93947314a09342f6`), which must merge first. The newly
enabled large-list page-pruning path depends on that fix's validation of legacy
and unknown-order bounds.
### Rationale for this change
Raising `datafusion.execution.parquet.max_in_list_size` enables useful
statistics pruning for larger identifier lists, but the current implementation
constructs and evaluates a growing tree of per-value comparisons. Large sparse
lists need a compact representation that still preserves gaps between their
values; one enclosing range cannot provide that pruning.
## What changes were proposed in this PR?
### What changes are included in this PR?
- Sort and deduplicate eligible string literals when building the pruning
predicate, then binary-search the domain for each inclusive min/max interval.
- Keep the configured limit as an absolute cap. The default remains 20, zero
still disables this rewrite, and eligible lists above 20 use the compact path.
- Retain the original exact row filter and literal guarantees. `NOT IN`,
null-containing lists, and unsupported expressions keep their existing
behavior; unknown or inverted bounds remain conservative.
- Pass the same configured limit to page-index pruning, which previously
used the default even when the limit was raised.
- Add standalone Parquet regressions and a benchmark comparing the
raised-cap `IN` path with equivalent per-value checks.
### Are there any user-facing changes?
Eligible large string lists are cheaper to prune when the existing limit is
raised. Page pruning now honors that limit as row-group pruning does. Results,
configuration defaults, and existing public APIs are unchanged.
## How was this PR tested?
### Are these changes tested?
The pruning-crate suite passed 93 tests. Standalone Parquet tests cover 20,
21, 256, and 1,024 values, exact results and scan metrics, sparse gaps,
page-only pruning, and default/zero-cap controls. A direct physical-source
regression checks `NOT IN (..., NULL)` with row-filter pushdown and `LIMIT 1`
so optimizer folding cannot hide an incorrect fully-matched-row-group decision.
A combined real-file regression forces compact page pruning with a raised cap
and verifies that missing or unknown footer ordering cannot remove the matching
row.
Against unchanged Apache `f1f0449a`, the new positive row-group/page
integration tests fail as expected; the `NOT IN (..., NULL)` control passes.
The new benchmark was run on unchanged Apache `f1f0449a` plus the benchmark,
and on this patch, using separate build directories. Both runs raise the cap to
the domain size and check identical pruning results. Local results on an Apple
M5 Max (18 CPUs, 128 GiB), Rust 1.97.0, `release-nonlto`, 20 samples:
| Values | Predicate construction, main → PR | Evaluate 4,096 intervals,
main → PR |
| --- | --- | --- |
| 20 | 31.1 → 27.4 µs | 177.6 → 165.7 µs |
| 21 | 30.5 → 3.52 µs | 183.8 → 98.1 µs |
| 256 | 356.6 → 21.4 µs | 5.53 → 0.144 ms |
| 1,024 | 1.466 → 0.081 ms | 68.8 → 0.198 ms |
The benchmark also includes a balanced explicit OR tree: at 1,024 values it
took 8.03 ms to evaluate the same intervals. These are pruning microbenchmarks,
not end-to-end query speedups.
```sh
cargo bench --locked --profile release-nonlto -p datafusion-pruning \
--bench string_in_list_pruning -- \
--sample-size 20 --warm-up-time 0.5 --measurement-time 1 --noplot
```
Formatting, all-targets/all-features Clippy with warnings denied, and
`./dev/rust_lint.sh` passed on the combined stack. The required extended
workspace run passed 10,674 Rust tests, with eight ignored, and all 503
SQL-logic files.
```sh
RUST_BACKTRACE=1 cargo test --locked --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
```
--
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]
