Repository navigation
Commit ef23530
committed
feat(parquet): runtime row-group early stop via TopK dynamic filter
Closes apache#22407.
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.
This PR closes the gap with a single decoder paused at row-group
boundaries, 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` (`push_decoder.rs`) mirrors `FilePruner` at row-group
granularity. Uses `DynamicFilterTracker` (apache#22460) to subscribe once to
every not-yet-complete dynamic filter; `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. Predicate
construction errors and predicate evaluation errors are counted into
two separate metrics.
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`; pruned indices are dropped and the
decoder is rebuilt via
`decoder.into_builder().with_row_groups(remaining).build()` so the
skipped RGs are bypassed entirely. Already-fetched buffered bytes for
downstream RGs carry across the rebuild.
3. Gate: build the pruner only when
`DynamicFilterTracking::classify(&predicate)` reports `Watching` AND
more than one row group remains. 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.
Observability:
- New `Count` metric `row_groups_pruned_dynamic_filter` on
`ParquetFileMetrics`.
- New `dynamic_rg_pruning=eligible` marker on `ParquetSource::fmt_extra`
(Default + Verbose), emitted when the predicate has a still-watching
dynamic portion.
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% |
Tests:
- 6 unit tests (3 in push_decoder.rs::tests for RowGroupPruner; 3 in
source.rs::tests for the EXPLAIN marker).
- 3 integration tests in
`datafusion/core/tests/parquet/dynamic_row_group_pruning.rs`.
- New SLT `dynamic_row_group_pruning.slt` covering both EXPLAIN surfaces.
- `cargo clippy --all-targets --all-features -- -D warnings` clean.1 parent d428760 commit ef23530
24 files changed
Lines changed: 1102 additions & 409 deletions
File tree
- datafusion
- core/tests/parquet
- datasource-parquet/src
- opener
- sqllogictest/test_files
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
| 1 | + | |
| 2 | + | |
| 3 | + | |
| 4 | + | |
| 5 | + | |
| 6 | + | |
| 7 | + | |
| 8 | + | |
| 9 | + | |
| 10 | + | |
| 11 | + | |
| 12 | + | |
| 13 | + | |
| 14 | + | |
| 15 | + | |
| 16 | + | |
| 17 | + | |
| 18 | + | |
| 19 | + | |
| 20 | + | |
| 21 | + | |
| 22 | + | |
| 23 | + | |
| 24 | + | |
| 25 | + | |
| 26 | + | |
| 27 | + | |
| 28 | + | |
| 29 | + | |
| 30 | + | |
| 31 | + | |
| 32 | + | |
| 33 | + | |
| 34 | + | |
| 35 | + | |
| 36 | + | |
| 37 | + | |
| 38 | + | |
| 39 | + | |
| 40 | + | |
| 41 | + | |
| 42 | + | |
| 43 | + | |
| 44 | + | |
| 45 | + | |
| 46 | + | |
| 47 | + | |
| 48 | + | |
| 49 | + | |
| 50 | + | |
| 51 | + | |
| 52 | + | |
| 53 | + | |
| 54 | + | |
| 55 | + | |
| 56 | + | |
| 57 | + | |
| 58 | + | |
| 59 | + | |
| 60 | + | |
| 61 | + | |
| 62 | + | |
| 63 | + | |
| 64 | + | |
| 65 | + | |
| 66 | + | |
| 67 | + | |
| 68 | + | |
| 69 | + | |
| 70 | + | |
| 71 | + | |
| 72 | + | |
| 73 | + | |
| 74 | + | |
| 75 | + | |
| 76 | + | |
| 77 | + | |
| 78 | + | |
| 79 | + | |
| 80 | + | |
| 81 | + | |
| 82 | + | |
| 83 | + | |
| 84 | + | |
| 85 | + | |
| 86 | + | |
| 87 | + | |
| 88 | + | |
| 89 | + | |
| 90 | + | |
| 91 | + | |
| 92 | + | |
| 93 | + | |
| 94 | + | |
| 95 | + | |
| 96 | + | |
| 97 | + | |
| 98 | + | |
| 99 | + | |
| 100 | + | |
| 101 | + | |
| 102 | + | |
| 103 | + | |
| 104 | + | |
| 105 | + | |
| 106 | + | |
| 107 | + | |
| 108 | + | |
| 109 | + | |
| 110 | + | |
| 111 | + | |
| 112 | + | |
| 113 | + | |
| 114 | + | |
| 115 | + | |
| 116 | + | |
| 117 | + | |
| 118 | + | |
| 119 | + | |
| 120 | + | |
| 121 | + | |
| 122 | + | |
| 123 | + | |
| 124 | + | |
| 125 | + | |
| 126 | + | |
| 127 | + | |
| 128 | + | |
| 129 | + | |
| 130 | + | |
| 131 | + | |
| 132 | + | |
| 133 | + | |
| 134 | + | |
| 135 | + | |
| 136 | + | |
| 137 | + | |
| 138 | + | |
| 139 | + | |
| 140 | + | |
| 141 | + | |
| 142 | + | |
| 143 | + | |
| 144 | + | |
| 145 | + | |
| 146 | + | |
| 147 | + | |
| 148 | + | |
| 149 | + | |
| 150 | + | |
| 151 | + | |
| 152 | + | |
| 153 | + | |
| 154 | + | |
| 155 | + | |
| 156 | + | |
| 157 | + | |
| 158 | + | |
| 159 | + | |
| 160 | + | |
| 161 | + | |
| 162 | + | |
| 163 | + | |
| 164 | + | |
| 165 | + | |
| 166 | + | |
| 167 | + | |
| 168 | + | |
| 169 | + | |
| 170 | + | |
| 171 | + | |
| 172 | + | |
| 173 | + | |
| 174 | + | |
| 175 | + | |
| 176 | + | |
| 177 | + | |
| 178 | + | |
| 179 | + | |
| 180 | + | |
| 181 | + | |
| 182 | + | |
| 183 | + | |
| 184 | + | |
| 185 | + | |
| 186 | + | |
| 187 | + | |
| 188 | + | |
| 189 | + | |
| 190 | + | |
| 191 | + | |
| 192 | + | |
| 193 | + | |
| 194 | + | |
| 195 | + | |
| 196 | + | |
| 197 | + | |
| 198 | + | |
| 199 | + | |
| 200 | + | |
| 201 | + | |
| 202 | + | |
| 203 | + | |
| 204 | + | |
| 205 | + | |
| 206 | + | |
| 207 | + | |
| 208 | + | |
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
46 | 46 | | |
47 | 47 | | |
48 | 48 | | |
| 49 | + | |
49 | 50 | | |
50 | 51 | | |
51 | 52 | | |
| |||
147 | 148 | | |
148 | 149 | | |
149 | 150 | | |
| 151 | + | |
| 152 | + | |
| 153 | + | |
| 154 | + | |
| 155 | + | |
| 156 | + | |
150 | 157 | | |
151 | 158 | | |
152 | 159 | | |
| |||
259 | 266 | | |
260 | 267 | | |
261 | 268 | | |
| 269 | + | |
| 270 | + | |
| 271 | + | |
| 272 | + | |
| 273 | + | |
| 274 | + | |
| 275 | + | |
262 | 276 | | |
263 | 277 | | |
264 | 278 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
115 | 115 | | |
116 | 116 | | |
117 | 117 | | |
118 | | - | |
119 | | - | |
120 | | - | |
121 | | - | |
122 | | - | |
123 | | - | |
124 | | - | |
125 | | - | |
126 | | - | |
127 | | - | |
128 | | - | |
129 | | - | |
130 | | - | |
131 | | - | |
132 | | - | |
133 | | - | |
134 | | - | |
135 | | - | |
136 | 118 | | |
137 | 119 | | |
138 | 120 | | |
| |||
213 | 195 | | |
214 | 196 | | |
215 | 197 | | |
216 | | - | |
217 | | - | |
218 | | - | |
219 | | - | |
220 | | - | |
221 | | - | |
222 | 198 | | |
223 | 199 | | |
224 | 200 | | |
| |||
404 | 380 | | |
405 | 381 | | |
406 | 382 | | |
407 | | - | |
408 | | - | |
409 | | - | |
410 | | - | |
411 | | - | |
412 | | - | |
413 | | - | |
414 | | - | |
415 | | - | |
416 | | - | |
417 | | - | |
418 | | - | |
419 | | - | |
420 | | - | |
421 | | - | |
422 | | - | |
423 | | - | |
424 | | - | |
425 | | - | |
426 | | - | |
427 | | - | |
428 | | - | |
429 | | - | |
430 | | - | |
431 | | - | |
432 | | - | |
433 | | - | |
434 | | - | |
435 | | - | |
436 | | - | |
437 | | - | |
438 | | - | |
439 | | - | |
440 | | - | |
441 | | - | |
442 | | - | |
443 | | - | |
444 | | - | |
445 | | - | |
446 | | - | |
447 | | - | |
448 | | - | |
449 | | - | |
450 | | - | |
451 | | - | |
452 | | - | |
453 | | - | |
454 | | - | |
455 | 383 | | |
456 | 384 | | |
457 | 385 | | |
| |||
| 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 | | |
| |||
0 commit comments