Repository navigation
Commit 9ad1217
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
- datafusion
- common/src
- core/tests/parquet
- datasource-parquet/src
- opener
- pruning
- benches
- src
- sqllogictest/test_files
- docs/source/user-guide
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
1368 | 1368 | | |
1369 | 1369 | | |
1370 | 1370 | | |
1371 | | - | |
1372 | | - | |
1373 | | - | |
| 1371 | + | |
| 1372 | + | |
| 1373 | + | |
1374 | 1374 | | |
1375 | | - | |
1376 | | - | |
1377 | | - | |
| 1375 | + | |
| 1376 | + | |
| 1377 | + | |
| 1378 | + | |
| 1379 | + | |
1378 | 1380 | | |
1379 | 1381 | | |
1380 | 1382 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
67 | 67 | | |
68 | 68 | | |
69 | 69 | | |
| 70 | + | |
| 71 | + | |
| 72 | + | |
| 73 | + | |
| 74 | + | |
| 75 | + | |
| 76 | + | |
70 | 77 | | |
71 | 78 | | |
72 | 79 | | |
73 | 80 | | |
74 | 81 | | |
75 | 82 | | |
76 | 83 | | |
| 84 | + | |
| 85 | + | |
| 86 | + | |
| 87 | + | |
77 | 88 | | |
78 | 89 | | |
79 | 90 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
58 | 58 | | |
59 | 59 | | |
60 | 60 | | |
| 61 | + | |
61 | 62 | | |
62 | 63 | | |
63 | 64 | | |
| |||
0 commit comments