Skip to content

Commit 22095cd

Browse files
committed
feat: reorder row groups by statistics during sort pushdown
When sort pushdown is active, reorder row groups within each file by their min/max statistics to match the requested sort order. This helps TopK queries find optimal values first via dynamic filter pushdown. - Add reorder_by_statistics to PreparedAccessPlan that sorts row_group_indexes by the first sort column's min values - Pass sort order from ParquetSource::try_pushdown_sort through to the opener via sort_order_for_reorder field - Reorder happens after pruning but before reverse (they compose) - Gracefully skips reorder when statistics unavailable, sort expr is not a simple column, row_selection present, or <=1 row groups Closes apache#21317
1 parent d68373e commit 22095cd

3 files changed

Lines changed: 134 additions & 2 deletions

File tree

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

Lines changed: 105 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -16,7 +16,12 @@
1616
// under the License.
1717

1818
use crate::sort::reverse_row_selection;
19+
use arrow::datatypes::Schema;
1920
use datafusion_common::{Result, assert_eq_or_internal_err};
21+
use datafusion_physical_expr::expressions::Column;
22+
use datafusion_physical_expr_common::sort_expr::LexOrdering;
23+
use log::debug;
24+
use parquet::arrow::arrow_reader::statistics::StatisticsConverter;
2025
use parquet::arrow::arrow_reader::{RowSelection, RowSelector};
2126
use parquet::file::metadata::{ParquetMetaData, RowGroupMetaData};
2227

@@ -377,6 +382,106 @@ impl PreparedAccessPlan {
377382
})
378383
}
379384

385+
/// Reorder row groups by their min statistics for the given sort order.
386+
///
387+
/// This helps TopK queries find optimal values first. For ASC sort,
388+
/// row groups with the smallest min values come first. For DESC sort,
389+
/// row groups with the largest min values come first.
390+
///
391+
/// Gracefully skips reordering when:
392+
/// - There is a row_selection (too complex to remap)
393+
/// - 0 or 1 row groups (nothing to reorder)
394+
/// - Sort expression is not a simple column reference
395+
/// - Statistics are unavailable
396+
pub(crate) fn reorder_by_statistics(
397+
mut self,
398+
sort_order: &LexOrdering,
399+
file_metadata: &ParquetMetaData,
400+
arrow_schema: &Schema,
401+
) -> Result<Self> {
402+
// Skip if row_selection present (too complex to remap)
403+
if self.row_selection.is_some() {
404+
debug!("Skipping RG reorder: row_selection present");
405+
return Ok(self);
406+
}
407+
408+
// Nothing to reorder
409+
if self.row_group_indexes.len() <= 1 {
410+
return Ok(self);
411+
}
412+
413+
// Get the first sort expression
414+
// LexOrdering is guaranteed non-empty, so first() returns &PhysicalSortExpr
415+
let first_sort_expr = sort_order.first();
416+
417+
// Extract column name from sort expression
418+
let column: &Column = match first_sort_expr.expr.as_any().downcast_ref::<Column>()
419+
{
420+
Some(col) => col,
421+
None => {
422+
debug!("Skipping RG reorder: sort expr is not a simple column");
423+
return Ok(self);
424+
}
425+
};
426+
427+
let descending = first_sort_expr.options.descending;
428+
429+
// Build statistics converter for this column
430+
let converter = match StatisticsConverter::try_new(
431+
column.name(),
432+
arrow_schema,
433+
file_metadata.file_metadata().schema_descr(),
434+
) {
435+
Ok(c) => c,
436+
Err(e) => {
437+
debug!("Skipping RG reorder: cannot create stats converter: {e}");
438+
return Ok(self);
439+
}
440+
};
441+
442+
// Get min values for the selected row groups
443+
let rg_metadata: Vec<&RowGroupMetaData> = self
444+
.row_group_indexes
445+
.iter()
446+
.map(|&idx| file_metadata.row_group(idx))
447+
.collect();
448+
449+
let min_values = match converter.row_group_mins(rg_metadata.iter().copied()) {
450+
Ok(vals) => vals,
451+
Err(e) => {
452+
debug!("Skipping RG reorder: cannot get min values: {e}");
453+
return Ok(self);
454+
}
455+
};
456+
457+
// Sort indices by min values
458+
let sort_options = arrow::compute::SortOptions {
459+
descending,
460+
nulls_first: first_sort_expr.options.nulls_first,
461+
};
462+
let sorted_indices = match arrow::compute::sort_to_indices(
463+
&min_values,
464+
Some(sort_options),
465+
None,
466+
) {
467+
Ok(indices) => indices,
468+
Err(e) => {
469+
debug!("Skipping RG reorder: sort failed: {e}");
470+
return Ok(self);
471+
}
472+
};
473+
474+
// Apply the reordering
475+
let original_indexes = self.row_group_indexes.clone();
476+
self.row_group_indexes = sorted_indices
477+
.values()
478+
.iter()
479+
.map(|&i| original_indexes[i as usize])
480+
.collect();
481+
482+
Ok(self)
483+
}
484+
380485
/// Reverse the access plan for reverse scanning
381486
pub(crate) fn reverse(mut self, file_metadata: &ParquetMetaData) -> Result<Self> {
382487
// Get the row group indexes before reversing

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

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -54,6 +54,7 @@ use datafusion_physical_expr_adapter::PhysicalExprAdapterFactory;
5454
use datafusion_physical_expr_common::physical_expr::{
5555
PhysicalExpr, is_dynamic_physical_expr,
5656
};
57+
use datafusion_physical_expr_common::sort_expr::LexOrdering;
5758
use datafusion_physical_plan::metrics::{
5859
BaselineMetrics, Count, ExecutionPlanMetricsSet, Gauge, MetricBuilder,
5960
MetricCategory, PruningMetrics,
@@ -154,6 +155,10 @@ pub(super) struct ParquetMorselizer {
154155
pub max_predicate_cache_size: Option<usize>,
155156
/// Whether to read row groups in reverse order
156157
pub reverse_row_groups: bool,
158+
/// Optional sort order used to reorder row groups by their min/max statistics.
159+
/// When set, row groups are reordered before reading so that row groups likely
160+
/// to contain optimal values (for TopK queries) are read first.
161+
pub sort_order_for_reorder: Option<LexOrdering>,
157162
}
158163

159164
impl fmt::Debug for ParquetMorselizer {
@@ -304,6 +309,7 @@ struct PreparedParquetOpen {
304309
predicate_creation_errors: Count,
305310
max_predicate_cache_size: Option<usize>,
306311
reverse_row_groups: bool,
312+
sort_order_for_reorder: Option<LexOrdering>,
307313
preserve_order: bool,
308314
#[cfg(feature = "parquet_encryption")]
309315
file_decryption_properties: Option<Arc<FileDecryptionProperties>>,
@@ -752,6 +758,7 @@ impl ParquetMorselizer {
752758
predicate_creation_errors,
753759
max_predicate_cache_size: self.max_predicate_cache_size,
754760
reverse_row_groups: self.reverse_row_groups,
761+
sort_order_for_reorder: self.sort_order_for_reorder.clone(),
755762
preserve_order: self.preserve_order,
756763
#[cfg(feature = "parquet_encryption")]
757764
file_decryption_properties: None,
@@ -1223,6 +1230,16 @@ impl RowGroupsPrunedParquetOpen {
12231230
// Prepare the access plan (extract row groups and row selection)
12241231
let mut prepared_plan = access_plan.prepare(rg_metadata)?;
12251232

1233+
// Reorder row groups by statistics if sort order is known.
1234+
// This helps TopK queries find optimal values first.
1235+
if let Some(sort_order) = &prepared.sort_order_for_reorder {
1236+
prepared_plan = prepared_plan.reorder_by_statistics(
1237+
sort_order,
1238+
file_metadata.as_ref(),
1239+
&prepared.physical_file_schema,
1240+
)?;
1241+
}
1242+
12261243
// Potentially reverse the access plan for performance.
12271244
// See `ParquetSource::try_pushdown_sort` for the rationale.
12281245
if prepared.reverse_row_groups {
@@ -1731,6 +1748,7 @@ mod test {
17311748
use datafusion_physical_expr_adapter::{
17321749
DefaultPhysicalExprAdapterFactory, replace_columns_with_literals,
17331750
};
1751+
use datafusion_physical_expr_common::sort_expr::LexOrdering;
17341752
use datafusion_physical_plan::metrics::ExecutionPlanMetricsSet;
17351753
use futures::{Stream, StreamExt};
17361754
use object_store::{ObjectStore, ObjectStoreExt, memory::InMemory, path::Path};
@@ -1759,6 +1777,7 @@ mod test {
17591777
coerce_int96: Option<arrow::datatypes::TimeUnit>,
17601778
max_predicate_cache_size: Option<usize>,
17611779
reverse_row_groups: bool,
1780+
sort_order_for_reorder: Option<LexOrdering>,
17621781
preserve_order: bool,
17631782
}
17641783

@@ -1785,6 +1804,7 @@ mod test {
17851804
coerce_int96: None,
17861805
max_predicate_cache_size: None,
17871806
reverse_row_groups: false,
1807+
sort_order_for_reorder: None,
17881808
preserve_order: false,
17891809
}
17901810
}
@@ -1900,6 +1920,7 @@ mod test {
19001920
encryption_factory: None,
19011921
max_predicate_cache_size: self.max_predicate_cache_size,
19021922
reverse_row_groups: self.reverse_row_groups,
1923+
sort_order_for_reorder: self.sort_order_for_reorder,
19031924
};
19041925
ParquetOpener { morselizer }
19051926
}

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

Lines changed: 8 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -55,7 +55,7 @@ use datafusion_physical_plan::metrics::ExecutionPlanMetricsSet;
5555

5656
#[cfg(feature = "parquet_encryption")]
5757
use datafusion_execution::parquet_encryption::EncryptionFactory;
58-
use datafusion_physical_expr_common::sort_expr::PhysicalSortExpr;
58+
use datafusion_physical_expr_common::sort_expr::{LexOrdering, PhysicalSortExpr};
5959
use itertools::Itertools;
6060
use object_store::ObjectStore;
6161
#[cfg(feature = "parquet_encryption")]
@@ -294,6 +294,8 @@ pub struct ParquetSource {
294294
/// so we still need to sort them after reading, so the reverse scan is inexact.
295295
/// Used to optimize ORDER BY ... DESC on sorted data.
296296
reverse_row_groups: bool,
297+
/// Optional sort order used to reorder row groups by min/max statistics.
298+
sort_order_for_reorder: Option<LexOrdering>,
297299
}
298300

299301
impl ParquetSource {
@@ -319,6 +321,7 @@ impl ParquetSource {
319321
#[cfg(feature = "parquet_encryption")]
320322
encryption_factory: None,
321323
reverse_row_groups: false,
324+
sort_order_for_reorder: None,
322325
}
323326
}
324327

@@ -570,6 +573,7 @@ impl FileSource for ParquetSource {
570573
encryption_factory: self.get_encryption_factory_with_config(),
571574
max_predicate_cache_size: self.max_predicate_cache_size(),
572575
reverse_row_groups: self.reverse_row_groups,
576+
sort_order_for_reorder: self.sort_order_for_reorder.clone(),
573577
},
574578
});
575579
Ok(opener)
@@ -817,7 +821,9 @@ impl FileSource for ParquetSource {
817821

818822
// Return Inexact because we're only reversing row group order,
819823
// not guaranteeing perfect row-level ordering
820-
let new_source = self.clone().with_reverse_row_groups(true);
824+
let sort_order = LexOrdering::new(order.iter().cloned());
825+
let mut new_source = self.clone().with_reverse_row_groups(true);
826+
new_source.sort_order_for_reorder = sort_order;
821827
Ok(SortOrderPushdownResult::Inexact {
822828
inner: Arc::new(new_source) as Arc<dyn FileSource>,
823829
})

0 commit comments

Comments
 (0)