Repository navigation
Commit f3f420b
authored
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.1 parent f40d978 commit f3f420b
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 | |
|---|---|---|---|
| |||
1392 | 1392 | | |
1393 | 1393 | | |
1394 | 1394 | | |
1395 | | - | |
1396 | | - | |
1397 | | - | |
1398 | | - | |
1399 | | - | |
1400 | | - | |
| 1395 | + | |
| 1396 | + | |
| 1397 | + | |
| 1398 | + | |
| 1399 | + | |
| 1400 | + | |
| 1401 | + | |
| 1402 | + | |
1401 | 1403 | | |
1402 | 1404 | | |
1403 | 1405 | | |
| |||
0 commit comments