Skip to content

Commit 9e68a86

Browse files
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

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

Lines changed: 435 additions & 0 deletions
Large diffs are not rendered by default.

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

Lines changed: 51 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -46,6 +46,7 @@ use tempfile::NamedTempFile;
4646

4747
mod content_defined_chunking;
4848
mod custom_reader;
49+
mod dynamic_row_group_pruning;
4950
#[cfg(feature = "parquet_encryption")]
5051
mod encryption;
5152
mod expr_adapter;
@@ -99,6 +100,10 @@ enum Unit {
99100
RowGroup(usize),
100101
// pass max row per page in parquet writer
101102
Page(usize),
103+
// pass max row per row_group AND max row per page. Use when a test
104+
// needs both multi-RG layout AND multiple pages within each RG so the
105+
// page index can prune at sub-RG granularity.
106+
RowGroupAndPage(usize, usize),
102107
}
103108

104109
/// Test fixture that has an execution context that has an external
@@ -147,6 +152,12 @@ struct TestOutput {
147152
}
148153

149154
impl TestOutput {
155+
/// Pretty-printed result batches, useful for asserting concrete row
156+
/// values in regression tests.
157+
fn pretty_results(&self) -> &str {
158+
&self.pretty_results
159+
}
160+
150161
/// retrieve the value of the named metric, if any
151162
fn metric_value(&self, metric_name: &str) -> Option<usize> {
152163
if let Some(pm) = self.pruning_metric(metric_name) {
@@ -259,6 +270,13 @@ impl TestOutput {
259270
.map(|pm| pm.total_pruned())
260271
}
261272

273+
/// The number of row groups pruned at runtime by the dynamic
274+
/// row-group pruner (e.g. driven by a TopK `SortExec` threshold
275+
/// pushed down via `DynamicFilterPhysicalExpr`).
276+
fn row_groups_pruned_dynamic_filter(&self) -> Option<usize> {
277+
self.metric_value("row_groups_pruned_dynamic_filter")
278+
}
279+
262280
fn description(&self) -> String {
263281
format!(
264282
"Input:\n{}\nQuery:\n{}\nOutput:\n{}\nMetrics:\n{}",
@@ -305,13 +323,32 @@ impl ContextWithParquet {
305323
Unit::RowGroup(row_per_group) => {
306324
config = config.with_parquet_bloom_filter_pruning(true);
307325
config.options_mut().execution.parquet.pushdown_filters = true;
308-
make_test_file_rg(scenario, row_per_group, custom_schema, custom_batches)
309-
.await
326+
make_test_file_rg(
327+
scenario,
328+
row_per_group,
329+
None,
330+
custom_schema,
331+
custom_batches,
332+
)
333+
.await
310334
}
311335
Unit::Page(row_per_page) => {
312336
config = config.with_parquet_page_index_pruning(true);
313337
make_test_file_page(scenario, row_per_page).await
314338
}
339+
Unit::RowGroupAndPage(row_per_group, row_per_page) => {
340+
config = config.with_parquet_bloom_filter_pruning(true);
341+
config = config.with_parquet_page_index_pruning(true);
342+
config.options_mut().execution.parquet.pushdown_filters = true;
343+
make_test_file_rg(
344+
scenario,
345+
row_per_group,
346+
Some(row_per_page),
347+
custom_schema,
348+
custom_batches,
349+
)
350+
.await
351+
}
315352
};
316353
let parquet_path = file.path().to_string_lossy();
317354

@@ -1139,6 +1176,7 @@ fn create_data_batch(scenario: Scenario) -> Vec<RecordBatch> {
11391176
async fn make_test_file_rg(
11401177
scenario: Scenario,
11411178
row_per_group: usize,
1179+
row_per_page: Option<usize>,
11421180
custom_schema: Option<SchemaRef>,
11431181
custom_batches: Option<Vec<RecordBatch>>,
11441182
) -> NamedTempFile {
@@ -1148,11 +1186,19 @@ async fn make_test_file_rg(
11481186
.tempfile()
11491187
.expect("tempfile creation");
11501188

1151-
let props = WriterProperties::builder()
1189+
let mut props_builder = WriterProperties::builder()
11521190
.set_max_row_group_row_count(Some(row_per_group))
11531191
.set_bloom_filter_enabled(true)
1154-
.set_statistics_enabled(EnabledStatistics::Page)
1155-
.build();
1192+
.set_statistics_enabled(EnabledStatistics::Page);
1193+
if let Some(rpp) = row_per_page {
1194+
// Bound rows per page so the page index can prune at sub-RG
1195+
// granularity. `write_batch_size` must also be set so the writer
1196+
// does not buffer the whole RG into one page.
1197+
props_builder = props_builder
1198+
.set_data_page_row_count_limit(rpp)
1199+
.set_write_batch_size(rpp);
1200+
}
1201+
let props = props_builder.build();
11561202

11571203
let (batches, schema) =
11581204
if let (Some(schema), Some(batches)) = (custom_schema, custom_batches) {

‎datafusion/datasource-parquet/src/access_plan.rs‎

Lines changed: 0 additions & 72 deletions
Original file line numberDiff line numberDiff line change
@@ -150,24 +150,6 @@ pub enum RowGroupAccess {
150150
Selection(RowSelection),
151151
}
152152

153-
/// A consecutive set of row groups that share the same row filter requirement.
154-
#[derive(Debug, Clone, PartialEq)]
155-
pub(crate) struct RowGroupRun {
156-
/// True if this run needs row filter evaluation.
157-
pub(crate) needs_filter: bool,
158-
/// The access plan for this run.
159-
pub(crate) access_plan: ParquetAccessPlan,
160-
}
161-
162-
impl RowGroupRun {
163-
fn new(needs_filter: bool, access_plan: ParquetAccessPlan) -> Self {
164-
Self {
165-
needs_filter,
166-
access_plan,
167-
}
168-
}
169-
}
170-
171153
impl RowGroupAccess {
172154
/// Return true if this row group should be scanned
173155
pub fn should_scan(&self) -> bool {
@@ -398,12 +380,6 @@ impl ParquetAccessPlan {
398380
&self.fully_matched
399381
}
400382

401-
/// Return true if any scanned row group is fully matched.
402-
fn has_fully_matched(&self) -> bool {
403-
self.row_group_index_iter()
404-
.any(|idx| self.is_fully_matched(idx))
405-
}
406-
407383
/// Set to scan only the [`RowSelection`] in the specified row group.
408384
///
409385
/// Behavior is different depending on the existing access
@@ -589,54 +565,6 @@ impl ParquetAccessPlan {
589565
self.row_groups
590566
}
591567

592-
/// Split this plan into consecutive row group runs that share the same row
593-
/// filter requirement.
594-
pub(crate) fn split_runs(self, needs_filter: bool) -> Vec<RowGroupRun> {
595-
if !needs_filter || !self.has_fully_matched() {
596-
return vec![RowGroupRun::new(needs_filter, self)];
597-
}
598-
599-
let num_row_groups = self.row_groups.len();
600-
let row_groups = self.row_groups;
601-
let fully_matched = self.fully_matched;
602-
let mut runs: Vec<RowGroupRun> = Vec::new();
603-
604-
for (idx, (access, fully_matched)) in
605-
row_groups.into_iter().zip(fully_matched).enumerate()
606-
{
607-
if !access.should_scan() {
608-
continue;
609-
}
610-
611-
let row_group_needs_filter = !fully_matched;
612-
if let Some(run) = runs
613-
.last_mut()
614-
.filter(|run| run.needs_filter == row_group_needs_filter)
615-
{
616-
run.access_plan.set(idx, access);
617-
if fully_matched {
618-
run.access_plan.mark_fully_matched(idx);
619-
}
620-
} else {
621-
let mut run_plan = ParquetAccessPlan::new_none(num_row_groups);
622-
run_plan.set(idx, access);
623-
if fully_matched {
624-
run_plan.mark_fully_matched(idx);
625-
}
626-
runs.push(RowGroupRun::new(row_group_needs_filter, run_plan));
627-
}
628-
}
629-
630-
if runs.is_empty() {
631-
vec![RowGroupRun::new(
632-
needs_filter,
633-
ParquetAccessPlan::new_none(num_row_groups),
634-
)]
635-
} else {
636-
runs
637-
}
638-
}
639-
640568
/// Prepare this plan and resolve to the final `PreparedAccessPlan`
641569
pub(crate) fn prepare(
642570
self,

‎datafusion/datasource-parquet/src/decoder_projection.rs‎

Lines changed: 7 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -20,7 +20,8 @@
2020
//! [`DecoderProjection`] owns the two halves of "project a decoded parquet
2121
//! batch onto the scan's output schema":
2222
//!
23-
//! * the [`ProjectionMask`] installed on every parquet decoder run, and
23+
//! * the [`ProjectionMask`] installed on the parquet decoder (and on any
24+
//! rebuild performed via `into_builder` at a row-group boundary), and
2425
//! * the per-batch transform ([`DecoderProjection::map`]) that applies the
2526
//! projector and, when needed, rebuilds the batch with the user's
2627
//! `output_schema` to recover metadata / nullability the file schema does
@@ -46,13 +47,14 @@ use parquet::schema::types::SchemaDescriptor;
4647
use crate::opener::{VirtualColumnsState, append_fields};
4748
use crate::row_filter::build_projection_read_plan;
4849

49-
/// Per-file decoder projection: the [`ProjectionMask`] installed on every
50-
/// parquet decoder run, plus the per-batch transform that maps the decoder's
50+
/// Per-file decoder projection: the [`ProjectionMask`] installed on the
51+
/// parquet decoder, plus the per-batch transform that maps the decoder's
5152
/// output onto the scan's `output_schema`.
5253
///
5354
/// Built once per file by the opener via [`Self::try_new`]; the
54-
/// push-decoder stream installs [`Self::projection_mask`] on each decoder
55-
/// and calls [`Self::map`] on every decoded batch.
55+
/// push-decoder stream installs [`Self::projection_mask`] on the decoder
56+
/// (and on any rebuild performed via `into_builder` at a row-group
57+
/// boundary) and calls [`Self::map`] on every decoded batch.
5658
pub(crate) struct DecoderProjection {
5759
projection_mask: ProjectionMask,
5860
projector: Projector,

‎datafusion/datasource-parquet/src/metrics.rs‎

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -53,6 +53,14 @@ pub struct ParquetFileMetrics {
5353
pub limit_pruned_row_groups: PruningMetrics,
5454
/// Number of row groups pruned by statistics
5555
pub row_groups_pruned_statistics: PruningMetrics,
56+
/// Number of row groups pruned at runtime by a dynamic predicate
57+
/// (e.g. the threshold expression a TopK `SortExec` pushes down).
58+
///
59+
/// Unlike [`Self::row_groups_pruned_statistics`], which is decided once
60+
/// at access-plan time, this counter reflects row groups that survived
61+
/// the initial pruning but were proved unreachable mid-scan after the
62+
/// dynamic filter tightened.
63+
pub row_groups_pruned_dynamic_filter: Count,
5664
/// Total number of bytes scanned
5765
pub bytes_scanned: Count,
5866
/// Total rows filtered out by predicates pushed into parquet scan
@@ -198,6 +206,11 @@ impl ParquetFileMetrics {
198206
.with_category(MetricCategory::Rows)
199207
.gauge("predicate_cache_records", partition);
200208

209+
let row_groups_pruned_dynamic_filter = MetricBuilder::new(metrics)
210+
.with_new_label("filename", filename.to_string())
211+
.with_type(MetricType::Summary)
212+
.counter("row_groups_pruned_dynamic_filter", partition);
213+
201214
Self {
202215
files_ranges_pruned_statistics,
203216
predicate_evaluation_errors,
@@ -217,6 +230,7 @@ impl ParquetFileMetrics {
217230
scan_efficiency_ratio,
218231
predicate_cache_inner_records,
219232
predicate_cache_records,
233+
row_groups_pruned_dynamic_filter,
220234
}
221235
}
222236

0 commit comments

Comments
 (0)