Skip to content

Commit 4130ce4

Browse files
zhuqi-lucasclaude
andcommitted
feat: sort file groups by statistics during sort pushdown
Sort files within each file group by min/max statistics during sort pushdown to better align with the requested ordering. When files are non-overlapping and within-file ordering is guaranteed (e.g. Parquet with sorting_columns metadata), the SortExec is completely eliminated. Key changes: - ParquetSource::try_pushdown_sort returns Exact when natural ordering satisfies the request, enabling sort elimination - FileScanConfig sorts files within groups by statistics and verifies non-overlapping property to determine Exact vs Inexact - Multi-group files are redistributed consecutively to preserve both sort elimination and I/O parallelism across partitions - Statistics-based file reordering as fallback when FileSource returns Unsupported (benefits TopK via better dynamic filter pruning) - New sort_pushdown benchmark for measuring sort elimination speedup Closes apache#17348 Co-Authored-By: Claude Opus 4.6 (1M context) <[email protected]>
1 parent c17c87c commit 4130ce4

4 files changed

Lines changed: 974 additions & 111 deletions

File tree

‎datafusion/core/tests/physical_optimizer/pushdown_sort.rs‎

Lines changed: 5 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -255,8 +255,9 @@ fn test_prefix_match_through_transparent_nodes() {
255255
}
256256

257257
#[test]
258-
fn test_no_prefix_match_wrong_direction() {
259-
// Test that prefix matching does NOT work if the direction is wrong
258+
fn test_exact_prefix_match_same_direction() {
259+
// Test that when the requested sort [a DESC] matches a prefix of the source's
260+
// natural ordering [a DESC, b ASC], the Sort is eliminated (Exact pushdown).
260261
let schema = schema();
261262

262263
// Source has [a DESC, b ASC] ordering
@@ -265,7 +266,7 @@ fn test_no_prefix_match_wrong_direction() {
265266
let source_ordering = LexOrdering::new(vec![a.clone().reverse(), b]).unwrap();
266267
let source = parquet_exec_with_sort(schema.clone(), vec![source_ordering]);
267268

268-
// Request [a DESC] - same direction as source, NOT a reverse prefix
269+
// Request [a DESC] - same direction as source prefix, Sort should be eliminated
269270
let same_direction = LexOrdering::new(vec![a.clone().reverse()]).unwrap();
270271
let plan = sort_exec(same_direction, source);
271272

@@ -278,8 +279,7 @@ fn test_no_prefix_match_wrong_direction() {
278279
- DataSourceExec: file_groups={1 group: [[x]]}, projection=[a, b, c, d, e], output_ordering=[a@0 DESC NULLS LAST, b@1 ASC], file_type=parquet
279280
output:
280281
Ok:
281-
- SortExec: expr=[a@0 DESC NULLS LAST], preserve_partitioning=[false]
282-
- DataSourceExec: file_groups={1 group: [[x]]}, projection=[a, b, c, d, e], output_ordering=[a@0 DESC NULLS LAST, b@1 ASC], file_type=parquet
282+
- DataSourceExec: file_groups={1 group: [[x]]}, projection=[a, b, c, d, e], output_ordering=[a@0 DESC NULLS LAST, b@1 ASC], file_type=parquet
283283
"
284284
);
285285
}

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

Lines changed: 19 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -743,19 +743,17 @@ impl FileSource for ParquetSource {
743743
///
744744
/// With both pieces of information, ParquetSource can decide what optimizations to apply.
745745
///
746-
/// # Phase 1 Behavior (Current)
747-
/// Returns `Inexact` when reversing the row group scan order would help satisfy the
748-
/// requested ordering. We still need a Sort operator at a higher level because:
749-
/// - We only reverse row group read order, not rows within row groups
750-
/// - This provides approximate ordering that benefits limit pushdown
751-
///
752-
/// # Phase 2 (Future)
753-
/// Could return `Exact` when we can guarantee perfect ordering through techniques like:
754-
/// - File reordering based on statistics
755-
/// - Detecting already-sorted data
756-
/// This would allow removing the Sort operator entirely.
746+
/// # Behavior
747+
/// - Returns `Exact` when the file's natural ordering (from Parquet metadata) already
748+
/// satisfies the requested ordering. This allows the Sort operator to be eliminated
749+
/// if the files within each group are also non-overlapping (checked by FileScanConfig).
750+
/// - Returns `Inexact` when reversing the row group scan order would help satisfy the
751+
/// requested ordering. We still need a Sort operator at a higher level because:
752+
/// - We only reverse row group read order, not rows within row groups
753+
/// - This provides approximate ordering that benefits limit pushdown
757754
///
758755
/// # Returns
756+
/// - `Exact`: The file's natural ordering satisfies the request (within-file ordering guaranteed)
759757
/// - `Inexact`: Created an optimized source (e.g., reversed scan) that approximates the order
760758
/// - `Unsupported`: Cannot optimize for this ordering
761759
fn try_pushdown_sort(
@@ -767,6 +765,16 @@ impl FileSource for ParquetSource {
767765
return Ok(SortOrderPushdownResult::Unsupported);
768766
}
769767

768+
// Check if the natural (non-reversed) ordering already satisfies the request.
769+
// Parquet metadata guarantees within-file ordering, so if the ordering matches
770+
// we can return Exact. FileScanConfig will verify that files within each group
771+
// are non-overlapping before declaring the entire scan as Exact.
772+
if eq_properties.ordering_satisfy(order.iter().cloned())? {
773+
return Ok(SortOrderPushdownResult::Exact {
774+
inner: Arc::new(self.clone()) as Arc<dyn FileSource>,
775+
});
776+
}
777+
770778
// Build new equivalence properties with the reversed ordering.
771779
// This allows us to check if the reversed ordering satisfies the request
772780
// by leveraging:
@@ -811,11 +819,6 @@ impl FileSource for ParquetSource {
811819
Ok(SortOrderPushdownResult::Inexact {
812820
inner: Arc::new(new_source) as Arc<dyn FileSource>,
813821
})
814-
815-
// TODO Phase 2: Add support for other optimizations:
816-
// - File reordering based on min/max statistics
817-
// - Detection of exact ordering (return Exact to remove Sort operator)
818-
// - Partial sort pushdown for prefix matches
819822
}
820823

821824
fn apply_expressions(

0 commit comments

Comments
 (0)