Skip to content

Commit fbbaf61

Browse files
committed
feat: initialize TopK dynamic filter threshold from parquet statistics
Before reading any parquet data, scan row group min/max statistics to compute an initial threshold for TopK's dynamic filter. This allows row-level filtering to benefit immediately from the first file opened, rather than waiting until TopK processes enough rows to build a threshold organically. Algorithm (single-column sort): - DESC LIMIT K: threshold = max(min) across RGs with num_rows >= K Filter: col > threshold - ASC LIMIT K: threshold = min(max) across RGs with num_rows >= K Filter: col < threshold Sort direction is read from sort_options on DynamicFilterPhysicalExpr, which is now set by SortExec::create_filter() for TopK queries. This makes the optimization work for ALL TopK queries on parquet, not just those with sort pushdown. The DynamicFilterPhysicalExpr is shared across all partitions, so each file's threshold update is visible to subsequent files globally. Graceful fallback: skips initialization when sort_options is absent, statistics are unavailable, column not found, or multi-column sort.
1 parent de86306 commit fbbaf61

3 files changed

Lines changed: 101 additions & 22 deletions

File tree

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

Lines changed: 63 additions & 21 deletions
Original file line numberDiff line numberDiff line change
@@ -1083,14 +1083,12 @@ impl RowGroupsPrunedParquetOpen {
10831083
// Initialize TopK dynamic filter from row group statistics.
10841084
// This sets an initial threshold before any data is read, so that
10851085
// subsequent row filtering can benefit immediately.
1086-
// Uses reverse_row_groups to infer sort direction:
1087-
// true => DESC (file declared ASC, reversed for DESC queries)
1088-
// false => ASC
1086+
// Sort direction is read from the DynamicFilterPhysicalExpr's
1087+
// sort_options (set by SortExec for TopK queries).
10891088
if let (Some(predicate), Some(limit)) = (&prepared.predicate, prepared.limit)
10901089
&& let Err(e) = try_init_topk_threshold(
10911090
predicate,
10921091
limit,
1093-
prepared.reverse_row_groups,
10941092
rg_metadata,
10951093
&prepared.physical_file_schema,
10961094
reader_metadata.parquet_schema(),
@@ -1265,7 +1263,6 @@ impl RowGroupsPrunedParquetOpen {
12651263
fn try_init_topk_threshold(
12661264
predicate: &Arc<dyn PhysicalExpr>,
12671265
limit: usize,
1268-
reverse_row_groups: bool,
12691266
rg_metadata: &[parquet::file::metadata::RowGroupMetaData],
12701267
arrow_schema: &Schema,
12711268
parquet_schema: &parquet::schema::types::SchemaDescriptor,
@@ -1276,17 +1273,25 @@ fn try_init_topk_threshold(
12761273
None => return Ok(()), // No dynamic filter found, nothing to do
12771274
};
12781275

1276+
// Read sort options from the dynamic filter (set by SortExec for TopK).
1277+
let sort_options = match dynamic_filter.sort_options() {
1278+
Some(opts) => opts,
1279+
None => return Ok(()), // No sort options, cannot determine direction
1280+
};
1281+
12791282
// Only handle single-column sort for now.
1280-
let children = dynamic_filter.children();
1281-
if children.len() != 1 {
1283+
if sort_options.len() != 1 {
12821284
debug!(
12831285
"Skipping TopK threshold initialization: expected 1 sort column, found {}",
1284-
children.len()
1286+
sort_options.len()
12851287
);
12861288
return Ok(());
12871289
}
12881290

1291+
let is_descending = sort_options[0].descending;
1292+
12891293
// The child must be a Column expression so we can look up statistics.
1294+
let children = dynamic_filter.children();
12901295
let col_expr: Arc<dyn PhysicalExpr> = Arc::clone(children[0]);
12911296
let col_any: &dyn std::any::Any = col_expr.as_ref();
12921297
let column = col_any.downcast_ref::<Column>().ok_or_else(|| {
@@ -1301,11 +1306,6 @@ fn try_init_topk_threshold(
13011306
let converter = StatisticsConverter::try_new(col_name, arrow_schema, parquet_schema)
13021307
.map_err(|e| DataFusionError::External(Box::new(e)))?;
13031308

1304-
// Determine sort direction from reverse_row_groups:
1305-
// reverse_row_groups = true => DESC sort (file is ASC, we reverse)
1306-
// reverse_row_groups = false => ASC sort
1307-
let is_descending = reverse_row_groups;
1308-
13091309
// Compute the threshold.
13101310
let threshold = if is_descending {
13111311
// DESC: threshold = max(min) across RGs with num_rows >= limit
@@ -3164,16 +3164,20 @@ mod test {
31643164
make_parquet_metadata_with_stats(&[rg0_values, rg1_values]);
31653165

31663166
let col_expr = Arc::new(Column::new("id", 0)) as Arc<dyn PhysicalExpr>;
3167-
let dynamic_filter = Arc::new(DynamicFilterPhysicalExpr::new(
3167+
let desc_opts = arrow::compute::SortOptions {
3168+
descending: true,
3169+
nulls_first: true,
3170+
};
3171+
let dynamic_filter = Arc::new(DynamicFilterPhysicalExpr::new_with_sort_options(
31683172
vec![Arc::clone(&col_expr)],
31693173
super::lit(true),
3174+
vec![desc_opts],
31703175
));
31713176
let predicate: Arc<dyn PhysicalExpr> = dynamic_filter.clone();
31723177

31733178
try_init_topk_threshold(
31743179
&predicate,
31753180
10,
3176-
true, // DESC => reverse_row_groups=true
31773181
&rg_metadata,
31783182
&arrow_schema,
31793183
&parquet_schema,
@@ -3206,16 +3210,20 @@ mod test {
32063210
make_parquet_metadata_with_stats(&[rg0_values, rg1_values]);
32073211

32083212
let col_expr = Arc::new(Column::new("id", 0)) as Arc<dyn PhysicalExpr>;
3209-
let dynamic_filter = Arc::new(DynamicFilterPhysicalExpr::new(
3213+
let asc_opts = arrow::compute::SortOptions {
3214+
descending: false,
3215+
nulls_first: false,
3216+
};
3217+
let dynamic_filter = Arc::new(DynamicFilterPhysicalExpr::new_with_sort_options(
32103218
vec![Arc::clone(&col_expr)],
32113219
super::lit(true),
3220+
vec![asc_opts],
32123221
));
32133222
let predicate: Arc<dyn PhysicalExpr> = dynamic_filter.clone();
32143223

32153224
try_init_topk_threshold(
32163225
&predicate,
32173226
10,
3218-
false, // ASC => reverse_row_groups=false
32193227
&rg_metadata,
32203228
&arrow_schema,
32213229
&parquet_schema,
@@ -3246,33 +3254,67 @@ mod test {
32463254
let result = try_init_topk_threshold(
32473255
&predicate,
32483256
10,
3249-
true,
32503257
&rg_metadata,
32513258
&arrow_schema,
32523259
&parquet_schema,
32533260
);
32543261
assert!(result.is_ok(), "should be a no-op when no dynamic filter");
32553262
}
32563263

3264+
#[test]
3265+
fn test_try_init_topk_threshold_no_sort_options() {
3266+
let rg0_values: Vec<i64> = (1..=200).collect();
3267+
let (rg_metadata, arrow_schema, parquet_schema) =
3268+
make_parquet_metadata_with_stats(&[rg0_values]);
3269+
3270+
// DynamicFilterPhysicalExpr WITHOUT sort_options => should be skipped
3271+
let col_expr = Arc::new(Column::new("id", 0)) as Arc<dyn PhysicalExpr>;
3272+
let dynamic_filter = Arc::new(DynamicFilterPhysicalExpr::new(
3273+
vec![col_expr],
3274+
super::lit(true),
3275+
));
3276+
let predicate: Arc<dyn PhysicalExpr> = dynamic_filter.clone();
3277+
3278+
let result = try_init_topk_threshold(
3279+
&predicate,
3280+
10,
3281+
&rg_metadata,
3282+
&arrow_schema,
3283+
&parquet_schema,
3284+
);
3285+
assert!(
3286+
result.is_ok(),
3287+
"no sort_options should be skipped gracefully"
3288+
);
3289+
3290+
let current = dynamic_filter.current().unwrap();
3291+
let display = format!("{current}");
3292+
assert_eq!(display, "true", "filter should remain unchanged: {display}");
3293+
}
3294+
32573295
#[test]
32583296
fn test_try_init_topk_threshold_multi_column_skipped() {
32593297
let rg0_values: Vec<i64> = (1..=200).collect();
32603298
let (rg_metadata, arrow_schema, parquet_schema) =
32613299
make_parquet_metadata_with_stats(&[rg0_values]);
32623300

3263-
// DynamicFilterPhysicalExpr with 2 children => should be skipped
3301+
// DynamicFilterPhysicalExpr with 2 sort columns => should be skipped
32643302
let col1 = Arc::new(Column::new("id", 0)) as Arc<dyn PhysicalExpr>;
32653303
let col2 = Arc::new(Column::new("id", 0)) as Arc<dyn PhysicalExpr>;
3266-
let dynamic_filter = Arc::new(DynamicFilterPhysicalExpr::new(
3304+
let opts = arrow::compute::SortOptions {
3305+
descending: true,
3306+
nulls_first: true,
3307+
};
3308+
let dynamic_filter = Arc::new(DynamicFilterPhysicalExpr::new_with_sort_options(
32673309
vec![col1, col2],
32683310
super::lit(true),
3311+
vec![opts, opts],
32693312
));
32703313
let predicate: Arc<dyn PhysicalExpr> = dynamic_filter.clone();
32713314

32723315
let result = try_init_topk_threshold(
32733316
&predicate,
32743317
10,
3275-
true,
32763318
&rg_metadata,
32773319
&arrow_schema,
32783320
&parquet_schema,

‎datafusion/physical-expr/src/expressions/dynamic_filters.rs‎

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -15,6 +15,7 @@
1515
// specific language governing permissions and limitations
1616
// under the License.
1717

18+
use arrow::compute::SortOptions;
1819
use parking_lot::RwLock;
1920
use std::{fmt::Display, hash::Hash, sync::Arc};
2021
use tokio::sync::watch;
@@ -74,6 +75,11 @@ pub struct DynamicFilterPhysicalExpr {
7475
/// But this can have overhead in production, so it's only included in our tests.
7576
data_type: Arc<RwLock<Option<DataType>>>,
7677
nullable: Arc<RwLock<Option<bool>>>,
78+
/// Optional sort options for each child expression.
79+
/// When set (e.g., by SortExec for TopK), downstream consumers like the
80+
/// parquet reader can use these to initialize the filter threshold from
81+
/// column statistics before reading any data.
82+
sort_options: Option<Vec<SortOptions>>,
7783
}
7884

7985
#[derive(Debug)]
@@ -177,9 +183,30 @@ impl DynamicFilterPhysicalExpr {
177183
state_watch,
178184
data_type: Arc::new(RwLock::new(None)),
179185
nullable: Arc::new(RwLock::new(None)),
186+
sort_options: None,
180187
}
181188
}
182189

190+
/// Create a new [`DynamicFilterPhysicalExpr`] with sort options.
191+
///
192+
/// Sort options indicate the sort direction for each child expression,
193+
/// enabling downstream consumers (e.g., parquet readers) to initialize
194+
/// the filter threshold from column statistics before reading data.
195+
pub fn new_with_sort_options(
196+
children: Vec<Arc<dyn PhysicalExpr>>,
197+
inner: Arc<dyn PhysicalExpr>,
198+
sort_options: Vec<SortOptions>,
199+
) -> Self {
200+
let mut this = Self::new(children, inner);
201+
this.sort_options = Some(sort_options);
202+
this
203+
}
204+
205+
/// Returns the sort options for each child expression, if available.
206+
pub fn sort_options(&self) -> Option<&[SortOptions]> {
207+
self.sort_options.as_deref()
208+
}
209+
183210
fn remap_children(
184211
children: &[Arc<dyn PhysicalExpr>],
185212
remapped_children: Option<&Vec<Arc<dyn PhysicalExpr>>>,
@@ -368,6 +395,7 @@ impl PhysicalExpr for DynamicFilterPhysicalExpr {
368395
state_watch: self.state_watch.clone(),
369396
data_type: Arc::clone(&self.data_type),
370397
nullable: Arc::clone(&self.nullable),
398+
sort_options: self.sort_options.clone(),
371399
}))
372400
}
373401

‎datafusion/physical-plan/src/sorts/sort.rs‎

Lines changed: 10 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -915,8 +915,17 @@ impl SortExec {
915915
.iter()
916916
.map(|sort_expr| Arc::clone(&sort_expr.expr))
917917
.collect::<Vec<_>>();
918+
let sort_options = self
919+
.expr
920+
.iter()
921+
.map(|sort_expr| sort_expr.options)
922+
.collect::<Vec<_>>();
918923
Arc::new(RwLock::new(TopKDynamicFilters::new(Arc::new(
919-
DynamicFilterPhysicalExpr::new(children, lit(true)),
924+
DynamicFilterPhysicalExpr::new_with_sort_options(
925+
children,
926+
lit(true),
927+
sort_options,
928+
),
920929
))))
921930
}
922931

0 commit comments

Comments
 (0)