Repository navigation
Commit a23cfb1
perf: extend compact IN-list pruning to ordered types (apache#25012)
## 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]>1 parent fc503ee commit a23cfb1
11 files changed
Lines changed: 1994 additions & 376 deletions
File tree
- datafusion
- common/src
- core/tests/parquet
- pruning
- benches
- src
- sqllogictest/test_files
- docs/source/user-guide
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
1287 | 1287 | | |
1288 | 1288 | | |
1289 | 1289 | | |
1290 | | - | |
1291 | | - | |
1292 | | - | |
1293 | | - | |
1294 | | - | |
1295 | | - | |
| 1290 | + | |
| 1291 | + | |
| 1292 | + | |
| 1293 | + | |
| 1294 | + | |
| 1295 | + | |
| 1296 | + | |
| 1297 | + | |
1296 | 1298 | | |
1297 | 1299 | | |
1298 | 1300 | | |
| |||
0 commit comments