Skip to content

Commit ef23530

Browse files
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
Lines changed: 208 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,208 @@
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+
/// Build five `RecordBatch`es in *descending* value order: batch 0 holds
56+
/// `v ∈ [400, 500)`, batch 4 holds `v ∈ [0, 100)`. The physical row-group
57+
/// order on disk therefore does **not** match the order a `ORDER BY v ASC`
58+
/// query wants — sort-pushdown's `reorder_by_statistics` must rearrange
59+
/// the access plan so the scan reads RG 4 first, then RG 3, etc.
60+
fn build_five_disjoint_batches_desc(schema: &Arc<Schema>) -> Vec<RecordBatch> {
61+
(0..5i64)
62+
.map(|rg| {
63+
let base = (4 - rg) * 100;
64+
let values: Vec<i64> = (base..base + 100).collect();
65+
let col: ArrayRef = Arc::new(Int64Array::from(values));
66+
RecordBatch::try_new(Arc::clone(schema), vec![col]).unwrap()
67+
})
68+
.collect()
69+
}
70+
71+
/// `ORDER BY v DESC LIMIT 5` against a 5-RG file with disjoint per-RG
72+
/// stats must trigger runtime RG pruning: the first RG read fills the
73+
/// heap, and the tightened threshold proves every other RG unreachable.
74+
#[tokio::test]
75+
async fn dynamic_rg_pruning_metric_fires_for_topk_descending_limit() {
76+
let schema = Arc::new(Schema::new(vec![Field::new("v", DataType::Int64, false)]));
77+
let batches = build_five_disjoint_batches(&schema);
78+
79+
// `with_custom_data` honors the custom schema + batches and ignores
80+
// `Scenario`. `Unit::RowGroup(100)` enables `pushdown_filters`, which
81+
// is required for the TopK dynamic filter to reach the parquet scan.
82+
let mut ctx = ContextWithParquet::with_custom_data(
83+
Scenario::Int,
84+
RowGroup(100),
85+
Arc::clone(&schema),
86+
batches,
87+
)
88+
.await;
89+
90+
let output = ctx.query("SELECT v FROM t ORDER BY v DESC LIMIT 5").await;
91+
92+
assert_eq!(output.result_rows, 5, "query must return LIMIT rows",);
93+
94+
let pruned = output
95+
.row_groups_pruned_dynamic_filter()
96+
.expect("`row_groups_pruned_dynamic_filter` metric must be registered");
97+
assert!(
98+
pruned >= 1,
99+
"dynamic RG pruner must skip at least one row group; \
100+
pruned={pruned}\n{}",
101+
output.description(),
102+
);
103+
}
104+
105+
/// Regression for the rg_plan / `reorder_by_statistics` ordering bug.
106+
///
107+
/// When `sort_order_for_reorder` is set on the parquet scan,
108+
/// `prepare_access_plan` calls
109+
/// [`PreparedAccessPlan::reorder_by_statistics`], which rearranges
110+
/// `row_group_indexes` so the decoder reads row groups in stats-optimal
111+
/// order (smallest-min first for ASC, etc.). The stream's per-RG plan
112+
/// (`rg_plan`) — which the runtime pruner walks one entry at a time —
113+
/// **must use this reordered list**, not the access plan's natural
114+
/// (index-ascending) order. Otherwise the pruner would consult the
115+
/// metadata of RG K while the decoder is actually about to yield RG K',
116+
/// silently producing wrong results.
117+
///
118+
/// This test makes the failure visible:
119+
///
120+
/// - File is written with RGs in *descending* `v` order (RG 0 has the
121+
/// largest values, RG 4 has the smallest).
122+
/// - Query is `ORDER BY v ASC LIMIT 5`, so sort-pushdown reorders the
123+
/// access plan to read RG 4 first, then RG 3, etc.
124+
/// - The smallest five values (which form the entire correct LIMIT
125+
/// answer) live in RG 4 alone. After they are emitted, the TopK
126+
/// threshold tightens enough that the per-RG pruner skips every other
127+
/// RG.
128+
///
129+
/// Without the fix, `rg_plan` would be `[0, 1, 2, 3, 4]` while the
130+
/// decoder reads `[4, 3, 2, 1, 0]`. The first yielded reader (for RG 4
131+
/// in the decoder) would be tracked as if it were RG 0, the pruner
132+
/// would check RG 1's stats (id range 300..400) against a threshold
133+
/// already tightened to `v < 5`, prune RG 1 (because nothing in
134+
/// 300..400 can satisfy `v < 5`), and then the rebuild via
135+
/// `into_builder` would scan a row group whose data does not match its
136+
/// expected metadata. The query would return fewer than five rows or
137+
/// the wrong rows.
138+
#[tokio::test]
139+
async fn dynamic_rg_pruning_handles_sort_pushdown_reorder() {
140+
let schema = Arc::new(Schema::new(vec![Field::new("v", DataType::Int64, false)]));
141+
let batches = build_five_disjoint_batches_desc(&schema);
142+
143+
let mut ctx = ContextWithParquet::with_custom_data(
144+
Scenario::Int,
145+
RowGroup(100),
146+
Arc::clone(&schema),
147+
batches,
148+
)
149+
.await;
150+
151+
let output = ctx.query("SELECT v FROM t ORDER BY v ASC LIMIT 5").await;
152+
153+
// Correctness — the five smallest values in the file are 0..=4.
154+
// If `rg_plan` is misaligned with the decoder's read order, the
155+
// pruner consults the wrong RG's stats and the result row count or
156+
// values would drift.
157+
assert_eq!(output.result_rows, 5, "query must return LIMIT rows");
158+
let formatted = output.pretty_results();
159+
for v in 0..=4i64 {
160+
assert!(
161+
formatted.contains(&format!("| {v} ")),
162+
"output must contain the smallest value {v}; got:\n{formatted}",
163+
);
164+
}
165+
166+
// Behavior — the per-RG pruner must engage. We don't pin the exact
167+
// count (batch-arrival timing affects how soon the heap fills); we
168+
// only require that at least one row group is skipped at runtime.
169+
let pruned = output
170+
.row_groups_pruned_dynamic_filter()
171+
.expect("`row_groups_pruned_dynamic_filter` metric must be registered");
172+
assert!(
173+
pruned >= 1,
174+
"with `sort_order_for_reorder` active and a tight TopK, the \
175+
runtime pruner must skip at least one row group; pruned={pruned}\n{}",
176+
output.description(),
177+
);
178+
}
179+
180+
/// A query without ORDER BY does not produce a TopK and therefore no
181+
/// `DynamicFilterPhysicalExpr` reaches the scan. The runtime pruner must
182+
/// stay quiet — the metric should be 0.
183+
#[tokio::test]
184+
async fn dynamic_rg_pruning_metric_quiet_without_topk() {
185+
let schema = Arc::new(Schema::new(vec![Field::new("v", DataType::Int64, false)]));
186+
let batches = build_five_disjoint_batches(&schema);
187+
188+
let mut ctx = ContextWithParquet::with_custom_data(
189+
Scenario::Int,
190+
RowGroup(100),
191+
Arc::clone(&schema),
192+
batches,
193+
)
194+
.await;
195+
196+
// Plain `SELECT *` — no sort, no limit, no dynamic filter.
197+
let output = ctx.query("SELECT v FROM t").await;
198+
assert_eq!(output.result_rows, 500);
199+
200+
let pruned = output.row_groups_pruned_dynamic_filter().unwrap_or(0);
201+
assert_eq!(
202+
pruned,
203+
0,
204+
"without TopK there is no dynamic filter, so the runtime pruner \
205+
must not fire; pruned={pruned}\n{}",
206+
output.description(),
207+
);
208+
}

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

Lines changed: 14 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;
@@ -147,6 +148,12 @@ struct TestOutput {
147148
}
148149

149150
impl TestOutput {
151+
/// Pretty-printed result batches, useful for asserting concrete row
152+
/// values in regression tests.
153+
fn pretty_results(&self) -> &str {
154+
&self.pretty_results
155+
}
156+
150157
/// retrieve the value of the named metric, if any
151158
fn metric_value(&self, metric_name: &str) -> Option<usize> {
152159
if let Some(pm) = self.pruning_metric(metric_name) {
@@ -259,6 +266,13 @@ impl TestOutput {
259266
.map(|pm| pm.total_pruned())
260267
}
261268

269+
/// The number of row groups pruned at runtime by the dynamic
270+
/// row-group pruner (e.g. driven by a TopK `SortExec` threshold
271+
/// pushed down via `DynamicFilterPhysicalExpr`).
272+
fn row_groups_pruned_dynamic_filter(&self) -> Option<usize> {
273+
self.metric_value("row_groups_pruned_dynamic_filter")
274+
}
275+
262276
fn description(&self) -> String {
263277
format!(
264278
"Input:\n{}\nQuery:\n{}\nOutput:\n{}\nMetrics:\n{}",

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

Lines changed: 0 additions & 72 deletions
Original file line numberDiff line numberDiff line change
@@ -115,24 +115,6 @@ pub enum RowGroupAccess {
115115
Selection(RowSelection),
116116
}
117117

118-
/// A consecutive set of row groups that share the same row filter requirement.
119-
#[derive(Debug, Clone, PartialEq)]
120-
pub(crate) struct RowGroupRun {
121-
/// True if this run needs row filter evaluation.
122-
pub(crate) needs_filter: bool,
123-
/// The access plan for this run.
124-
pub(crate) access_plan: ParquetAccessPlan,
125-
}
126-
127-
impl RowGroupRun {
128-
fn new(needs_filter: bool, access_plan: ParquetAccessPlan) -> Self {
129-
Self {
130-
needs_filter,
131-
access_plan,
132-
}
133-
}
134-
}
135-
136118
impl RowGroupAccess {
137119
/// Return true if this row group should be scanned
138120
pub fn should_scan(&self) -> bool {
@@ -213,12 +195,6 @@ impl ParquetAccessPlan {
213195
&self.fully_matched
214196
}
215197

216-
/// Return true if any scanned row group is fully matched.
217-
fn has_fully_matched(&self) -> bool {
218-
self.row_group_index_iter()
219-
.any(|idx| self.is_fully_matched(idx))
220-
}
221-
222198
/// Set to scan only the [`RowSelection`] in the specified row group.
223199
///
224200
/// Behavior is different depending on the existing access
@@ -404,54 +380,6 @@ impl ParquetAccessPlan {
404380
self.row_groups
405381
}
406382

407-
/// Split this plan into consecutive row group runs that share the same row
408-
/// filter requirement.
409-
pub(crate) fn split_runs(self, needs_filter: bool) -> Vec<RowGroupRun> {
410-
if !needs_filter || !self.has_fully_matched() {
411-
return vec![RowGroupRun::new(needs_filter, self)];
412-
}
413-
414-
let num_row_groups = self.row_groups.len();
415-
let row_groups = self.row_groups;
416-
let fully_matched = self.fully_matched;
417-
let mut runs: Vec<RowGroupRun> = Vec::new();
418-
419-
for (idx, (access, fully_matched)) in
420-
row_groups.into_iter().zip(fully_matched).enumerate()
421-
{
422-
if !access.should_scan() {
423-
continue;
424-
}
425-
426-
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)
430-
{
431-
run.access_plan.set(idx, access);
432-
if fully_matched {
433-
run.access_plan.mark_fully_matched(idx);
434-
}
435-
} else {
436-
let mut run_plan = ParquetAccessPlan::new_none(num_row_groups);
437-
run_plan.set(idx, access);
438-
if fully_matched {
439-
run_plan.mark_fully_matched(idx);
440-
}
441-
runs.push(RowGroupRun::new(row_group_needs_filter, run_plan));
442-
}
443-
}
444-
445-
if runs.is_empty() {
446-
vec![RowGroupRun::new(
447-
needs_filter,
448-
ParquetAccessPlan::new_none(num_row_groups),
449-
)]
450-
} else {
451-
runs
452-
}
453-
}
454-
455383
/// Prepare this plan and resolve to the final `PreparedAccessPlan`
456384
pub(crate) fn prepare(
457385
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,

0 commit comments

Comments
 (0)