Repository navigation
Commit 9e68a86
authored
feat(parquet): intra-file early stopping via statistics + dynamic filters (#22450)
## Which issue does this PR close?
Closes #22407.
## Rationale for this change
DataFusion already prunes parquet at three granularities — **file**
(`EarlyStoppingStream` + `FilePruner`), **row group at scan-startup**
(`PruningPredicate` → `RowGroupAccessPlanFilter`), and **row inside an
open RG** (`RowFilter`).
There's a gap in the middle: once row-group pruning runs at file open,
that
decision is **frozen** because any dynamic filter is still `lit(true)`
at
that point. As `TopK` tightens its threshold at runtime, subsequent RGs
in
the already-opened file keep getting decoded even when their stats
already
prove they cannot beat the threshold. This is the dominant cost for
`ORDER BY ... LIMIT` queries on multi-RG files where file-level pruning
can't help (single large file, or scrambled-RG multi-file).
See the issue for a full architectural diagram and a concrete trace
showing where the wasted I/O / decompression / decode lives.
## What changes are included in this PR?
A single decoder paused at row-group boundaries, with a pruner consulted
between row groups and the decoder rebuilt via `into_builder()` to skip
the row groups the pruner just rejected. Three coordinated pieces:
1. **`RowGroupPruner`**
(`datafusion/datasource-parquet/src/push_decoder.rs`)
mirrors `FilePruner` at row-group granularity. It uses the
`DynamicFilterTracker` API from #22460 to subscribe once to every
not-yet-complete dynamic filter in the predicate; `tracker.changed()`
is a single atomic load — no tree traversal per check. The cached
`PruningPredicate` is rebuilt only when a watched filter has actually
moved, then evaluated against the next pending row group's statistics
via the existing `RowGroupPruningStatistics` adapter. Predicate
construction errors and predicate evaluation errors are counted into
two separate metrics so a flaky predicate path can never silently
drop data.
2. **Single-decoder iteration model**
(`PushDecoderStreamState::transition`). The opener builds **one**
`ParquetPushDecoder` from the prepared access plan, and the stream
uses arrow-rs 59's `ParquetRecordBatchReader` iterator to pause at
row-group boundaries. At each boundary the pruner is consulted
against the head of `rg_plan` (the remaining row-group indices). If
the pruner proves the head RG unwinnable, that index is dropped from
the plan and the decoder is **rebuilt via**
`decoder.into_builder().with_row_groups(remaining).build()` so the
skipped RGs are bypassed entirely — no decode, no row-filter eval.
Already-fetched buffered bytes for downstream RGs carry across the
rebuild.
3. **Gate: build the pruner only when the predicate actually moves.**
The opener creates a `RowGroupPruner` only when
`DynamicFilterTracking::classify(&predicate)` reports `Watching` (at
least one not-yet-complete dynamic filter) **and** more than one row
group remains in the access plan. Static or already-complete
predicates were fully consumed by `prune_by_statistics` at file open,
so re-evaluating them per RG boundary would be wasted work.
The earlier multi-decoder design (`PendingDecoderRun`,
`ParquetAccessPlan::split_runs`, `force_per_row_group`) is removed —
arrow-rs 59's `into_builder` + `with_row_groups` makes a single decoder
strictly more capable.
### Observability
- New `Count` metric `row_groups_pruned_dynamic_filter` on
`ParquetFileMetrics` surfaces the runtime saving.
- New `dynamic_rg_pruning=eligible` marker on `ParquetSource`'s
`EXPLAIN` (`fmt_extra` Default + Verbose) signals plan-time
eligibility, emitted whenever the predicate has a still-watching
dynamic portion. **Eligible** rather than **true** because the static
plan can't predict the runtime outcome.
### Benchmarks (`benchmarks/sort_pushdown_inexact`, 5 iterations)
| Query | main | this PR | Δ |
|---|---|---|---|
| Q1 `ORDER BY l_orderkey DESC LIMIT 100` | 6.99 ms | 3.80 ms | **−46%**
|
| Q2 `ORDER BY l_orderkey DESC LIMIT 1000` | 3.29 ms | 1.33 ms |
**−60%** |
| Q3 `SELECT * ... DESC LIMIT 100` | 11.17 ms | 9.91 ms | −11% |
| Q4 `SELECT * ... DESC LIMIT 1000` | 9.28 ms | 7.95 ms | −14% |
Narrow-projection queries gain the most — their per-RG cost is dominated
by metadata + sort-column read, which this PR eliminates for unwinnable
RGs. Wide-projection queries gain less because the *kept* RG's
all-column decode dominates total time, but still see meaningful
savings.
## Are these changes tested?
Three layers:
- **6 unit tests**:
- 3 in `push_decoder.rs::tests`: `RowGroupPruner` basic pruning,
tracker-driven dynamic-filter updates, fallback when the predicate
has no analyzable bounds.
- 3 in `source.rs::tests`: `dynamic_rg_pruning=eligible` marker
present on dynamic predicate, absent on static predicate, absent
when there is no predicate at all.
- **3 integration tests** in
`datafusion/core/tests/parquet/dynamic_row_group_pruning.rs`:
asserts `row_groups_pruned_dynamic_filter >= 1` end-to-end on a 5-RG
`ORDER BY DESC LIMIT 5` scan; a regression test for the
`prepare_access_plan` reorder bug that uses `ORDER BY ASC` against a
file written in descending value order so the sort-pushdown reorder
is exercised; and a quiet-without-TopK test that asserts the metric
stays at 0 (no spurious firing).
- **New SLT**
`datafusion/sqllogictest/test_files/dynamic_row_group_pruning.slt`:
asserts both `EXPLAIN` surfaces — plain `EXPLAIN` shows
`dynamic_rg_pruning=eligible`, and `EXPLAIN ANALYZE` pins
`row_groups_pruned_dynamic_filter=4` (five RGs, four pruned at
runtime).
`cargo clippy --all-targets --all-features -- -D warnings` clean.
## Are there any user-facing changes?
Two visible additions, both opt-in via existing dynamic-filter
infrastructure:
- New `row_groups_pruned_dynamic_filter` counter visible in
`EXPLAIN ANALYZE` for queries whose plan carries a
`DynamicFilterPhysicalExpr` (today: only TopK with
`enable_topk_dynamic_filter_pushdown=true`, which is the default).
- New `dynamic_rg_pruning=eligible` marker visible in `EXPLAIN`
output for the same queries.
No config changes, no API breakage, no behavior change for queries
without a dynamic predicate.1 parent ba67bb4 commit 9e68a86
24 files changed
Lines changed: 1385 additions & 419 deletions
File tree
- datafusion
- core/tests/parquet
- datasource-parquet/src
- opener
- sqllogictest/test_files
Large diffs are not rendered by default.
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
46 | 46 | | |
47 | 47 | | |
48 | 48 | | |
| 49 | + | |
49 | 50 | | |
50 | 51 | | |
51 | 52 | | |
| |||
99 | 100 | | |
100 | 101 | | |
101 | 102 | | |
| 103 | + | |
| 104 | + | |
| 105 | + | |
| 106 | + | |
102 | 107 | | |
103 | 108 | | |
104 | 109 | | |
| |||
147 | 152 | | |
148 | 153 | | |
149 | 154 | | |
| 155 | + | |
| 156 | + | |
| 157 | + | |
| 158 | + | |
| 159 | + | |
| 160 | + | |
150 | 161 | | |
151 | 162 | | |
152 | 163 | | |
| |||
259 | 270 | | |
260 | 271 | | |
261 | 272 | | |
| 273 | + | |
| 274 | + | |
| 275 | + | |
| 276 | + | |
| 277 | + | |
| 278 | + | |
| 279 | + | |
262 | 280 | | |
263 | 281 | | |
264 | 282 | | |
| |||
305 | 323 | | |
306 | 324 | | |
307 | 325 | | |
308 | | - | |
309 | | - | |
| 326 | + | |
| 327 | + | |
| 328 | + | |
| 329 | + | |
| 330 | + | |
| 331 | + | |
| 332 | + | |
| 333 | + | |
310 | 334 | | |
311 | 335 | | |
312 | 336 | | |
313 | 337 | | |
314 | 338 | | |
| 339 | + | |
| 340 | + | |
| 341 | + | |
| 342 | + | |
| 343 | + | |
| 344 | + | |
| 345 | + | |
| 346 | + | |
| 347 | + | |
| 348 | + | |
| 349 | + | |
| 350 | + | |
| 351 | + | |
315 | 352 | | |
316 | 353 | | |
317 | 354 | | |
| |||
1139 | 1176 | | |
1140 | 1177 | | |
1141 | 1178 | | |
| 1179 | + | |
1142 | 1180 | | |
1143 | 1181 | | |
1144 | 1182 | | |
| |||
1148 | 1186 | | |
1149 | 1187 | | |
1150 | 1188 | | |
1151 | | - | |
| 1189 | + | |
1152 | 1190 | | |
1153 | 1191 | | |
1154 | | - | |
1155 | | - | |
| 1192 | + | |
| 1193 | + | |
| 1194 | + | |
| 1195 | + | |
| 1196 | + | |
| 1197 | + | |
| 1198 | + | |
| 1199 | + | |
| 1200 | + | |
| 1201 | + | |
1156 | 1202 | | |
1157 | 1203 | | |
1158 | 1204 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
150 | 150 | | |
151 | 151 | | |
152 | 152 | | |
153 | | - | |
154 | | - | |
155 | | - | |
156 | | - | |
157 | | - | |
158 | | - | |
159 | | - | |
160 | | - | |
161 | | - | |
162 | | - | |
163 | | - | |
164 | | - | |
165 | | - | |
166 | | - | |
167 | | - | |
168 | | - | |
169 | | - | |
170 | | - | |
171 | 153 | | |
172 | 154 | | |
173 | 155 | | |
| |||
398 | 380 | | |
399 | 381 | | |
400 | 382 | | |
401 | | - | |
402 | | - | |
403 | | - | |
404 | | - | |
405 | | - | |
406 | | - | |
407 | 383 | | |
408 | 384 | | |
409 | 385 | | |
| |||
589 | 565 | | |
590 | 566 | | |
591 | 567 | | |
592 | | - | |
593 | | - | |
594 | | - | |
595 | | - | |
596 | | - | |
597 | | - | |
598 | | - | |
599 | | - | |
600 | | - | |
601 | | - | |
602 | | - | |
603 | | - | |
604 | | - | |
605 | | - | |
606 | | - | |
607 | | - | |
608 | | - | |
609 | | - | |
610 | | - | |
611 | | - | |
612 | | - | |
613 | | - | |
614 | | - | |
615 | | - | |
616 | | - | |
617 | | - | |
618 | | - | |
619 | | - | |
620 | | - | |
621 | | - | |
622 | | - | |
623 | | - | |
624 | | - | |
625 | | - | |
626 | | - | |
627 | | - | |
628 | | - | |
629 | | - | |
630 | | - | |
631 | | - | |
632 | | - | |
633 | | - | |
634 | | - | |
635 | | - | |
636 | | - | |
637 | | - | |
638 | | - | |
639 | | - | |
640 | 568 | | |
641 | 569 | | |
642 | 570 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
20 | 20 | | |
21 | 21 | | |
22 | 22 | | |
23 | | - | |
| 23 | + | |
| 24 | + | |
24 | 25 | | |
25 | 26 | | |
26 | 27 | | |
| |||
46 | 47 | | |
47 | 48 | | |
48 | 49 | | |
49 | | - | |
50 | | - | |
| 50 | + | |
| 51 | + | |
51 | 52 | | |
52 | 53 | | |
53 | 54 | | |
54 | | - | |
55 | | - | |
| 55 | + | |
| 56 | + | |
| 57 | + | |
56 | 58 | | |
57 | 59 | | |
58 | 60 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
53 | 53 | | |
54 | 54 | | |
55 | 55 | | |
| 56 | + | |
| 57 | + | |
| 58 | + | |
| 59 | + | |
| 60 | + | |
| 61 | + | |
| 62 | + | |
| 63 | + | |
56 | 64 | | |
57 | 65 | | |
58 | 66 | | |
| |||
198 | 206 | | |
199 | 207 | | |
200 | 208 | | |
| 209 | + | |
| 210 | + | |
| 211 | + | |
| 212 | + | |
| 213 | + | |
201 | 214 | | |
202 | 215 | | |
203 | 216 | | |
| |||
217 | 230 | | |
218 | 231 | | |
219 | 232 | | |
| 233 | + | |
220 | 234 | | |
221 | 235 | | |
222 | 236 | | |
| |||
0 commit comments