Skip to content

Commit f3f420b

Browse files
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/config.rs‎

Lines changed: 8 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -1392,12 +1392,14 @@ config_namespace! {
13921392
/// rewrite; other predicates and Bloom-filter pruning remain available.
13931393
///
13941394
/// Within the cap, nonempty lists of at most 20 values use the existing
1395-
/// per-value rewrite. Larger literal string lists on a string column use
1396-
/// a compact representation, for both `IN` and `NOT IN`, including lists
1397-
/// with NULL members. `NOT IN` with NULL and all-NULL `IN` lists cannot
1398-
/// match any rows. Other lists retain the existing per-value rewrite, so
1399-
/// raising the cap can make those predicates expensive to build and
1400-
/// evaluate.
1395+
/// per-value rewrite. Larger literal lists use a compact representation
1396+
/// when the column type is string, variable-length binary, integer,
1397+
/// decimal, date, time, timestamp, or duration. This applies to both `IN`
1398+
/// and `NOT IN`, including lists with NULL members. `NOT IN` with NULL and
1399+
/// all-NULL `IN` lists cannot match any rows. Compact lists containing NULL
1400+
/// do not use the fully-matched-row-group optimization. Floating-point and
1401+
/// other lists retain the existing per-value rewrite, so raising the cap
1402+
/// can make those predicates expensive to build and evaluate.
14011403
///
14021404
/// Defaults to 20.
14031405
pub max_in_list_size: usize, default = 20

0 commit comments

Comments
 (0)