Skip to content

Commit 86c2b24

Browse files
fix: preserve required sorts above custom execution plans
Rebuild custom plans with candidate sorted children and require their output properties to satisfy the original ordering before accepting pushdown. Keep the outer sort when the candidate cannot be validated. Reproduce the bug with a fixed custom projection that negates one column. Check ordered SQL results and use EXPLAIN to assert the retained outer sort. Retain a focused unit test for safe pushdown through renamed columns. Closes apache#26656.
1 parent 2717e25 commit 86c2b24

4 files changed

Lines changed: 282 additions & 25 deletions

File tree

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

Lines changed: 105 additions & 25 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+
ChildrenPropertiesMode, ExecutionPlan, ExecutionPlanProperties,
54+
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
@@ -979,20 +982,16 @@ fn expr_source_side(
979982
}
980983
}
981984

982-
/// Handles the custom pushdown of parent-required sorting requirements down to
983-
/// the child execution plans, considering whether the input order is maintained.
984-
///
985-
/// # Arguments
986-
///
987-
/// * `plan` - A reference to an `ExecutionPlan` for which the pushdown will be applied.
988-
/// * `parent_required` - The sorting requirements expected by the parent node.
989-
/// * `maintains_input_order` - A vector of booleans indicating whether each child
990-
/// maintains the input order.
985+
/// Attempts sort pushdown through an operator without a specialized handler.
991986
///
992-
/// # Returns
987+
/// First, map the requested output sort columns to a child's columns by position,
988+
/// when the operator preserves that child's row positions. This is only a
989+
/// proposed mapping: the operator may change column positions or values.
993990
///
994-
/// Returns `Ok(Some(Vec<Option<LexRequirement>>))` if the sorting requirements can be
995-
/// pushed down, `Ok(None)` if not. On error, returns a `Result::Err`.
991+
/// Then, rebuild the operator with the proposed sorted children and check its
992+
/// output ordering. Return child requirements only if the rebuilt operator
993+
/// satisfies the original output requirement; otherwise return `None` to keep
994+
/// the sort above the node.
996995
fn handle_custom_pushdown(
997996
plan: &Arc<dyn ExecutionPlan>,
998997
parent_required: OrderingRequirements,
@@ -1007,8 +1006,8 @@ fn handle_custom_pushdown(
10071006

10081007
// Collect all unique column indices used in the parent-required sorting
10091008
// expression:
1010-
let requirement = parent_required.into_single();
1011-
let all_indices: HashSet<usize> = requirement
1009+
let output_requirement = parent_required.into_single();
1010+
let all_indices: HashSet<usize> = output_requirement
10121011
.iter()
10131012
.flat_map(|order| {
10141013
collect_columns(&order.expr)
@@ -1050,12 +1049,11 @@ fn handle_custom_pushdown(
10501049
.sum::<usize>();
10511050
// Transform the parent-required expression for the child schema by
10521051
// adjusting columns:
1053-
let updated_parent_req = requirement
1054-
.into_iter()
1052+
let child_requirement = output_requirement
1053+
.iter()
10551054
.map(|req| {
10561055
let child_schema = plan_children[maintained_child_idx].schema();
1057-
let updated_columns = req
1058-
.expr
1056+
let updated_columns = Arc::clone(&req.expr)
10591057
.transform_up(|expr| {
10601058
if let Some(col) = expr.downcast_ref::<Column>() {
10611059
let new_index = col.index() - sub_offset;
@@ -1070,22 +1068,74 @@ fn handle_custom_pushdown(
10701068
.data;
10711069
Ok(PhysicalSortRequirement::new(updated_columns, req.options))
10721070
})
1073-
.collect::<Result<Vec<_>>>()?;
1071+
.collect::<Result<Vec<_>>>();
1072+
let Ok(child_requirement) = child_requirement else {
1073+
return Ok(None);
1074+
};
10741075

1075-
// Prepare the result, populating with the updated requirements for children that maintain order
1076-
let result = maintains_input_order
1076+
// Apply the proposed ordering to each child that preserves row positions.
1077+
let child_requirements = maintains_input_order
10771078
.iter()
10781079
.map(|&maintains_order| {
10791080
if maintains_order {
1080-
LexRequirement::new(updated_parent_req.clone())
1081+
LexRequirement::new(child_requirement.clone())
10811082
.map(OrderingRequirements::new)
10821083
} else {
10831084
None
10841085
}
10851086
})
1086-
.collect();
1087+
.collect::<Vec<_>>();
1088+
1089+
// Build a trial plan with sorted inputs. Replacing its children lets the
1090+
// custom operator recompute its output ordering through the existing API.
1091+
// This checks plan metadata during optimization.
1092+
let mut sorted_children = Vec::with_capacity(plan_children.len());
1093+
for (child, required) in plan_children.into_iter().zip(&child_requirements) {
1094+
let sorted: Arc<dyn ExecutionPlan> = if let Some(required) = required {
1095+
let ordering = LexOrdering::from(required.first().clone());
1096+
let schema = child.schema();
1097+
// Positional mapping can produce incompatible types, or invalid
1098+
// indices in another order-preserving child. Validate before
1099+
// SortExec::new, which panics if computing its properties fails.
1100+
if ordering.iter().any(|sort| {
1101+
collect_columns(&sort.expr)
1102+
.iter()
1103+
.any(|column| column.index() >= schema.fields().len())
1104+
|| sort.expr.data_type(&schema).is_err()
1105+
}) {
1106+
return Ok(None);
1107+
}
1108+
if child
1109+
.equivalence_properties()
1110+
.extract_common_sort_prefix(ordering.clone())
1111+
.is_err()
1112+
{
1113+
return Ok(None);
1114+
}
1115+
Arc::new(
1116+
SortExec::new(ordering, Arc::clone(child))
1117+
.with_preserve_partitioning(true),
1118+
)
1119+
} else {
1120+
Arc::clone(child)
1121+
};
1122+
sorted_children.push(sorted);
1123+
}
1124+
let Ok(candidate_plan) = Arc::clone(plan).replace_children(
1125+
sorted_children,
1126+
ReplaceChildrenOptions::new(ChildrenPropertiesMode::Recompute),
1127+
) else {
1128+
return Ok(None);
1129+
};
1130+
if !candidate_plan
1131+
.equivalence_properties()
1132+
.ordering_satisfy_requirement(output_requirement)
1133+
.unwrap_or(false)
1134+
{
1135+
return Ok(None);
1136+
}
10871137

1088-
Ok(Some(result))
1138+
Ok(Some(child_requirements))
10891139
} else {
10901140
Ok(None)
10911141
}
@@ -1366,6 +1416,36 @@ mod tests {
13661416
LexRequirement::new(reqs).unwrap()
13671417
}
13681418

1419+
// Exercise the custom-operator fallback directly with ProjectionExec's
1420+
// property derivation. The SQL tests cover dispatch through a custom plan.
1421+
#[test]
1422+
fn custom_pushdown_accepts_renamed_columns() -> Result<()> {
1423+
let child = child_schema();
1424+
let input = Arc::new(EmptyExec::new(Arc::clone(&child)));
1425+
let plan: Arc<dyn ExecutionPlan> = Arc::new(ProjectionExec::try_new(
1426+
[
1427+
(col("a", &child)?, "first".to_string()),
1428+
(col("b", &child)?, "second".to_string()),
1429+
],
1430+
input,
1431+
)?);
1432+
let output = plan.schema();
1433+
let required = OrderingRequirements::new(lex([
1434+
req("first", &output, ASC),
1435+
req("second", &output, DESC),
1436+
]));
1437+
let expected = OrderingRequirements::new(lex([
1438+
req("a", &child, ASC),
1439+
req("b", &child, DESC),
1440+
]));
1441+
1442+
assert_eq!(
1443+
handle_custom_pushdown(&plan, required, &[true])?,
1444+
Some(vec![Some(expected)])
1445+
);
1446+
Ok(())
1447+
}
1448+
13691449
#[test]
13701450
fn remap_single_hard_requirement_through_reordering_projection() {
13711451
let projection = reordering_projection();

‎datafusion/sqllogictest/src/test_context.rs‎

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -73,6 +73,7 @@ use log::info;
7373
use sqlparser::ast;
7474
use tempfile::TempDir;
7575

76+
mod custom_sort_pushdown;
7677
mod range_partitioning;
7778

7879
/// Context for running tests
@@ -182,6 +183,12 @@ impl TestContext {
182183

183184
let file_name = relative_path.file_name().unwrap().to_str().unwrap();
184185
match file_name {
186+
"sort_pushdown.slt" => {
187+
custom_sort_pushdown::register_custom_sort_pushdown(
188+
test_ctx.session_ctx(),
189+
)
190+
.expect("register custom projection table");
191+
}
185192
"parquet_missing_bounds.slt" => {
186193
register_parquet_missing_bounds(&mut test_ctx).await;
187194
}
Lines changed: 139 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,139 @@
1+
// Licensed to the Apache Software Foundation (ASF) under one
2+
// or more contributor license agreements. See the NOTICE file
3+
// distributed with this work for additional information
4+
// regarding copyright ownership. The ASF licenses this file
5+
// to you under the Apache License, Version 2.0 (the
6+
// "License"); you may not use this file except in compliance
7+
// with the License. You may obtain a copy of the License at
8+
//
9+
// http://www.apache.org/licenses/LICENSE-2.0
10+
//
11+
// Unless required by applicable law or agreed to in writing,
12+
// software distributed under the License is distributed on an
13+
// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14+
// KIND, either express or implied. See the License for the
15+
// specific language governing permissions and limitations
16+
// under the License.
17+
18+
use std::fmt::{self, Formatter};
19+
use std::sync::Arc;
20+
21+
use arrow::array::record_batch;
22+
use arrow::datatypes::{self as arrow_schema, SchemaRef};
23+
use async_trait::async_trait;
24+
use datafusion::catalog::{Session, TableProvider};
25+
use datafusion::common::Result;
26+
use datafusion::common::tree_node::TreeNodeRecursion;
27+
use datafusion::execution::{SendableRecordBatchStream, TaskContext};
28+
use datafusion::logical_expr::{Expr, TableType};
29+
use datafusion::physical_expr::PhysicalExpr;
30+
use datafusion::physical_expr::expressions::{col, negative};
31+
use datafusion::physical_expr::projection::ProjectionExprs;
32+
use datafusion::physical_plan::projection::ProjectionExec;
33+
use datafusion::physical_plan::test::TestMemoryExec;
34+
use datafusion::physical_plan::{
35+
DisplayAs, DisplayFormatType, ExecutionPlan, PlanProperties,
36+
};
37+
use datafusion::prelude::SessionContext;
38+
39+
/// Register a fixed custom operator that negates its input column.
40+
pub(super) fn register_custom_sort_pushdown(ctx: &SessionContext) -> Result<()> {
41+
let batch = record_batch!(("a", Int32, [2, 1, 3]))?;
42+
let schema = batch.schema();
43+
let input = TestMemoryExec::try_new_exec(&[vec![batch]], Arc::clone(&schema), None)?;
44+
let projection = ProjectionExec::try_new(
45+
[(negative(col("a", &schema)?, &schema)?, "a".to_string())],
46+
input,
47+
)?;
48+
ctx.register_table(
49+
"custom_negated_projection",
50+
Arc::new(CustomProjection(projection)),
51+
)?;
52+
Ok(())
53+
}
54+
55+
/// Negates values while preserving row positions. Keeping a distinct plan type
56+
/// exercises the generic custom-plan sort pushdown path.
57+
#[derive(Debug, Clone)]
58+
struct CustomProjection(ProjectionExec);
59+
60+
#[async_trait]
61+
impl TableProvider for CustomProjection {
62+
fn schema(&self) -> SchemaRef {
63+
self.0.schema()
64+
}
65+
66+
fn table_type(&self) -> TableType {
67+
TableType::Base
68+
}
69+
70+
async fn scan(
71+
&self,
72+
_: &dyn Session,
73+
projection: Option<&[usize]>,
74+
_: &[Expr],
75+
_: Option<usize>,
76+
) -> Result<Arc<dyn ExecutionPlan>> {
77+
let plan: Arc<dyn ExecutionPlan> = Arc::new(self.clone());
78+
if let Some(projection) = projection {
79+
let expressions = ProjectionExprs::from_indices(projection, &self.0.schema());
80+
Ok(Arc::new(ProjectionExec::try_new(
81+
expressions.iter().cloned(),
82+
plan,
83+
)?))
84+
} else {
85+
Ok(plan)
86+
}
87+
}
88+
}
89+
90+
impl DisplayAs for CustomProjection {
91+
fn fmt_as(&self, display_type: DisplayFormatType, f: &mut Formatter) -> fmt::Result {
92+
write!(f, "Custom")?;
93+
self.0.fmt_as(display_type, f)
94+
}
95+
}
96+
97+
impl ExecutionPlan for CustomProjection {
98+
fn name(&self) -> &str {
99+
"CustomProjectionExec"
100+
}
101+
102+
fn properties(&self) -> &Arc<PlanProperties> {
103+
self.0.properties()
104+
}
105+
106+
fn children(&self) -> Vec<&Arc<dyn ExecutionPlan>> {
107+
self.0.children()
108+
}
109+
110+
// Row positions are preserved; projected values have the opposite ordering.
111+
fn maintains_input_order(&self) -> Vec<bool> {
112+
self.0.maintains_input_order()
113+
}
114+
115+
fn with_new_children(
116+
self: Arc<Self>,
117+
children: Vec<Arc<dyn ExecutionPlan>>,
118+
) -> Result<Arc<dyn ExecutionPlan>> {
119+
Ok(Arc::new(Self(ProjectionExec::try_new(
120+
self.0.expr().to_vec(),
121+
Arc::clone(&children[0]),
122+
)?)))
123+
}
124+
125+
fn apply_expressions(
126+
&self,
127+
f: &mut dyn FnMut(&Arc<dyn PhysicalExpr>) -> Result<TreeNodeRecursion>,
128+
) -> Result<TreeNodeRecursion> {
129+
self.0.apply_expressions(f)
130+
}
131+
132+
fn execute(
133+
&self,
134+
partition: usize,
135+
context: Arc<TaskContext>,
136+
) -> Result<SendableRecordBatchStream> {
137+
self.0.execute(partition, context)
138+
}
139+
}

‎datafusion/sqllogictest/test_files/sort_pushdown.slt‎

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

18+
# The custom operator evaluates -a AS a, preserving row positions while
19+
# reversing the ordering of values. Its input is [2, 1, 3].
20+
statement ok
21+
SET datafusion.execution.target_partitions = 1;
22+
23+
query I
24+
SELECT a FROM custom_negated_projection ORDER BY a;
25+
----
26+
-3
27+
-2
28+
-1
29+
30+
# The sort must stay above the custom projection.
31+
statement ok
32+
SET datafusion.explain.physical_plan_only = true;
33+
34+
query TT
35+
EXPLAIN SELECT a FROM custom_negated_projection ORDER BY a;
36+
----
37+
physical_plan
38+
01)SortExec: expr=[a@0 ASC NULLS LAST], preserve_partitioning=[false]
39+
02)--CustomProjectionExec: expr=[(- a@0) as a]
40+
03)----CooperativeExec
41+
04)------DataSourceExec: partitions=1, partition_sizes=[1]
42+
43+
statement ok
44+
SET datafusion.explain.physical_plan_only = false;
45+
46+
statement ok
47+
SET datafusion.execution.target_partitions = 4;
48+
1849
#Sort Pushdown for ordered Parquet files
1950
statement ok
2051
SET datafusion.execution.parquet.pushdown_filters = true;

0 commit comments

Comments
 (0)