Skip to content

Commit a23cfb1

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

Lines changed: 8 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -1287,12 +1287,14 @@ config_namespace! {
12871287
/// rewrite; other predicates and Bloom-filter pruning remain available.
12881288
///
12891289
/// Within the cap, nonempty lists of at most 20 values use the existing
1290-
/// per-value rewrite. Larger literal string lists on a string column use
1291-
/// a compact representation, for both `IN` and `NOT IN`, including lists
1292-
/// with NULL members. `NOT IN` with NULL and all-NULL `IN` lists cannot
1293-
/// match any rows. Other lists retain the existing per-value rewrite, so
1294-
/// raising the cap can make those predicates expensive to build and
1295-
/// evaluate.
1290+
/// per-value rewrite. Larger literal lists use a compact representation
1291+
/// when the column type is string, variable-length binary, integer,
1292+
/// decimal, date, time, timestamp, or duration. This applies to both `IN`
1293+
/// and `NOT IN`, including lists with NULL members. `NOT IN` with NULL and
1294+
/// all-NULL `IN` lists cannot match any rows. Compact lists containing NULL
1295+
/// do not use the fully-matched-row-group optimization. Floating-point and
1296+
/// other lists retain the existing per-value rewrite, so raising the cap
1297+
/// can make those predicates expensive to build and evaluate.
12961298
///
12971299
/// Defaults to 20.
12981300
pub max_in_list_size: usize, default = 20

0 commit comments

Comments
 (0)