Skip to content

Commit 3ecdbd2

Browse files
committed
feat(parquet): apply TopK threshold to row-group statistics mid-scan
Closes apache#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.
1 parent 4c0f944 commit 3ecdbd2

9 files changed

Lines changed: 749 additions & 31 deletions

File tree

Lines changed: 117 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,117 @@
1+
// Licensed to the Apache Software Foundation (ASF) under one
2+
// or more contributor license agreements. See the NOTICE file
3+
// distributed with this work for additional information
4+
// regarding copyright ownership. The ASF licenses this file
5+
// to you under the Apache License, Version 2.0 (the
6+
// "License"); you may not use this file except in compliance
7+
// with the License. You may obtain a copy of the License at
8+
//
9+
// http://www.apache.org/licenses/LICENSE-2.0
10+
//
11+
// Unless required by applicable law or agreed to in writing,
12+
// software distributed under the License is distributed on an
13+
// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14+
// KIND, either express or implied. See the License for the
15+
// specific language governing permissions and limitations
16+
// under the License.
17+
18+
//! End-to-end test for **runtime row-group pruning** driven by a TopK
19+
//! `SortExec`'s `DynamicFilterPhysicalExpr`.
20+
//!
21+
//! A 5-row-group parquet file is constructed with disjoint statistics on
22+
//! the sort column (`v`): row group `i` contains values
23+
//! `[i*100, (i+1)*100)`. The query `ORDER BY v DESC LIMIT 5` fills the
24+
//! TopK heap from the row group with the largest values; the threshold
25+
//! then proves the remaining row groups cannot contribute. The runtime
26+
//! `RowGroupPruner` in the parquet scan must observe the tightened
27+
//! threshold and increment `row_groups_pruned_dynamic_filter`.
28+
//!
29+
//! We assert a property (`pruned >= 1`) rather than an exact count
30+
//! because batch-arrival timing affects how soon the TopK heap fills,
31+
//! and we don't want this test to become flaky.
32+
33+
use std::sync::Arc;
34+
35+
use arrow::array::{ArrayRef, Int64Array, RecordBatch};
36+
use arrow_schema::{DataType, Field, Schema};
37+
38+
use crate::parquet::Unit::RowGroup;
39+
use crate::parquet::{ContextWithParquet, Scenario};
40+
41+
/// Build five `RecordBatch`es whose `v` column ranges are disjoint:
42+
/// batch `i` carries `v` values `[i*100, (i+1)*100)`. When written with
43+
/// `max_row_group_row_count = 100` each batch lands in its own row group.
44+
fn build_five_disjoint_batches(schema: &Arc<Schema>) -> Vec<RecordBatch> {
45+
(0..5i64)
46+
.map(|rg| {
47+
let base = rg * 100;
48+
let values: Vec<i64> = (base..base + 100).collect();
49+
let col: ArrayRef = Arc::new(Int64Array::from(values));
50+
RecordBatch::try_new(Arc::clone(schema), vec![col]).unwrap()
51+
})
52+
.collect()
53+
}
54+
55+
/// `ORDER BY v DESC LIMIT 5` against a 5-RG file with disjoint per-RG
56+
/// stats must trigger runtime RG pruning: the first RG read fills the
57+
/// heap, and the tightened threshold proves every other RG unreachable.
58+
#[tokio::test]
59+
async fn dynamic_rg_pruning_metric_fires_for_topk_descending_limit() {
60+
let schema = Arc::new(Schema::new(vec![Field::new("v", DataType::Int64, false)]));
61+
let batches = build_five_disjoint_batches(&schema);
62+
63+
// `with_custom_data` honors the custom schema + batches and ignores
64+
// `Scenario`. `Unit::RowGroup(100)` enables `pushdown_filters`, which
65+
// is required for the TopK dynamic filter to reach the parquet scan.
66+
let mut ctx = ContextWithParquet::with_custom_data(
67+
Scenario::Int,
68+
RowGroup(100),
69+
Arc::clone(&schema),
70+
batches,
71+
)
72+
.await;
73+
74+
let output = ctx.query("SELECT v FROM t ORDER BY v DESC LIMIT 5").await;
75+
76+
assert_eq!(output.result_rows, 5, "query must return LIMIT rows",);
77+
78+
let pruned = output
79+
.row_groups_pruned_dynamic_filter()
80+
.expect("`row_groups_pruned_dynamic_filter` metric must be registered");
81+
assert!(
82+
pruned >= 1,
83+
"dynamic RG pruner must skip at least one row group; \
84+
pruned={pruned}\n{}",
85+
output.description(),
86+
);
87+
}
88+
89+
/// A query without ORDER BY does not produce a TopK and therefore no
90+
/// `DynamicFilterPhysicalExpr` reaches the scan. The runtime pruner must
91+
/// stay quiet — the metric should be 0.
92+
#[tokio::test]
93+
async fn dynamic_rg_pruning_metric_quiet_without_topk() {
94+
let schema = Arc::new(Schema::new(vec![Field::new("v", DataType::Int64, false)]));
95+
let batches = build_five_disjoint_batches(&schema);
96+
97+
let mut ctx = ContextWithParquet::with_custom_data(
98+
Scenario::Int,
99+
RowGroup(100),
100+
Arc::clone(&schema),
101+
batches,
102+
)
103+
.await;
104+
105+
// Plain `SELECT *` — no sort, no limit, no dynamic filter.
106+
let output = ctx.query("SELECT v FROM t").await;
107+
assert_eq!(output.result_rows, 500);
108+
109+
let pruned = output.row_groups_pruned_dynamic_filter().unwrap_or(0);
110+
assert_eq!(
111+
pruned,
112+
0,
113+
"without TopK there is no dynamic filter, so the runtime pruner \
114+
must not fire; pruned={pruned}\n{}",
115+
output.description(),
116+
);
117+
}

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

Lines changed: 8 additions & 0 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;
@@ -259,6 +260,13 @@ impl TestOutput {
259260
.map(|pm| pm.total_pruned())
260261
}
261262

263+
/// The number of row groups pruned at runtime by the dynamic
264+
/// row-group pruner (e.g. driven by a TopK `SortExec` threshold
265+
/// pushed down via `DynamicFilterPhysicalExpr`).
266+
fn row_groups_pruned_dynamic_filter(&self) -> Option<usize> {
267+
self.metric_value("row_groups_pruned_dynamic_filter")
268+
}
269+
262270
fn description(&self) -> String {
263271
format!(
264272
"Input:\n{}\nQuery:\n{}\nOutput:\n{}\nMetrics:\n{}",

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

Lines changed: 21 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -406,8 +406,19 @@ impl ParquetAccessPlan {
406406

407407
/// Split this plan into consecutive row group runs that share the same row
408408
/// filter requirement.
409-
pub(crate) fn split_runs(self, needs_filter: bool) -> Vec<RowGroupRun> {
410-
if !needs_filter || !self.has_fully_matched() {
409+
///
410+
/// When `force_per_row_group` is set, every scanned row group becomes its
411+
/// own run regardless of the fully-matched classification. Callers should
412+
/// turn this on when they intend to apply runtime-evaluated pruning
413+
/// between decoders (e.g. dynamic-filter-driven RG pruning), since the
414+
/// default grouping would coalesce away the inter-RG transition points
415+
/// the pruner depends on.
416+
pub(crate) fn split_runs(
417+
self,
418+
needs_filter: bool,
419+
force_per_row_group: bool,
420+
) -> Vec<RowGroupRun> {
421+
if !force_per_row_group && (!needs_filter || !self.has_fully_matched()) {
411422
return vec![RowGroupRun::new(needs_filter, self)];
412423
}
413424

@@ -424,9 +435,14 @@ impl ParquetAccessPlan {
424435
}
425436

426437
let row_group_needs_filter = !fully_matched;
427-
if let Some(run) = runs
428-
.last_mut()
429-
.filter(|run| run.needs_filter == row_group_needs_filter)
438+
// Coalesce consecutive RGs into a run only when (a) they share
439+
// the same filter requirement and (b) we're not forcing per-RG
440+
// splitting for runtime pruning.
441+
let can_coalesce = !force_per_row_group;
442+
if can_coalesce
443+
&& let Some(run) = runs
444+
.last_mut()
445+
.filter(|run| run.needs_filter == row_group_needs_filter)
430446
{
431447
run.access_plan.set(idx, access);
432448
if fully_matched {

‎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 [`row_groups_pruned_statistics`], which is decided once at
60+
/// access-plan time, this counter reflects row groups that survived the
61+
/// 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

‎datafusion/datasource-parquet/src/opener/mod.rs‎

Lines changed: 56 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -26,7 +26,9 @@ use self::encryption::EncryptionContext;
2626
use crate::access_plan::PreparedAccessPlan;
2727
use crate::decoder_projection::DecoderProjection;
2828
use crate::page_filter::PagePruningAccessPlanFilter;
29-
use crate::push_decoder::{DecoderBuilderConfig, PushDecoderStreamState};
29+
use crate::push_decoder::{
30+
DecoderBuilderConfig, PendingDecoderRun, PushDecoderStreamState, RowGroupPruner,
31+
};
3032
use crate::row_filter::RowFilterGenerator;
3133
use crate::row_group_filter::{BloomFilterStatistics, RowGroupAccessPlanFilter};
3234
use crate::{
@@ -1158,7 +1160,7 @@ impl RowGroupsPrunedParquetOpen {
11581160
&prepared.output_schema,
11591161
)?;
11601162

1161-
let (decoder, pending_decoders, remaining_limit) = {
1163+
let (decoder, pending_runs, remaining_limit) = {
11621164
let pushdown_predicate = prepared
11631165
.pushdown_filters
11641166
.then_some(prepared.predicate.as_ref())
@@ -1171,11 +1173,23 @@ impl RowGroupsPrunedParquetOpen {
11711173
&prepared.file_metrics,
11721174
);
11731175

1176+
// If the scan carries a *dynamic* predicate (e.g. the threshold
1177+
// expression a TopK SortExec pushes down), force one decoder per
1178+
// row group so the runtime row-group pruner has a transition
1179+
// point at every RG boundary. Without this, a TopK query whose
1180+
// initial predicate is `lit(true)` collapses to a single run
1181+
// covering every RG, hiding the inter-RG hook the pruner needs.
1182+
let force_per_rg_runs = prepared
1183+
.predicate
1184+
.as_ref()
1185+
.map(is_dynamic_physical_expr)
1186+
.unwrap_or(false);
11741187
// Split into consecutive runs of row groups that share the same filter
11751188
// requirement. Fully matched row groups skip the RowFilter; others need it.
11761189
// Reverse the run order for reverse scans so the combined decoder stream
11771190
// preserves the requested global row group order.
1178-
let mut runs = access_plan.split_runs(row_filter_generator.has_row_filter());
1191+
let mut runs = access_plan
1192+
.split_runs(row_filter_generator.has_row_filter(), force_per_rg_runs);
11791193
if prepared.reverse_row_groups {
11801194
runs.reverse();
11811195
}
@@ -1191,9 +1205,13 @@ impl RowGroupsPrunedParquetOpen {
11911205
decoder_limit,
11921206
};
11931207

1194-
// Build a decoder per run.
1195-
let mut decoders = VecDeque::with_capacity(runs.len());
1208+
// Build a decoder per run, tagging each with the row group
1209+
// indices it will scan so downstream consumers (e.g. dynamic
1210+
// RG-level pruning) can decide to skip a run at runtime.
1211+
let mut decoders: VecDeque<PendingDecoderRun> =
1212+
VecDeque::with_capacity(runs.len());
11961213
for run in runs {
1214+
let row_group_indices = run.access_plan.row_group_indexes();
11971215
let prepared_access_plan = prepare_access_plan(run.access_plan)?;
11981216
let mut builder =
11991217
decoder_config.build(prepared_access_plan, reader_metadata.clone());
@@ -1208,13 +1226,16 @@ impl RowGroupsPrunedParquetOpen {
12081226
.with_max_predicate_cache_size(max_predicate_cache_size);
12091227
}
12101228
}
1211-
decoders.push_back(builder.build()?);
1229+
decoders.push_back(PendingDecoderRun {
1230+
decoder: builder.build()?,
1231+
row_group_indices,
1232+
});
12121233
}
12131234

1214-
let decoder = decoders
1235+
let first = decoders
12151236
.pop_front()
12161237
.expect("at least one decoder must be created");
1217-
(decoder, decoders, remaining_limit)
1238+
(first.decoder, decoders, remaining_limit)
12181239
};
12191240

12201241
let predicate_cache_inner_records =
@@ -1224,16 +1245,38 @@ impl RowGroupsPrunedParquetOpen {
12241245

12251246
let files_ranges_pruned_statistics =
12261247
prepared.file_metrics.files_ranges_pruned_statistics.clone();
1248+
1249+
// Build a dynamic row-group pruner only when both halves are useful:
1250+
// 1) the scan has a predicate (so there is something to evaluate),
1251+
// 2) there is at least one pending run that could be skipped.
1252+
// The pruner consults the predicate's `snapshot_generation` so the
1253+
// cost is one rebuild per dynamic-filter update, not per RG check.
1254+
let row_group_pruner = match (&prepared.predicate, pending_runs.is_empty()) {
1255+
(Some(predicate), false) => Some(RowGroupPruner::new(
1256+
Arc::clone(predicate),
1257+
Arc::clone(&prepared.physical_file_schema),
1258+
Arc::clone(reader_metadata.metadata()),
1259+
prepared.file_metrics.predicate_evaluation_errors.clone(),
1260+
)),
1261+
_ => None,
1262+
};
1263+
let row_groups_pruned_dynamic = prepared
1264+
.file_metrics
1265+
.row_groups_pruned_dynamic_filter
1266+
.clone();
1267+
12271268
let stream = PushDecoderStreamState {
12281269
decoder,
1229-
pending_decoders,
1270+
pending_runs,
12301271
remaining_limit,
12311272
reader: prepared.async_file_reader,
12321273
decoder_projection,
12331274
arrow_reader_metrics,
12341275
predicate_cache_inner_records,
12351276
predicate_cache_records,
12361277
baseline_metrics: prepared.baseline_metrics,
1278+
row_group_pruner,
1279+
row_groups_pruned_dynamic,
12371280
}
12381281
.into_stream();
12391282

@@ -2594,7 +2637,7 @@ mod test {
25942637
RowGroupAccess::Scan,
25952638
RowGroupAccess::Scan,
25962639
]);
2597-
let runs = plan.split_runs(true);
2640+
let runs = plan.split_runs(true, false);
25982641
assert_eq!(runs.len(), 1);
25992642
assert!(runs[0].needs_filter);
26002643
assert_eq!(runs[0].access_plan.row_group_indexes(), vec![0, 1, 2]);
@@ -2612,7 +2655,7 @@ mod test {
26122655
plan.mark_fully_matched(1);
26132656
plan.mark_fully_matched(2);
26142657

2615-
let runs = plan.split_runs(true);
2658+
let runs = plan.split_runs(true, false);
26162659
assert_eq!(runs.len(), 1);
26172660
assert!(!runs[0].needs_filter);
26182661
assert_eq!(runs[0].access_plan.row_group_indexes(), vec![0, 1, 2]);
@@ -2632,7 +2675,7 @@ mod test {
26322675
plan.mark_fully_matched(2);
26332676
plan.mark_fully_matched(4);
26342677

2635-
let runs = plan.split_runs(true);
2678+
let runs = plan.split_runs(true, false);
26362679
assert_eq!(runs.len(), 4);
26372680

26382681
assert!(runs[0].needs_filter);
@@ -2659,7 +2702,7 @@ mod test {
26592702
]);
26602703
plan.mark_fully_matched(2);
26612704

2662-
let runs = plan.split_runs(true);
2705+
let runs = plan.split_runs(true, false);
26632706
assert_eq!(runs.len(), 3);
26642707

26652708
assert!(runs[0].needs_filter);

0 commit comments

Comments
 (0)