Skip to content

Commit 6f7d7a2

Browse files
fix: validate sort pushdown through custom execution plans
Rebuild custom plans with candidate sorted children and verify their input requirements and output ordering before accepting pushdown. Preserve safe pushdown through transparent nodes, and keep the outer sort for computed keys, fetched custom nodes, and unordered unbounded inputs. Cover transformed and reordered columns, filtered computed keys, and ordered row selection with SQL results and EXPLAIN regressions. Retain focused checks for compatible sorts and mandatory input requirements. Closes apache#26656. Developed with AI assistance. The validated fallback follows Jayzhan211's review suggestion.
1 parent 350ca76 commit 6f7d7a2

7 files changed

Lines changed: 536 additions & 61 deletions

File tree

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

Lines changed: 22 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -2604,7 +2604,6 @@ async fn test_push_with_required_input_ordering_prohibited() -> Result<()> {
26042604
Ok(())
26052605
}
26062606

2607-
// test when the required input ordering is satisfied so could push through
26082607
#[tokio::test]
26092608
async fn test_push_with_required_input_ordering_allowed() -> Result<()> {
26102609
let schema = create_test_schema3()?;
@@ -2618,14 +2617,6 @@ async fn test_push_with_required_input_ordering_allowed() -> Result<()> {
26182617
.into_arc();
26192618
let plan = sort_exec(ordering_ab, plan);
26202619

2621-
/*
2622-
let expected_input = [
2623-
"SortExec: expr=[a@0 ASC, b@1 ASC], preserve_partitioning=[false]", // <-- can push this down (as it is compatible with the required input ordering)
2624-
" RequiredInputOrderingExec", // <-- this requires input sorted by a, and preserves the input order
2625-
" SortExec: expr=[a@0 ASC], preserve_partitioning=[false]",
2626-
" DataSourceExec: partitions=1, partition_sizes=[0]",
2627-
];
2628-
*/
26292620
let test = EnforceSortingTest::new(plan.clone()).with_repartition_sorts(true);
26302621

26312622
assert_snapshot!(test.run(), @r"
@@ -2640,7 +2631,28 @@ async fn test_push_with_required_input_ordering_allowed() -> Result<()> {
26402631
SortExec: expr=[a@0 ASC, b@1 ASC], preserve_partitioning=[false]
26412632
DataSourceExec: partitions=1, partition_sizes=[0]
26422633
");
2643-
// Should be able to push down
2634+
Ok(())
2635+
}
2636+
2637+
#[tokio::test]
2638+
async fn test_push_with_required_input_ordering_conflicting_suffix() -> Result<()> {
2639+
let schema = create_test_schema3()?;
2640+
let required: LexOrdering = [sort_expr("a", &schema), sort_expr("b", &schema)].into();
2641+
let requested = [sort_expr("a", &schema), sort_expr("c", &schema)].into();
2642+
let input = sort_exec(required.clone(), memory_exec(&schema));
2643+
let plan = RequirementsTestExec::new(input)
2644+
.with_required_input_ordering(Some(required))
2645+
.into_arc();
2646+
let plan = sort_exec(requested, plan);
2647+
let test = EnforceSortingTest::new(plan).with_repartition_sorts(true);
2648+
2649+
assert_snapshot!(test.run(), @r"
2650+
Input / Optimized Plan:
2651+
SortExec: expr=[a@0 ASC, c@2 ASC], preserve_partitioning=[false]
2652+
RequiredInputOrderingExec
2653+
SortExec: expr=[a@0 ASC, b@1 ASC], preserve_partitioning=[false]
2654+
DataSourceExec: partitions=1, partition_sizes=[0]
2655+
");
26442656
Ok(())
26452657
}
26462658

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

Lines changed: 26 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -34,8 +34,10 @@ use datafusion_physical_expr::expressions;
3434
use datafusion_physical_expr_common::physical_expr::PhysicalExpr;
3535
use datafusion_physical_expr_common::sort_expr::LexOrdering;
3636
use datafusion_physical_optimizer::PhysicalOptimizerRule;
37+
use datafusion_physical_optimizer::ensure_requirements::EnsureRequirements;
3738
use datafusion_physical_optimizer::pushdown_sort::PushdownSort;
38-
use datafusion_physical_plan::collect;
39+
use datafusion_physical_plan::sorts::sort::SortExec;
40+
use datafusion_physical_plan::{ExecutionPlan, collect};
3941
use std::sync::Arc;
4042

4143
use crate::physical_optimizer::test_utils::{
@@ -1137,6 +1139,29 @@ fn test_sort_pushdown_exact_no_fetch_no_limit() {
11371139
);
11381140
}
11391141

1142+
#[test]
1143+
fn test_custom_plan_with_fetch_keeps_outer_sort() -> Result<()> {
1144+
let schema = schema();
1145+
let a = sort_expr("a", &schema);
1146+
let source = TestScan::new(schema.clone(), vec![[a.clone()].into()])
1147+
.with_supports_fetch(true)
1148+
.with_fetch(Some(10))
1149+
.unwrap();
1150+
let ordering = LexOrdering::new(vec![a, sort_expr("b", &schema)]).unwrap();
1151+
let plan = sort_exec(ordering.clone(), source);
1152+
1153+
let mut config = ConfigOptions::new();
1154+
config.execution.target_partitions = 1;
1155+
let optimized = EnsureRequirements::new().optimize(plan, &config)?;
1156+
let sort = optimized
1157+
.downcast_ref::<SortExec>()
1158+
.expect("a fetched custom plan must retain the requested outer sort");
1159+
assert_eq!(sort.expr(), &ordering);
1160+
assert!(sort.input().is::<TestScan>());
1161+
assert_eq!(sort.input().fetch(), Some(10));
1162+
Ok(())
1163+
}
1164+
11401165
#[test]
11411166
fn test_sort_pushdown_exact_preserves_fetch_with_global_limit() {
11421167
// When a source returns Exact but does NOT support with_fetch(),

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

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1074,6 +1074,10 @@ impl ExecutionPlan for TestScan {
10741074
Ok(Arc::new(Statistics::new_unknown(&self.schema)))
10751075
}
10761076

1077+
fn supports_limit_pushdown(&self) -> bool {
1078+
self.supports_fetch
1079+
}
1080+
10771081
fn with_fetch(&self, fetch: Option<usize>) -> Option<Arc<dyn ExecutionPlan>> {
10781082
if self.supports_fetch {
10791083
let mut new_scan = self.clone();

‎datafusion/physical-optimizer/src/ensure_requirements/enforce_sorting/sort_pushdown.rs‎

Lines changed: 145 additions & 49 deletions
Original file line numberDiff line numberDiff line change
@@ -49,7 +49,10 @@ use datafusion_physical_plan::repartition::RepartitionExec;
4949
use datafusion_physical_plan::sorts::sort::SortExec;
5050
use datafusion_physical_plan::sorts::sort_preserving_merge::SortPreservingMergeExec;
5151
use datafusion_physical_plan::tree_node::PlanContext;
52-
use datafusion_physical_plan::{ExecutionPlan, ExecutionPlanProperties};
52+
use datafusion_physical_plan::{
53+
ChildSatisfactionOptions, ChildrenPropertiesMode, ExecutionPlan,
54+
ExecutionPlanProperties, ReplaceChildrenOptions,
55+
};
5356

5457
/// "Data class" used by sort pushdown (now driven from `EnsureRequirements`)
5558
/// to push down [`SortExec`] in the plan. In some cases the total
@@ -548,49 +551,18 @@ fn pushdown_requirement_to_children(
548551
} else {
549552
Ok(None)
550553
}
551-
} else if plan.fetch().is_some()
552-
&& plan.supports_limit_pushdown()
553-
&& plan
554-
.maintains_input_order()
555-
.into_iter()
556-
.all(|maintain| maintain)
557-
{
558-
// Push down through operator with fetch when:
559-
// - requirement is aligned with output ordering
560-
// - it preserves ordering during execution
561-
//
562-
// A `ProjectionExec` reports a `fetch()` forwarded from its input and
563-
// can renumber/reorder columns, so the requirement (expressed in the
564-
// projection's output schema) must be remapped into the child schema
565-
// before being pushed down — forwarding it unchanged would let a key
566-
// such as `score@1` (valid in the output schema) refer to a different
567-
// column in the child schema, producing a `SortExec` whose key points
568-
// at the wrong column ("does not satisfy order requirements ...
569-
// Child-0 order: []"). If a required column maps to a computed
570-
// (non-`Column`) projection expression it cannot be expressed below the
571-
// projection, so the sort is kept above it.
572-
let child_required =
573-
if let Some(projection) = plan.downcast_ref::<ProjectionExec>() {
574-
match remap_requirement_through_projection(projection, &parent_required) {
575-
Some(remapped) => remapped,
576-
None => return Ok(None),
577-
}
578-
} else {
579-
parent_required.clone()
580-
};
581-
582-
// Pushing a sort below an unordered fetch changes which rows it keeps.
583-
let Some(ordering) = plan.properties().output_ordering() else {
554+
} else if plan.is::<SortPreservingMergeExec>() && plan.fetch().is_some() {
555+
// Refining a fetched merge must preserve the ordering that selected its rows.
556+
let Some(ordering) = plan.output_ordering() else {
584557
return Ok(None);
585558
};
586-
if plan.properties().eq_properties.requirements_compatible(
587-
parent_required.first().clone(),
588-
ordering.clone().into(),
589-
) {
590-
Ok(Some(vec![Some(child_required)]))
591-
} else {
592-
Ok(None)
593-
}
559+
Ok(plan
560+
.equivalence_properties()
561+
.requirements_compatible(
562+
parent_required.first().clone(),
563+
ordering.clone().into(),
564+
)
565+
.then(|| vec![Some(parent_required)]))
594566
} else if is_union(plan) {
595567
// `UnionExec` does not have real sort requirements for its input, we
596568
// just propagate the sort requirements down:
@@ -635,14 +607,11 @@ fn pushdown_requirement_to_children(
635607
} else if let Some(projection_exec) = plan.downcast_ref::<ProjectionExec>() {
636608
handle_projection_pushdown(projection_exec, &parent_required)
637609
} else if maintains_input_order.is_empty()
638-
|| !maintains_input_order.iter().any(|o| *o)
610+
|| !maintains_input_order.iter().any(|maintains| *maintains)
639611
|| plan.is::<RepartitionExec>()
640612
|| plan.is::<FilterExec>()
641613
|| pushdown_would_violate_requirements(&parent_required, plan.as_ref())
642614
{
643-
// If the current plan is a leaf node or can not maintain any of the input ordering, can not pushed down requirements.
644-
// For RepartitionExec, we always choose to not push down the sort requirements even the RepartitionExec(input_partition=1) could maintain input ordering.
645-
// Pushing down is not beneficial
646615
Ok(None)
647616
} else if is_sort_preserving_merge(plan) {
648617
let new_ordering = LexOrdering::from(parent_required.first().clone());
@@ -1000,14 +969,22 @@ fn handle_custom_pushdown(
1000969
) -> Result<Option<Vec<Option<OrderingRequirements>>>> {
1001970
let plan_children = plan.children();
1002971

1003-
// If the plan has no children, return early:
1004-
if plan_children.is_empty() {
972+
// A fetched custom node already selects rows; reordering its input can
973+
// change that selection. Native limit and merge cases are handled earlier.
974+
if plan_children.is_empty() || plan.fetch().is_some() {
1005975
return Ok(None);
1006976
}
1007977

1008978
// Collect all unique column indices used in the parent-required sorting
1009979
// expression:
1010980
let requirement = parent_required.into_single();
981+
// Evaluating a computed key earlier can fail on rows this node would discard.
982+
if requirement
983+
.iter()
984+
.any(|sort| sort.expr.downcast_ref::<Column>().is_none())
985+
{
986+
return Ok(None);
987+
}
1011988
let all_indices: HashSet<usize> = requirement
1012989
.iter()
1013990
.flat_map(|order| {
@@ -1051,6 +1028,7 @@ fn handle_custom_pushdown(
10511028
// Transform the parent-required expression for the child schema by
10521029
// adjusting columns:
10531030
let updated_parent_req = requirement
1031+
.clone()
10541032
.into_iter()
10551033
.map(|req| {
10561034
let child_schema = plan_children[maintained_child_idx].schema();
@@ -1073,7 +1051,7 @@ fn handle_custom_pushdown(
10731051
.collect::<Result<Vec<_>>>()?;
10741052

10751053
// Prepare the result, populating with the updated requirements for children that maintain order
1076-
let result = maintains_input_order
1054+
let result: Vec<_> = maintains_input_order
10771055
.iter()
10781056
.map(|&maintains_order| {
10791057
if maintains_order {
@@ -1085,12 +1063,101 @@ fn handle_custom_pushdown(
10851063
})
10861064
.collect();
10871065

1066+
// Test the proposed child orderings without moving the real sorts yet.
1067+
let mut probe_children = Vec::with_capacity(plan_children.len());
1068+
for (child, required) in plan_children.iter().zip(&result) {
1069+
let child = if let Some(required) = required {
1070+
// Other order-maintaining inputs may have narrower schemas.
1071+
if required.first().iter().any(|sort| {
1072+
collect_columns(&sort.expr)
1073+
.iter()
1074+
.any(|column| column.index() >= child.schema().fields().len())
1075+
}) {
1076+
return Ok(None);
1077+
}
1078+
// A bounded operator can stop an unbounded input; a new blocking
1079+
// sort below it cannot. An already ordered input needs no new sort.
1080+
if child.boundedness().is_unbounded()
1081+
&& !child
1082+
.equivalence_properties()
1083+
.ordering_satisfy_requirement(required.first().clone())?
1084+
{
1085+
return Ok(None);
1086+
}
1087+
Arc::new(
1088+
SortExec::new(required.first().clone().into(), Arc::clone(child))
1089+
.with_preserve_partitioning(true),
1090+
) as Arc<dyn ExecutionPlan>
1091+
} else {
1092+
Arc::clone(child)
1093+
};
1094+
probe_children.push(child);
1095+
}
1096+
let children = probe_children
1097+
.iter()
1098+
.map(|child| child.as_ref())
1099+
.collect::<Vec<_>>();
1100+
if !sort_pushdown_inputs_satisfied(plan.as_ref(), &children)? {
1101+
return Ok(None);
1102+
}
1103+
let probe = Arc::clone(plan).replace_children(
1104+
probe_children,
1105+
ReplaceChildrenOptions::new(ChildrenPropertiesMode::Recompute),
1106+
)?;
1107+
let children = probe
1108+
.children()
1109+
.into_iter()
1110+
.map(|child| child.as_ref())
1111+
.collect::<Vec<_>>();
1112+
if !sort_pushdown_inputs_satisfied(probe.as_ref(), &children)?
1113+
|| !probe
1114+
.equivalence_properties()
1115+
.ordering_satisfy_requirement(requirement)?
1116+
{
1117+
return Ok(None);
1118+
}
10881119
Ok(Some(result))
10891120
} else {
10901121
Ok(None)
10911122
}
10921123
}
10931124

1125+
/// A sort probe must satisfy the node's input requirements as well as its output order.
1126+
fn sort_pushdown_inputs_satisfied(
1127+
plan: &dyn ExecutionPlan,
1128+
children: &[&dyn ExecutionPlan],
1129+
) -> Result<bool> {
1130+
let ordering = plan.required_input_ordering();
1131+
let distribution = plan.input_distribution_requirements();
1132+
if ordering.len() != children.len()
1133+
|| distribution.per_child_distributions().len() != children.len()
1134+
{
1135+
return Ok(false);
1136+
}
1137+
for (index, (child, required)) in children.iter().zip(ordering).enumerate() {
1138+
if let Some(required) = required
1139+
&& !child
1140+
.equivalence_properties()
1141+
.ordering_satisfy_requirement(required.first().clone())?
1142+
{
1143+
return Ok(false);
1144+
}
1145+
if !distribution
1146+
.child_satisfaction(
1147+
index,
1148+
*child,
1149+
ChildSatisfactionOptions::new().with_allow_subset(true),
1150+
)?
1151+
.is_satisfied()
1152+
{
1153+
return Ok(false);
1154+
}
1155+
}
1156+
Ok(distribution
1157+
.unsatisfied_co_partitioned_children(plan.name(), children)?
1158+
.is_empty())
1159+
}
1160+
10941161
// For hash join we only maintain the input order for the right child
10951162
// for join type: Inner, Right, RightSemi, RightAnti, RightMark
10961163
fn handle_hash_join(
@@ -1247,10 +1314,16 @@ mod tests {
12471314
use arrow::compute::SortOptions;
12481315
use arrow::datatypes::{DataType, Field, Schema};
12491316
use datafusion_expr::Operator;
1317+
use datafusion_expr::physical_planning_context::{
1318+
ScalarSubqueryResults, SubqueryIndex,
1319+
};
12501320
use datafusion_physical_expr::PhysicalExpr;
12511321
use datafusion_physical_expr::expressions::{BinaryExpr, col};
12521322
use datafusion_physical_plan::empty::EmptyExec;
12531323
use datafusion_physical_plan::limit::GlobalLimitExec;
1324+
use datafusion_physical_plan::scalar_subquery::{
1325+
ScalarSubqueryExec, ScalarSubqueryLink,
1326+
};
12541327

12551328
const DESC: SortOptions = SortOptions {
12561329
descending: true,
@@ -1366,6 +1439,29 @@ mod tests {
13661439
LexRequirement::new(reqs).unwrap()
13671440
}
13681441

1442+
#[test]
1443+
fn scalar_subquery_sort_applies_only_to_the_main_input() -> Result<()> {
1444+
let schema = child_schema();
1445+
let input: Arc<dyn ExecutionPlan> = Arc::new(EmptyExec::new(Arc::clone(&schema)));
1446+
let requirement = OrderingRequirements::new(lex([
1447+
req("c", &schema, DESC),
1448+
req("a", &schema, ASC),
1449+
]));
1450+
let plan: Arc<dyn ExecutionPlan> = Arc::new(ScalarSubqueryExec::new(
1451+
Arc::clone(&input),
1452+
vec![ScalarSubqueryLink {
1453+
plan: Arc::clone(&input),
1454+
index: SubqueryIndex::new(0),
1455+
}],
1456+
ScalarSubqueryResults::new(1),
1457+
));
1458+
assert_eq!(
1459+
pushdown_requirement_to_children(&plan, requirement.clone(), None)?,
1460+
Some(vec![Some(requirement), None])
1461+
);
1462+
Ok(())
1463+
}
1464+
13691465
#[test]
13701466
fn remap_single_hard_requirement_through_reordering_projection() {
13711467
let projection = reordering_projection();

0 commit comments

Comments
 (0)