Skip to content

Commit 99e723d

Browse files
fix: retain only valid orderings after order-preserving repartition (#26747)
## Which issue does this PR close? Closes #26745. Closes #26036. ## Rationale for this change An order-preserving repartition can incorrectly retain independent input orderings that do not hold after merging partitions. This lets the planner remove a necessary sort, causing `ORDER BY` to return rows in the wrong order. ## What changes are included in this PR? - Retain only the merge key ordering when repartitioning merges multiple input partitions. - Preserve projected cast relationships so valid cast-derived orderings can still be inferred after the merge. - Extend ordering checks to use equivalent expressions without assuming that equality implies a strictly order-preserving transformation. - Update affected expected plans. ## What is the testing strategy for this PR? - Add the issue’s reproduction to `order.slt`, verifying exact row order. - Add safety cases in `equivalence_properties.slt` and `monotonic_projection_test.slt`. - Verify the existing unbounded-stream cast-ordering test continues to pass. ## Are there any user-facing changes? Only that queries affected by #26745 now return rows in the requested order.
1 parent ce0e829 commit 99e723d

10 files changed

Lines changed: 250 additions & 24 deletions

File tree

‎datafusion/physical-expr/src/equivalence/class.rs‎

Lines changed: 28 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -9,15 +9,17 @@ use std::sync::Arc;
99
use std::vec::IntoIter;
1010

1111
use super::ProjectionMapping;
12-
use crate::expressions::Literal;
12+
use crate::expressions::{Column, Literal};
1313
use crate::physical_expr::add_offset_to_expr;
1414
use crate::projection::ProjectionTargets;
1515
use crate::{PhysicalExpr, PhysicalExprRef, PhysicalSortExpr, PhysicalSortRequirement};
1616

1717
use datafusion_common::tree_node::{Transformed, TransformedResult, TreeNode};
1818
use datafusion_common::{JoinType, Result, ScalarValue};
1919
use datafusion_expr::sort_properties::SortProperties;
20-
use datafusion_physical_expr_common::physical_expr::format_physical_expr_list;
20+
use datafusion_physical_expr_common::physical_expr::{
21+
format_physical_expr_list, is_volatile,
22+
};
2123

2224
use indexmap::{IndexMap, IndexSet};
2325

@@ -172,6 +174,14 @@ pub struct EquivalenceClass {
172174
}
173175

174176
impl EquivalenceClass {
177+
/// Keeps what still holds on a join side whose unmatched rows are padded
178+
/// with NULLs: padded columns stay equal to each other, but constants and
179+
/// computed members do not (`coalesce(a, 0)` is 0 where `a` is NULL).
180+
fn null_pad(&mut self) {
181+
self.constant = None;
182+
self.exprs.retain(|expr| expr.is::<Column>());
183+
}
184+
175185
// Create a new equivalence class from a pre-existing collection.
176186
pub fn new(exprs: impl IntoIterator<Item = Arc<dyn PhysicalExpr>>) -> Self {
177187
let mut class = Self::default();
@@ -740,6 +750,7 @@ impl EquivalenceGroup {
740750
let mut new_constants = vec![];
741751
let mut new_classes =
742752
IndexMap::<_, EquivalenceClass>::with_capacity(mapping.len());
753+
let mut augmented = None;
743754
for (source, targets) in mapping.iter() {
744755
// We need to find equivalent projected expressions. For example,
745756
// consider a table with columns `[a, b, c]` with `a` == `b`, and
@@ -751,6 +762,15 @@ impl EquivalenceGroup {
751762
for (target, _) in targets.iter() {
752763
cls.push(Arc::clone(target));
753764
}
765+
// Retain deterministic expressions as equalities so orderings derived
766+
// through strict functions can be inferred after a merge clears orderings.
767+
if !source.children().is_empty() && !is_volatile(source) {
768+
let augmented = augmented
769+
.get_or_insert_with(|| self.augment_projection_mapping(mapping));
770+
if let Some(projected) = Self::project_expr_indirect(augmented, source) {
771+
cls.push(projected);
772+
}
773+
}
754774
// Save new constants arising from the projection:
755775
if let Some(across) = self.is_expr_constant(source) {
756776
for (target, _) in targets.iter() {
@@ -837,10 +857,10 @@ impl EquivalenceGroup {
837857
.cloned()
838858
.map(|mut cls| {
839859
// Rows without a match on the left side are
840-
// padded with NULLs, so its constants no
841-
// longer hold.
860+
// padded with NULLs, so its constants and computed
861+
// equalities no longer hold.
842862
if matches!(join_type, JoinType::Right | JoinType::Full) {
843-
cls.constant = None;
863+
cls.null_pad();
844864
}
845865
cls
846866
})
@@ -850,13 +870,13 @@ impl EquivalenceGroup {
850870
.map(|cls| {
851871
let mut cls = cls.try_with_offset(left_size as _)?;
852872
// Rows without a match on the right side are
853-
// padded with NULLs, so its constants no
854-
// longer hold.
873+
// padded with NULLs, so its constants and computed
874+
// equalities no longer hold.
855875
if matches!(
856876
join_type,
857877
JoinType::Left | JoinType::Full
858878
) {
859-
cls.constant = None;
879+
cls.null_pad();
860880
}
861881
Ok(cls)
862882
})

‎datafusion/physical-expr/src/equivalence/properties/mod.rs‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1298,7 +1298,8 @@ impl EquivalenceProperties {
12981298
/// # Returns
12991299
///
13001300
/// Returns an [`ExprProperties`] object containing the ordering and range
1301-
/// information for the given expression.
1301+
/// information for the given expression. If its ordering is unknown, falls
1302+
/// back to the sort properties of an equivalent expression.
13021303
pub fn get_expr_properties(&self, expr: Arc<dyn PhysicalExpr>) -> ExprProperties {
13031304
SortKeyWalk::new(self).expr_properties(expr)
13041305
}

‎datafusion/physical-expr/src/equivalence/properties/walk.rs‎

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -104,7 +104,17 @@ impl<'a> SortKeyWalk<'a> {
104104
/// group.
105105
fn pin_key(&mut self, key: Arc<dyn PhysicalExpr>) -> Result<()> {
106106
let mut stack = vec![key];
107+
let mut visited = HashSet::new();
107108
while let Some(expr) = stack.pop() {
109+
if let Some(class) = self.props.eq_group.get_equivalence_class(&expr) {
110+
for equivalent in class.iter() {
111+
if !equivalent.children().is_empty()
112+
&& visited.insert(Arc::clone(equivalent))
113+
{
114+
stack.push(Arc::clone(equivalent));
115+
}
116+
}
117+
}
108118
let properties = self.expr_properties(Arc::clone(&expr));
109119
if properties.strictly_order_preserving {
110120
for child in expr.children() {
@@ -175,6 +185,25 @@ impl<'a> SortKeyWalk<'a> {
175185
/// Returns the properties of `expr` among the rows that tie on the
176186
/// pinned expressions.
177187
pub(super) fn expr_properties(&self, expr: Arc<dyn PhysicalExpr>) -> ExprProperties {
188+
let class = self.props.eq_group.get_equivalence_class(&expr);
189+
let mut properties = self.expr_properties_from_tree(expr);
190+
if properties.sort_properties != SortProperties::Unordered {
191+
return properties;
192+
}
193+
if let Some(class) = class {
194+
for equivalent in class.iter() {
195+
let equivalent_properties =
196+
self.expr_properties_from_tree(Arc::clone(equivalent));
197+
if equivalent_properties.sort_properties != SortProperties::Unordered {
198+
properties.sort_properties = equivalent_properties.sort_properties;
199+
return properties;
200+
}
201+
}
202+
}
203+
properties
204+
}
205+
206+
fn expr_properties_from_tree(&self, expr: Arc<dyn PhysicalExpr>) -> ExprProperties {
178207
ExprPropertiesNode::new_unknown(expr)
179208
.transform_up(|node| self.update_properties(node))
180209
.data()

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

Lines changed: 10 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -311,11 +311,16 @@ fn pushdown_sorts_helper(
311311
sort_ordering.clone().into(),
312312
parent_requirement.first().clone(),
313313
);
314-
sort_push_down.data.ordering_requirement = if current_is_stricter {
315-
Some(OrderingRequirements::from(sort_ordering))
316-
} else {
317-
Some(parent_requirement)
318-
};
314+
// A fetched sort selects rows using its own keys. Even if those
315+
// keys satisfy the parent ordering, replacing them with a weaker
316+
// ordering can change which rows survive (e.g. a lossy cast can
317+
// introduce ties). Keep the selection keys in that case.
318+
sort_push_down.data.ordering_requirement =
319+
if current_is_stricter || (sort_fetch.is_some() && satisfy_parent) {
320+
Some(OrderingRequirements::from(sort_ordering))
321+
} else {
322+
Some(parent_requirement)
323+
};
319324
// Recursive call to helper, so it doesn't transform_down and miss
320325
// the new node (previous child of sort):
321326
return pushdown_sorts_helper(sort_push_down);

‎datafusion/physical-plan/src/repartition/mod.rs‎

Lines changed: 6 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -2187,15 +2187,14 @@ impl RepartitionExec {
21872187
input: &Arc<dyn ExecutionPlan>,
21882188
preserve_order: bool,
21892189
) -> EquivalenceProperties {
2190-
// Equivalence Properties
21912190
let mut eq_properties = input.equivalence_properties().clone();
2192-
// If the ordering is lost, reset the ordering equivalence class:
2193-
if !Self::maintains_input_order_helper(input, preserve_order)[0] {
2194-
eq_properties.clear_orderings();
2195-
}
2196-
// When there are more than one input partitions, they will be fused at the output.
2197-
// Therefore, remove per partition constants.
2191+
// Fusing several input partitions keeps only the merge key ordering,
2192+
// and per-partition constants no longer hold.
21982193
if input.output_partitioning().partition_count() > 1 {
2194+
eq_properties.clear_orderings();
2195+
if preserve_order && let Some(ordering) = input.output_ordering() {
2196+
eq_properties.add_ordering(ordering.clone());
2197+
}
21992198
eq_properties.clear_per_partition_constants();
22002199
}
22012200
eq_properties

‎datafusion/sqllogictest/test_files/equivalence_properties.slt‎

Lines changed: 140 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -134,6 +134,133 @@ SELECT l.c, s.x FROM (SELECT c FROM t) l CROSS JOIN (SELECT x FROM small WHERE x
134134
1 1
135135
2 1
136136

137+
###
138+
### Equal expressions need not be injective
139+
###
140+
141+
# c = abs(a) transfers ordering to abs(a), but equal c values do not pin
142+
# down a. The sort on b must remain for the two rows with c = 1.
143+
statement ok
144+
set datafusion.execution.target_partitions = 1;
145+
146+
query I
147+
COPY (VALUES (-1, 2, 1), (1, 1, 1))
148+
TO 'test_files/scratch/equivalence_properties/abs.csv'
149+
OPTIONS ('format.has_header' 'true');
150+
----
151+
2
152+
153+
statement ok
154+
CREATE EXTERNAL TABLE abs_equivalence (a INT, b INT, c INT)
155+
STORED AS CSV
156+
WITH ORDER (a, b)
157+
WITH ORDER (c)
158+
LOCATION 'test_files/scratch/equivalence_properties/abs.csv'
159+
OPTIONS ('format.has_header' 'true');
160+
161+
query III
162+
SELECT a, b, c FROM abs_equivalence WHERE c = abs(a) ORDER BY c, b;
163+
----
164+
1 1 1
165+
-1 2 1
166+
167+
statement ok
168+
DROP TABLE abs_equivalence;
169+
170+
###
171+
### Projection equalities and TopK
172+
###
173+
174+
# Independent volatile calls must keep the outer sort above the inner TopK.
175+
statement ok
176+
set datafusion.execution.target_partitions = 1;
177+
178+
query TT
179+
EXPLAIN SELECT r, x FROM (
180+
SELECT random() AS r, CAST(random() AS FLOAT) AS x
181+
FROM generate_series(1, 2000) ORDER BY r LIMIT 1000
182+
) ORDER BY x;
183+
----
184+
physical_plan
185+
01)SortExec: expr=[x@1 ASC NULLS LAST], preserve_partitioning=[false]
186+
02)--SortExec: TopK(fetch=1000), expr=[r@0 ASC NULLS LAST], preserve_partitioning=[false]
187+
03)----ProjectionExec: expr=[random() as r, CAST(random() AS Float32) as x]
188+
04)------LazyMemoryExec: partitions=1, batch_generators=[generate_series: start=1, end=2000, batch_size=8192]
189+
190+
# A deterministic cast is a valid equality, but can introduce ties. The
191+
# inner TopK must still select by r, even though its output is ordered by x.
192+
statement ok
193+
CREATE TABLE lossy_topk AS VALUES (16777217), (16777216);
194+
195+
query IR
196+
SELECT r, x FROM (
197+
SELECT column1 AS r, CAST(column1 AS FLOAT) AS x FROM lossy_topk
198+
ORDER BY r LIMIT 1
199+
) ORDER BY x;
200+
----
201+
16777216 16777216
202+
203+
statement ok
204+
DROP TABLE lossy_topk;
205+
206+
statement ok
207+
set datafusion.execution.target_partitions = 4;
208+
209+
###
210+
### Outer join NULL padding invalidates computed equalities
211+
###
212+
213+
statement ok
214+
set datafusion.execution.target_partitions = 1;
215+
216+
statement ok
217+
CREATE TABLE padded_l(k INT) AS VALUES (1), (2), (3);
218+
219+
statement ok
220+
CREATE TABLE padded_r(k INT, a INT) AS VALUES (1, 1), (2, 2);
221+
222+
# On the unmatched row, rr.x is NULL but the CASE expression is 0.
223+
# Their input equality must not remove the outer sort.
224+
query I
225+
SELECT y FROM (
226+
SELECT CASE WHEN a IS NULL THEN 0 ELSE a END AS y FROM (
227+
SELECT rr.x, rr.a
228+
FROM (SELECT k, a, CASE WHEN a IS NULL THEN 0 ELSE a END AS x FROM padded_r) rr
229+
RIGHT JOIN padded_l ON padded_l.k = rr.k
230+
ORDER BY rr.x LIMIT 100
231+
)
232+
) ORDER BY y;
233+
----
234+
0
235+
1
236+
2
237+
238+
# The filter-derived equality from #26036 is also invalid on padded rows.
239+
statement ok
240+
CREATE TABLE padded_filter(a INT, b INT) AS VALUES (2, 2), (3, 3), (5, 5), (6, 6), (7, 7), (8, 8);
241+
242+
query III
243+
SELECT padded_l.k, rr.a, rr.b FROM padded_l
244+
LEFT JOIN (SELECT a, b FROM padded_filter WHERE b = coalesce(a, 0)) rr
245+
ON padded_l.k = rr.b
246+
ORDER BY coalesce(rr.a, 0), padded_l.k;
247+
----
248+
1 NULL NULL
249+
2 2 2
250+
3 3 3
251+
252+
statement ok
253+
DROP TABLE padded_filter;
254+
255+
statement ok
256+
DROP TABLE padded_l;
257+
258+
statement ok
259+
DROP TABLE padded_r;
260+
261+
statement ok
262+
set datafusion.execution.target_partitions = 4;
263+
137264
###
138265
### Functions whose ordering cannot be derived from their input
139266
###
@@ -235,6 +362,19 @@ physical_plan
235362
05)--------RepartitionExec: partitioning=RoundRobinBatch(2), input_partitions=1, maintains_sort_order=true
236363
06)----------StreamingTableExec: partition_sizes=1, projection=[a, b, c], infinite_source=true, output_ordering=[a@0 ASC NULLS LAST, b@1 ASC NULLS LAST, c@2 ASC NULLS LAST]
237364

365+
# Strictly increasing functions also retain their derived ordering after merging.
366+
query TT
367+
EXPLAIN SELECT a, x, SUM(c) OVER (PARTITION BY x ORDER BY b) s
368+
FROM (SELECT to_unixtime(a) x, a, b, c FROM t_inf);
369+
----
370+
physical_plan
371+
01)ProjectionExec: expr=[a@1 as a, x@0 as x, sum(t_inf.c) PARTITION BY [x] ORDER BY [t_inf.b ASC NULLS LAST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW@4 as s]
372+
02)--BoundedWindowAggExec: wdw=[sum(t_inf.c) PARTITION BY [x] ORDER BY [t_inf.b ASC NULLS LAST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW: Field { "sum(t_inf.c) PARTITION BY [x] ORDER BY [t_inf.b ASC NULLS LAST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW": nullable Int64 }, frame: RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW], mode=[Sorted]
373+
03)----RepartitionExec: partitioning=Hash([x@0], 2), input_partitions=2, preserve_order=true, sort_exprs=a@1 ASC NULLS LAST, b@2 ASC NULLS LAST, c@3 ASC NULLS LAST, x@0 ASC NULLS LAST
374+
04)------ProjectionExec: expr=[to_unixtime(a@0) as x, a@0 as a, b@1 as b, c@2 as c]
375+
05)--------RepartitionExec: partitioning=RoundRobinBatch(2), input_partitions=1, maintains_sort_order=true
376+
06)----------StreamingTableExec: partition_sizes=1, projection=[a, b, c], infinite_source=true, output_ordering=[a@0 ASC NULLS LAST, b@1 ASC NULLS LAST, c@2 ASC NULLS LAST]
377+
238378
statement ok
239379
set datafusion.execution.target_partitions = 4;
240380

‎datafusion/sqllogictest/test_files/monotonic_projection_test.slt‎

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -276,6 +276,14 @@ SELECT k, cast(v as float) v_ FROM t2_int_float ORDER BY v_ DESC, k DESC;
276276
2 16777216
277277
1 16777216
278278

279+
# Retaining v lets projection record v_ = CAST(v AS FLOAT). Equal v_ values
280+
# still do not imply equal v values: the suffix key must be sorted again.
281+
query IIR
282+
SELECT k, v, cast(v as float) v_ FROM t1_int_float ORDER BY v_ DESC, k DESC;
283+
----
284+
2 16777216 16777216
285+
1 16777217 16777216
286+
279287
# Widening cast (Int32 -> Int64) is strictly 1-to-1, so the optimizer CAN
280288
# legally reuse the pre-existing sort order and omit a SortExec.
281289
statement ok

‎datafusion/sqllogictest/test_files/order.slt‎

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2315,6 +2315,30 @@ physical_plan
23152315
02)--SortPreservingMergeExec: [a@0 ASC NULLS LAST], fetch=10
23162316
03)----DataSourceExec: file_groups={2 groups: [[WORKSPACE_ROOT/datafusion/sqllogictest/test_files/scratch/order/spm_orderings/1.csv], [WORKSPACE_ROOT/datafusion/sqllogictest/test_files/scratch/order/spm_orderings/2.csv]]}, projection=[a, b], limit=10, output_orderings=[[a@0 ASC NULLS LAST], [b@1 ASC NULLS LAST]], file_type=csv, has_header=true
23172317

2318+
# An order-preserving RepartitionExec also only guarantees its merge key
2319+
# ordering. Grouping by both columns merges on [a, b], so ORDER BY b still
2320+
# needs a sort even though each input file is individually sorted by b.
2321+
# https://github.com/apache/datafusion/issues/26745
2322+
statement ok
2323+
SET datafusion.optimizer.prefer_existing_sort = true;
2324+
2325+
statement ok
2326+
SET datafusion.optimizer.repartition_file_scans = false;
2327+
2328+
query III
2329+
SELECT a, b, count(*) FROM spm_orderings GROUP BY a, b ORDER BY b;
2330+
----
2331+
1 1 1
2332+
3 2 1
2333+
1 10 1
2334+
2 20 1
2335+
2336+
statement ok
2337+
RESET datafusion.optimizer.prefer_existing_sort;
2338+
2339+
statement ok
2340+
RESET datafusion.optimizer.repartition_file_scans;
2341+
23182342
statement ok
23192343
DROP TABLE spm_orderings;
23202344

‎datafusion/sqllogictest/test_files/push_down_filter_regression.slt‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -585,9 +585,9 @@ EXPLAIN SELECT a, b, cnt FROM (
585585
physical_plan
586586
01)FilterExec: cnt@2 = 2
587587
02)--ProjectionExec: expr=[a@0 as a, b@1 as b, count(agg_filter_pushdown.b)@2 as cnt]
588-
03)----AggregateExec: mode=FinalPartitioned, gby=[a@0 as a, b@1 as b], aggr=[count(agg_filter_pushdown.b)]
588+
03)----AggregateExec: mode=FinalPartitioned, gby=[a@0 as a, b@1 as b], aggr=[count(agg_filter_pushdown.b)], group_clustering_mode=Partial([1])
589589
04)------RepartitionExec: partitioning=Hash([a@0, b@1], 4), input_partitions=4
590-
05)--------AggregateExec: mode=Partial, gby=[a@0 as a, b@1 as b], aggr=[count(agg_filter_pushdown.b)]
590+
05)--------AggregateExec: mode=Partial, gby=[a@0 as a, b@1 as b], aggr=[count(agg_filter_pushdown.b)], group_clustering_mode=Partial([1])
591591
06)----------RepartitionExec: partitioning=RoundRobinBatch(4), input_partitions=1
592592
07)------------DataSourceExec: file_groups={1 group: [[WORKSPACE_ROOT/datafusion/sqllogictest/test_files/scratch/push_down_filter_regression/agg_filter_pushdown.parquet]]}, projection=[a, b], file_type=parquet, predicate=b@1 = CAST(foo AS Utf8View), pruning_predicate=b_null_count@2 != row_count@3 AND b_min@0 <= foo AND foo <= b_max@1, required_guarantees=[]
593593

0 commit comments

Comments
 (0)