Skip to content

Commit 9ad1217

Browse files
authored
perf: use compact pruning for large string IN lists (apache#24526)
## Why are the changes needed? ### Which issue does this PR close? Related to apache#8668 and apache#8609; follows apache#24074 and the merged statistics-ordering fix apache#24525. ### Rationale for this change Queries often select a sparse set of string identifiers. Parquet min/max statistics can make these queries much cheaper by ruling out row groups or pages that cannot contain any requested identifier. For example, this query asks for 21 IDs, spaced ten apart: ```sql SET datafusion.execution.parquet.max_in_list_size = 1024; SELECT * FROM events WHERE customer_id IN ( 'id000', 'id010', 'id020', 'id030', 'id040', 'id050', 'id060', 'id070', 'id080', 'id090', 'id100', 'id110', 'id120', 'id130', 'id140', 'id150', 'id160', 'id170', 'id180', 'id190', 'id200' ); ``` A row group whose values fall between `id003` and `id007` cannot contain a match. The default pruning limit is 20, so this list is not eligible for the `IN` min/max rewrite unless the caller raises the limit. apache#24074 made that limit configurable. With a raised limit, DataFusion can already reject this row group, but it does so by constructing a growing expression tree resembling: ```text (min <= id000 AND id000 <= max) OR (min <= id010 AND id010 <= max) OR ... ``` For hundreds or thousands of identifiers, building and evaluating that tree can become expensive in its own right. Replacing the list with one enclosing range, `[id000, id200]`, would be cheaper, but would lose the gaps: that broad range overlaps `[id003, id007]` even though none of the requested IDs is present there. The aim is to keep the useful pruning precision of the existing per-value checks while making large lists cheaper to represent and evaluate. In the included local microbenchmark, evaluating 1,024 values against 4,096 intervals falls from 68.8 ms to 0.198 ms. This measures pruning work only, not end-to-end query speedup. ## What changes were proposed in this PR? ### What changes are included in this PR? Eligible large string lists are stored as a sorted, deduplicated set of values inside the pruning predicate, rather than expanded into one comparison branch per value. For each inclusive statistics interval, DataFusion finds the first requested value at or after the interval's minimum, then checks whether that value is also at or before its maximum. In the example, the first requested ID at or after `id003` is `id010`. Since `id010 > id007`, the row group can be skipped. An interval such as `[id019, id021]` must be kept because it could contain `id020`. This takes a binary search per interval after sorting the values once per constructed predicate, and the expression tree no longer grows with the number of IDs. The result remains a conservative pruning decision. An overlapping interval means only that a match is possible; the original `IN` expression still performs exact row filtering. The original literal information also remains available to other pruning mechanisms, including Bloom filters. Inverted or unusable bounds yield UNKNOWN. A single known bound can still exclude the entire domain; otherwise, incomplete bounds yield UNKNOWN and keep the container eligible for reading. **Limits and scope** For a nonempty input list of `N` values, before this optimization deduplicates it, and configured cap `C = datafusion.execution.parquet.max_in_list_size`: | Condition | Min/max pruning behavior | | --- | --- | | `N <= min(20, C)` | Existing per-value rewrite | | `20 < N <= C`, positive, non-null literal strings on a direct string column | Compact sorted-domain lookup | | `20 < N <= C`, other lists | Existing per-value rewrite, including non-string lists, `NOT IN`, and NULL-containing lists | | `N > C` | This `IN` min/max rewrite is skipped; it does not disable all pruning | The compact path supports `Utf8`, `LargeUtf8`, `Utf8View`, and dictionary-encoded string columns. Unsupported expressions keep their existing handling. The default cap remains 20, and `C = 0` disables this `IN` min/max rewrite. Other predicates and literal/containment pruning, including Bloom filters, remain available. Raising the cap can still produce expensive comparison trees for lists that do not use the compact path. The lower threshold of 20 preserves the existing expression shape and limits this PR's scope; it is not a measured performance crossover. Page-index pruning now receives the same configured cap as row-group pruning, so raising the limit can benefit both. An interval search requires bounds in the same comparison order as the query. The compact path reads the same statistics adapters as the existing per-value path. The already-merged apache#24525 masks untrusted Parquet byte-array bounds. For other statistics sources, `PruningStatistics` requires conservative bounds in Arrow's comparison order; arbitrary provider bounds are trusted rather than validated by this expression. ### Are there any user-facing changes? Users who raise `datafusion.execution.parquet.max_in_list_size` get cheaper min/max pruning for eligible large string lists, and page pruning now honors that setting. The configuration default, exact query results, and existing public APIs are unchanged. This is a focused optimization for literal string lists, not a general rewrite of every large `IN` expression. ## How was this PR tested? ### Are these changes tested? The pruning-crate suite passed 95 tests. The standalone Parquet regressions use lists of 20, 21, 256, and 1,024 values and check both exact query results and scan/pruning metrics. They cover gaps inside the list's enclosing range, row-group pruning, page-only pruning, and the default and zero-cap controls. Two correctness regressions exercise the less obvious interactions. A direct physical-source test uses `NOT IN (..., NULL)`, row-filter pushdown, and `LIMIT 1`, so logical optimizer folding cannot hide an incorrect decision to bypass filtering. A real-file test combines this PR with apache#24525 and verifies that compact page pruning cannot lose a matching row when the footer's ordering is missing or unknown. Against unchanged Apache `f1f0449a`, the positive row-group/page tests fail as expected; the `NOT IN (..., NULL)` control passes. The benchmark compares the actual raised-cap `IN` path on Apache `f1f0449a` and this patch, using separate build directories and checking that both return the same nontrivial 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 | A balanced explicit OR tree is included as another comparison: at 1,024 values it takes 8.03 ms to evaluate the same intervals. These measurements isolate pruning overhead; no end-to-end workload improvement is claimed. The latest documentation/comment update passed configuration-doc generation, formatting, all-targets/all-features Clippy with warnings denied, and `./dev/rust_lint.sh` (including the workspace Rust documentation check). Focused validation also passed all 3 Parquet IN-list integration tests and all 9 Parquet statistics-ordering tests. The CI follow-up in [1a2b38c](apache@1a2b38c) updates the `SHOW ALL VERBOSE` snapshot to match the revised `max_in_list_size` help text. The stale row caused both the cargo test and benchmark verification jobs to fail. After the correction, the targeted `information_schema.slt` test and full extended suite passed: 10,796 Rust tests (8 ignored) and all 505 SQL logic files. Formatting, Clippy with all targets and features and warnings denied, and `./dev/rust_lint.sh` also passed. <details> <summary>Validation commands</summary> ```sh cargo test --locked --profile ci -p datafusion-pruning cargo test --locked --profile ci -p datafusion \ --test parquet_integration string_in_list_pruning 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 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 ``` </details>
1 parent d1fe988 commit 9ad1217

16 files changed

Lines changed: 1374 additions & 37 deletions

File tree

‎Cargo.lock‎

Lines changed: 1 addition & 0 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎datafusion/common/src/config.rs‎

Lines changed: 8 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -1368,13 +1368,15 @@ config_namespace! {
13681368
/// parquet reader setting. 0 means no caching.
13691369
pub max_predicate_cache_size: Option<usize>, default = None
13701370

1371-
/// Maximum number of values in an `IN (...)` list for which pruning will
1372-
/// occur. Longer lists will not be used to prune files, row groups, or
1373-
/// data pages.
1371+
/// Maximum number of input values in an `IN (...)` list eligible for
1372+
/// min/max pruning. Lists above this cap, or a cap of 0, skip this
1373+
/// rewrite; other predicates and Bloom-filter pruning remain available.
13741374
///
1375-
/// Higher values help in cases such as filtering on a list of
1376-
/// ~25-100 identifiers, but also make the predicate more expensive to
1377-
/// evaluate. Set to 0 to disable `IN (...)` list pruning entirely.
1375+
/// Within the cap, nonempty lists of at most 20 values use the existing
1376+
/// per-value rewrite. Larger positive, non-null literal string lists
1377+
/// on a string column use a compact sorted domain. Other lists retain
1378+
/// the existing per-value rewrite, so raising the cap can make those
1379+
/// predicates expensive to build and evaluate.
13781380
///
13791381
/// Defaults to 20.
13801382
pub max_in_list_size: usize, default = 20

‎datafusion/common/src/pruning.rs‎

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -67,13 +67,24 @@ pub trait PruningStatistics {
6767
/// returned array should have `null` in that row. If the minimum value is
6868
/// not known for any row, return `None`.
6969
///
70+
/// Each non-null entry must be a conservative lower bound for all non-null
71+
/// values in its container, using Arrow's comparison order for the column
72+
/// type. For strings, this is unsigned lexicographic UTF-8 byte order.
73+
/// Bounds that cannot satisfy this contract must be reported as unknown.
74+
/// Pruning relies on providers to uphold this contract; it does not validate
75+
/// the ordering or bound guarantees of arbitrary statistics sources.
76+
///
7077
/// Note: the returned array must contain [`Self::num_containers`] rows
7178
fn min_values(&self, column: &Column) -> Option<ArrayRef>;
7279

7380
/// Return the maximum values for the named column, if known.
7481
///
7582
/// See [`Self::min_values`] for when to return `None` and null values.
7683
///
84+
/// Each non-null entry must be a conservative upper bound for all non-null
85+
/// values in its container, using the comparison order described in
86+
/// [`Self::min_values`].
87+
///
7788
/// Note: the returned array must contain [`Self::num_containers`] rows
7889
fn max_values(&self, column: &Column) -> Option<ArrayRef>;
7990

‎datafusion/core/tests/parquet/mod.rs‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -58,6 +58,7 @@ mod page_pruning;
5858
mod row_group_pruning;
5959
mod schema;
6060
mod schema_coercion;
61+
mod string_in_list_pruning;
6162
mod utils;
6263

6364
#[cfg(test)]

0 commit comments

Comments
 (0)