Skip to content

Commit 390622a

Browse files
fix: validate sort pushdown through custom execution plans (#26118)
## Which issue does this PR close? Closes #26656. ## Rationale for this change Sort pushdown through a custom execution plan could return incorrectly ordered results or fail plan validation when the operator reordered or transformed columns. [`ExecutionPlan::maintains_input_order`](https://github.com/apache/datafusion/blob/6f3950c7c0698a88c1106f7fdc2a7d909d53aa7d/datafusion/physical-plan/src/execution_plan.rs#L241) describes row sequence. A custom projection computing `-a AS a` preserves that sequence but reverses value ordering. For input `[2, 1, 3]`, the sort could move below the custom projection and produce `[-1, -2, -3]`; keeping it above produces the requested ascending order, `[-3, -2, -1]`. Native [`ProjectionExec`](https://github.com/apache/datafusion/blob/6f3950c7c0698a88c1106f7fdc2a7d909d53aa7d/datafusion/physical-plan/src/projection.rs#L75) already has [specialized sort pushdown](https://github.com/apache/datafusion/blob/6f3950c7c0698a88c1106f7fdc2a7d909d53aa7d/datafusion/physical-optimizer/src/ensure_requirements/enforce_sorting/sort_pushdown.rs#L1334): it remaps column references and rejects pushdown when a required key comes from a computed expression. A custom projection can reach the generic fallback, which did not verify how sorting its inputs affects its output. ## What changes are included in this PR? The [generic fallback](https://github.com/apache/datafusion/blob/6f3950c7c0698a88c1106f7fdc2a7d909d53aa7d/datafusion/physical-optimizer/src/ensure_requirements/enforce_sorting/sort_pushdown.rs#L1080) builds temporary sorted inputs and checks the node's original input ordering requirements. It then rebuilds the node so it recomputes its properties from those inputs. Pushdown is accepted only if the rebuilt node's input requirements are satisfied and its output provides the requested ordering. These temporary plans are never executed. Safe pushdown and compatible-sort consolidation remain available without a new API or custom-node opt-in. The existing exclusions for filters, repartitions, and conflicting input orderings remain. <details> <summary>Custom sort pushdown checks</summary> These checks apply when the generic fallback proposes moving an ordering below a node. Some built-in nodes also use this path. Nodes already providing the requested ordering can use an earlier fast path if they can retain any parent limit. **1. Valid inputs** - **Column mapping:** propose remapped plain-column keys for inputs whose row order the node maintains. Every referenced column index must be valid in each input that would be sorted. - **Unbounded inputs:** an unbounded input must already satisfy its proposed ordering requirement. - **Input requirements:** temporary sorts preserve partitioning and must satisfy the original node's input ordering requirements before rebuilding. After rebuilding, check its input ordering, distribution, and co-partitioning (compatible partition layouts across inputs). **2. Correctly ordered output** - The rebuilt node's output properties must prove the ordering requested by its parent. **3. Row selection and limits** - **Parent limit:** if a parent limit is pending, decline pushdown unless the node supports limit pushdown and preserves row count. - **The node's own limit:** if the node reports a `fetch`, it must have exactly one child, which must be a [`SortExec`](https://github.com/apache/datafusion/blob/6f3950c7c0698a88c1106f7fdc2a7d909d53aa7d/datafusion/physical-plan/src/sorts/sort.rs#L1134). The proposed ordering must satisfy that child's complete original ordering, including hidden keys, without relying on its old ordering metadata. - **Limit placement:** forward only a safe parent limit. Do not reuse the node's own output `fetch` as an input bound: it may discard rows through an offset or filter. Respect the child's own TopK bound. A failed safety check declines pushdown; the caller keeps the necessary sort or limit above the node. Errors propagate. </details> ## What is the testing strategy for this PR? [SQL regressions](https://github.com/apache/datafusion/blob/6f3950c7c0698a88c1106f7fdc2a7d909d53aa7d/datafusion/sqllogictest/test_files/sort_pushdown.slt) check results and sort placement for transformed/reordered columns, filtered computed keys, native TopK refinement, hidden sort keys, and a custom offset with a limit. The [custom test wrapper](https://github.com/apache/datafusion/blob/6f3950c7c0698a88c1106f7fdc2a7d909d53aa7d/datafusion/sqllogictest/src/test_context/custom_sort_pushdown.rs) skips identity projections so computed-key tests reach the generic fallback. The test-only [`CustomLimitRule`](https://github.com/apache/datafusion/blob/6f3950c7c0698a88c1106f7fdc2a7d909d53aa7d/datafusion/sqllogictest/src/test_context/custom_sort_pushdown.rs#L134) replaces an unnecessary sort on the already ordered test input with a custom limit, so SQL `ORDER BY ... LIMIT` exercises the generic fallback. [Optimizer snapshots](https://github.com/apache/datafusion/blob/6f3950c7c0698a88c1106f7fdc2a7d909d53aa7d/datafusion/core/tests/physical_optimizer/enforce_sorting.rs) cover mandatory ordering conflicts, narrower child schemas, and unbounded inputs. Removing each of the schema-width, unbounded-input, and computed-key guards makes its regression test fail. ## Are there any user-facing changes? Affected custom execution plans retain required sorts and row limits while preserving safe sort refinements. No public API changes. Developed with AI assistance.
1 parent cadb6cd commit 390622a

7 files changed

Lines changed: 835 additions & 135 deletions

File tree

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

Lines changed: 63 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -13,7 +13,7 @@ use crate::physical_optimizer::test_utils::{
1313
parquet_exec_with_sort, projection_exec, repartition_exec, sort_exec,
1414
sort_exec_with_fetch, sort_expr, sort_expr_options, sort_merge_join_exec,
1515
sort_preserving_merge_exec, sort_preserving_merge_exec_with_fetch,
16-
spr_repartition_exec, stream_exec_ordered, union_exec,
16+
spr_repartition_exec, stream_exec, stream_exec_ordered, union_exec,
1717
};
1818

1919
use arrow::compute::{SortOptions};
@@ -2775,6 +2775,68 @@ async fn test_push_with_required_input_ordering_allowed() -> Result<()> {
27752775
Ok(())
27762776
}
27772777

2778+
#[tokio::test]
2779+
async fn test_push_with_required_input_ordering_conflicting_suffix() -> Result<()> {
2780+
let schema = create_test_schema3()?;
2781+
let required: LexOrdering = [sort_expr("a", &schema), sort_expr("b", &schema)].into();
2782+
let requested = [sort_expr("a", &schema), sort_expr("c", &schema)].into();
2783+
let input = sort_exec(required.clone(), memory_exec(&schema));
2784+
let plan = RequirementsTestExec::new(input)
2785+
.with_required_input_ordering(Some(required))
2786+
.into_arc();
2787+
let plan = sort_exec(requested, plan);
2788+
let test = EnforceSortingTest::new(plan).with_repartition_sorts(true);
2789+
2790+
assert_snapshot!(test.run(), @r"
2791+
Input / Optimized Plan:
2792+
SortExec: expr=[a@0 ASC, c@2 ASC], preserve_partitioning=[false]
2793+
RequiredInputOrderingExec
2794+
SortExec: expr=[a@0 ASC, b@1 ASC], preserve_partitioning=[false]
2795+
DataSourceExec: partitions=1, partition_sizes=[0]
2796+
");
2797+
Ok(())
2798+
}
2799+
2800+
#[test]
2801+
fn test_custom_sort_pushdown_keeps_sort_above_unbounded_input() -> Result<()> {
2802+
let schema = create_test_schema3()?;
2803+
// Keep the custom node directly below the sort. It bounds the stream
2804+
// without advertising a fetch, so this reaches the unbounded-input guard.
2805+
let custom = RequirementsTestExec::new(stream_exec(&schema))
2806+
.with_required_input_distribution(Distribution::SinglePartition)
2807+
.with_bounded_output()
2808+
.into_arc();
2809+
let plan = sort_exec([sort_expr("a", &schema)].into(), custom);
2810+
2811+
assert_snapshot!(EnforceSortingTest::new(plan).run(), @r"
2812+
Input / Optimized Plan:
2813+
SortExec: expr=[a@0 ASC], preserve_partitioning=[false]
2814+
RequiredInputOrderingExec
2815+
StreamingTableExec: partition_sizes=1, projection=[a, b, c, d, e], infinite_source=true
2816+
");
2817+
Ok(())
2818+
}
2819+
2820+
#[test]
2821+
fn test_custom_sort_pushdown_rejects_narrower_order_maintaining_input() -> Result<()> {
2822+
let schema = create_test_schema3()?;
2823+
let narrow_schema = Arc::new(schema.project(&[0])?);
2824+
// b@1 is valid in the first input and output, but not the second input.
2825+
let custom = RequirementsTestExec::new(memory_exec(&schema))
2826+
.with_additional_input(memory_exec(&narrow_schema))
2827+
.into_arc();
2828+
let plan = sort_exec([sort_expr("b", &schema)].into(), custom);
2829+
2830+
assert_snapshot!(EnforceSortingTest::new(plan).run(), @r"
2831+
Input / Optimized Plan:
2832+
SortExec: expr=[b@1 ASC], preserve_partitioning=[false]
2833+
RequiredInputOrderingExec
2834+
DataSourceExec: partitions=1, partition_sizes=[0]
2835+
DataSourceExec: partitions=1, partition_sizes=[0]
2836+
");
2837+
Ok(())
2838+
}
2839+
27782840
#[tokio::test]
27792841
async fn test_replace_with_partial_sort() -> Result<()> {
27802842
let schema = create_test_schema3()?;

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

Lines changed: 26 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -21,8 +21,10 @@ use datafusion_physical_expr::expressions;
2121
use datafusion_physical_expr_common::physical_expr::PhysicalExpr;
2222
use datafusion_physical_expr_common::sort_expr::LexOrdering;
2323
use datafusion_physical_optimizer::PhysicalOptimizerRule;
24+
use datafusion_physical_optimizer::ensure_requirements::EnsureRequirements;
2425
use datafusion_physical_optimizer::pushdown_sort::PushdownSort;
25-
use datafusion_physical_plan::collect;
26+
use datafusion_physical_plan::sorts::sort::SortExec;
27+
use datafusion_physical_plan::{ExecutionPlan, collect};
2628
use std::sync::Arc;
2729

2830
use crate::physical_optimizer::test_utils::{
@@ -1124,6 +1126,29 @@ fn test_sort_pushdown_exact_no_fetch_no_limit() {
11241126
);
11251127
}
11261128

1129+
#[test]
1130+
fn test_custom_plan_with_fetch_keeps_outer_sort() -> Result<()> {
1131+
let schema = schema();
1132+
let a = sort_expr("a", &schema);
1133+
let source = TestScan::new(schema.clone(), vec![[a.clone()].into()])
1134+
.with_supports_fetch(true)
1135+
.with_fetch(Some(10))
1136+
.unwrap();
1137+
let ordering = LexOrdering::new(vec![a, sort_expr("b", &schema)]).unwrap();
1138+
let plan = sort_exec(ordering.clone(), source);
1139+
1140+
let mut config = ConfigOptions::new();
1141+
config.execution.target_partitions = 1;
1142+
let optimized = EnsureRequirements::new().optimize(plan, &config)?;
1143+
let sort = optimized
1144+
.downcast_ref::<SortExec>()
1145+
.expect("a fetched custom plan must retain the requested outer sort");
1146+
assert_eq!(sort.expr(), &ordering);
1147+
assert!(sort.input().is::<TestScan>());
1148+
assert_eq!(sort.input().fetch(), Some(10));
1149+
Ok(())
1150+
}
1151+
11271152
#[test]
11281153
fn test_sort_pushdown_exact_preserves_fetch_with_global_limit() {
11291154
// When a source returns Exact but does NOT support with_fetch(),

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

Lines changed: 43 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -421,25 +421,44 @@ pub fn projection_exec(
421421
Ok(Arc::new(ProjectionExec::try_new(proj_exprs, input)?))
422422
}
423423

424-
/// A test [`ExecutionPlan`] whose requirements can be configured.
424+
/// A test [`ExecutionPlan`] with configurable input requirements.
425+
/// Its output properties follow its first input unless boundedness is overridden.
425426
#[derive(Debug)]
426427
pub struct RequirementsTestExec {
427428
required_input_ordering: Option<LexOrdering>,
428429
required_input_distribution: Distribution,
429430
maintains_input_order: bool,
430-
input: Arc<dyn ExecutionPlan>,
431+
inputs: Vec<Arc<dyn ExecutionPlan>>,
432+
bounded_output: bool,
433+
cache: Arc<PlanProperties>,
431434
}
432435

433436
impl RequirementsTestExec {
434437
pub fn new(input: Arc<dyn ExecutionPlan>) -> Self {
438+
let cache = Arc::clone(input.properties());
435439
Self {
436440
required_input_ordering: None,
437441
required_input_distribution: Distribution::UnspecifiedDistribution,
438442
maintains_input_order: true,
439-
input,
443+
inputs: vec![input],
444+
bounded_output: false,
445+
cache,
440446
}
441447
}
442448

449+
/// Add another input with the same requirements and order-preservation flag.
450+
pub fn with_additional_input(mut self, input: Arc<dyn ExecutionPlan>) -> Self {
451+
self.inputs.push(input);
452+
self
453+
}
454+
455+
/// Model a custom operator that stops reading an unbounded input.
456+
pub fn with_bounded_output(mut self) -> Self {
457+
self.bounded_output = true;
458+
Arc::make_mut(&mut self.cache).boundedness = Boundedness::Bounded;
459+
self
460+
}
461+
443462
/// sets the required input ordering
444463
pub fn with_required_input_ordering(
445464
mut self,
@@ -490,40 +509,48 @@ impl ExecutionPlan for RequirementsTestExec {
490509
}
491510

492511
fn properties(&self) -> &Arc<PlanProperties> {
493-
self.input.properties()
512+
&self.cache
494513
}
495514

496515
fn required_input_ordering(&self) -> Vec<Option<OrderingRequirements>> {
497516
vec![
498517
self.required_input_ordering
499518
.as_ref()
500-
.map(|ordering| OrderingRequirements::from(ordering.clone())),
519+
.map(|ordering| OrderingRequirements::from(ordering.clone()));
520+
self.inputs.len()
501521
]
502522
}
503523

504524
fn input_distribution_requirements(&self) -> InputDistributionRequirements {
505-
InputDistributionRequirements::new(vec![self.required_input_distribution.clone()])
525+
InputDistributionRequirements::new(vec![
526+
self.required_input_distribution.clone();
527+
self.inputs.len()
528+
])
506529
}
507530

508531
fn maintains_input_order(&self) -> Vec<bool> {
509-
vec![self.maintains_input_order]
532+
vec![self.maintains_input_order; self.inputs.len()]
510533
}
511534

512535
fn children(&self) -> Vec<&Arc<dyn ExecutionPlan>> {
513-
vec![&self.input]
536+
self.inputs.iter().collect()
514537
}
515538

516539
fn replace_children(
517540
self: Arc<Self>,
518541
children: Vec<Arc<dyn ExecutionPlan>>,
519542
_: ReplaceChildrenOptions,
520543
) -> Result<Arc<dyn ExecutionPlan>> {
521-
assert_eq!(children.len(), 1);
522-
Ok(RequirementsTestExec::new(Arc::clone(&children[0]))
544+
assert_eq!(children.len(), self.inputs.len());
545+
let mut plan = RequirementsTestExec::new(Arc::clone(&children[0]))
523546
.with_required_input_ordering(self.required_input_ordering.clone())
524547
.with_required_input_distribution(self.required_input_distribution.clone())
525-
.with_maintains_input_order(self.maintains_input_order)
526-
.into_arc())
548+
.with_maintains_input_order(self.maintains_input_order);
549+
plan.inputs.extend(children.into_iter().skip(1));
550+
if self.bounded_output {
551+
plan = plan.with_bounded_output();
552+
}
553+
Ok(plan.into_arc())
527554
}
528555

529556
fn with_new_children(
@@ -1061,6 +1088,10 @@ impl ExecutionPlan for TestScan {
10611088
Ok(Arc::new(Statistics::new_unknown(&self.schema)))
10621089
}
10631090

1091+
fn supports_limit_pushdown(&self) -> bool {
1092+
self.supports_fetch
1093+
}
1094+
10641095
fn with_fetch(&self, fetch: Option<usize>) -> Option<Arc<dyn ExecutionPlan>> {
10651096
if self.supports_fetch {
10661097
let mut new_scan = self.clone();

0 commit comments

Comments
 (0)