You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
Commit 3ecdbd2
Browse filesBrowse the repository at this point in the historyBrowse files
feat(parquet): apply TopK threshold to row-group statistics mid-scan
Closesapache#22407.
## What
Adds runtime row-group pruning between push-decoder runs, driven by the
dynamic predicate a TopK `SortExec` pushes down via
`DynamicFilterPhysicalExpr`. As the heap fills, the threshold tightens,
and subsequent row groups whose statistics prove they cannot contribute
are skipped without ever invoking their decoder — zero IO, zero decode.
## Why
DataFusion already prunes parquet at three granularities — file
(`EarlyStoppingStream`), row group at scan-startup (`PruningPredicate`),
and row (`RowFilter`). There is a gap: once `Layer 1` selects a file's
row groups, that decision is **frozen** at scan startup, when the
dynamic filter is still `lit(true)`. As `TopK` tightens at runtime,
subsequent RGs in the already-opened file keep being decoded even when
stats prove they can't beat the threshold. This is the dominant cost
for `ORDER BY ... LIMIT` queries on multi-RG files. See apache#22407 for the
full architectural trace.
## How
Two coordinated pieces:
1. **`RowGroupPruner`** (in `push_decoder.rs`). Mirrors `FilePruner`'s
pattern at row-group granularity: tracks `snapshot_generation` so
the cached `PruningPredicate` is rebuilt only when the dynamic
filter has actually moved; evaluates against the next pending run's
row-group stats via the existing `RowGroupPruningStatistics`
adapter from `row_group_filter.rs`. Errors fall back to "don't
prune" — a flaky pruning path never silently drops data.
2. **Per-RG decoder splitting when the predicate is dynamic**.
`RowGroupAccessPlan::split_runs` previously coalesced consecutive
same-`fully_matched` RGs into a single run. For ORDER BY + LIMIT
the initial dynamic filter is `lit(true)`, the static fully-matched
analysis marks nothing, and `split_runs` collapsed every RG into
one run — leaving no inter-run hook for runtime pruning. A new
`force_per_row_group` flag (set by `is_dynamic_physical_expr`)
disables coalescing for dynamic predicates only, so static-WHERE
queries pay nothing.
Plumbing: `PendingDecoderRun` wraps each queued decoder with its row
group indices. `PushDecoderStreamState::transition` consults the
pruner at every run boundary and skips runs whose row groups are
proved unwinnable.
## 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 — *eligible* rather than *true* because the static plan
can't predict the runtime outcome.
## Benchmarks (`benchmarks/sort_pushdown_inexact`, 5 iters)
| 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.
## Test coverage
- 6 new unit tests: 3 on `RowGroupPruner` (basic pruning,
generation-tracked dynamic updates, fallback when predicate has no
analyzable bounds) + 3 on `fmt_extra` marker (present on dynamic
predicate, absent on static, absent on no-predicate).
- 2 new 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 TopK query, and asserts the metric stays at 0 when no TopK is
present (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).
129 parquet unit + 204 parquet integration + SLT all pass.
`cargo clippy -D warnings` clean.
0 commit comments