Skip to content

Commit 3f4a37f

Browse files
fix: decline sort pushdown through SortPreservingMergeExec with fetch (#26162) (#27060)
## Which issue does this PR close? - Closes #26162. ## Rationale for this change In #26162, running `ORDER BY b, a` over a multi-partition subquery with `ORDER BY b LIMIT n` produces incorrect ordering on `a`. Pushing `[b, a]` down removed the outer `SortExec`, but SPM only merges on `[b]`. As a result, `a` was not sorted in the final output. In the discussion, @jayzhan211 suggested two possible approaches: declining pushdown for SPM with fetch, or rewriting SPM's expressions when pushing through it. I chose `Ok(None)` (declining pushdown) because: - The subquery did not explicitly request the parent's sort. When a limit is present, forcing that sort on the entire dataset across partitions before a limit is unnecessary work. - Since `pushdown_requirement_to_children` only adds requirements to children, I think a logic to rewrite SPM adds extra complexity. ## What changes are included in this PR? - Return `Ok(None)` from `pushdown_requirement_to_children` when `plan` is `SortPreservingMergeExec` and has a `fetch`. - Add an SLT regression query in `limit.slt`. ## What is the testing strategy for this PR? - query on a partitioned table in `limit.slt` reproducing #26162. ## Are there any user-facing changes? Yes, bug fix: queries like `ORDER BY b, a` over a multi-partition subquery with `ORDER BY b LIMIT n` now return correctly ordered results on `a`. No API changes. --------- Co-authored-by: Jay Zhan <[email protected]>
1 parent 042727c commit 3f4a37f

3 files changed

Lines changed: 102 additions & 34 deletions

File tree

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

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -522,6 +522,32 @@ fn test_fetched_merge_keeps_stricter_topk_above() {
522522
");
523523
}
524524

525+
/// A merge guarantees only its own keys across partitions, so a finer
526+
/// requirement must stay above it.
527+
#[test]
528+
fn test_finer_sort_stays_above_merge_without_fetch() {
529+
let source: Arc<dyn ExecutionPlan> = Arc::new(MockMultiPartitionExec::new(4));
530+
let a = sort_expr_on("a", 0, false, false);
531+
let a_b = LexOrdering::new(
532+
a.iter()
533+
.cloned()
534+
.chain(sort_expr_on("b", 1, false, false).iter().cloned()),
535+
)
536+
.unwrap();
537+
let merge = Arc::new(SortPreservingMergeExec::new(a, source));
538+
let plan: Arc<dyn ExecutionPlan> = Arc::new(SortExec::new(a_b, merge));
539+
540+
let mut sort_push_down = SortPushDown::new_default(plan);
541+
assign_initial_requirements(&mut sort_push_down);
542+
let pushed_down = plan_string(&pushdown_sorts(sort_push_down).unwrap().plan);
543+
544+
assert_snapshot!(pushed_down, @r"
545+
SortExec: expr=[a@0 ASC NULLS LAST, b@1 ASC NULLS LAST], preserve_partitioning=[false]
546+
SortPreservingMergeExec: [a@0 ASC NULLS LAST]
547+
MockMultiPartitionExec
548+
");
549+
}
550+
525551
// ========================================================================
526552
// Multiple sort columns test
527553
// ========================================================================

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

Lines changed: 5 additions & 34 deletions
Original file line numberDiff line numberDiff line change
@@ -5,10 +5,7 @@
55
use std::fmt::Debug;
66
use std::sync::Arc;
77

8-
use crate::utils::{
9-
add_sort_above_with_distribution, is_sort, is_sort_preserving_merge, is_union,
10-
is_window,
11-
};
8+
use crate::utils::{add_sort_above_with_distribution, is_sort, is_union, is_window};
129

1310
use arrow::datatypes::SchemaRef;
1411
use datafusion_common::tree_node::{Transformed, TreeNode};
@@ -524,21 +521,10 @@ fn pushdown_requirement_to_children(
524521
} else {
525522
Ok(None)
526523
}
527-
} else if plan.is::<SortPreservingMergeExec>() && plan.fetch().is_some() {
528-
// Push down through a fetched merge when:
529-
// - requirement is aligned with output ordering
530-
// - it preserves ordering during execution
531-
// Refining a fetched merge must preserve the ordering that selected its rows.
532-
let Some(ordering) = plan.output_ordering() else {
533-
return Ok(None);
534-
};
535-
Ok(plan
536-
.equivalence_properties()
537-
.requirements_compatible(
538-
parent_required.first().clone(),
539-
ordering.clone().into(),
540-
)
541-
.then(|| vec![Some(parent_required)]))
524+
} else if plan.is::<SortPreservingMergeExec>() {
525+
// A merge orders rows across partitions only by its own keys, and this
526+
// function doesn't rewrite them. Keep the finer parent sort above it.
527+
Ok(None)
542528
} else if is_union(plan) {
543529
// `UnionExec` does not have real sort requirements for its input, we
544530
// just propagate the sort requirements down:
@@ -593,21 +579,6 @@ fn pushdown_requirement_to_children(
593579
// Keep sorts above RepartitionExec even when a single input partition
594580
// lets it preserve order; pushing the sort below it provides no benefit.
595581
Ok(None)
596-
} else if is_sort_preserving_merge(plan) {
597-
let new_ordering = LexOrdering::from(parent_required.first().clone());
598-
let mut spm_eqs = plan.equivalence_properties().clone();
599-
let old_ordering = spm_eqs.output_ordering().unwrap();
600-
// Sort preserving merge will have new ordering, one requirement above is pushed down to its below.
601-
let change = spm_eqs.reorder(new_ordering)?;
602-
if !change || spm_eqs.ordering_satisfy(old_ordering)? {
603-
// Can push-down through SortPreservingMergeExec, because parent requirement is finer
604-
// than SortPreservingMergeExec output ordering.
605-
Ok(Some(vec![Some(parent_required)]))
606-
} else {
607-
// Do not push-down through SortPreservingMergeExec when
608-
// ordering requirement invalidates requirement of sort preserving merge exec.
609-
Ok(None)
610-
}
611582
} else if let Some(hash_join) = plan.downcast_ref::<HashJoinExec>() {
612583
handle_hash_join(hash_join, parent_required)
613584
} else {

‎datafusion/sqllogictest/test_files/limit.slt‎

Lines changed: 71 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1331,3 +1331,74 @@ SET datafusion.optimizer.max_passes = 3;
13311331

13321332
statement ok
13331333
DROP TABLE t26431;
1334+
1335+
# Test for #26162: ORDER BY b, a over a subquery with ORDER BY b LIMIT n
1336+
# Ensure SortPreservingMergeExec with fetch does not push down finer sort requirements
1337+
statement ok
1338+
CREATE TABLE t_26162 AS
1339+
SELECT 4 AS a, 1 AS b UNION ALL SELECT 8, 2 UNION ALL SELECT 12, 3
1340+
UNION ALL SELECT 3, 1 UNION ALL SELECT 7, 2 UNION ALL SELECT 11, 3
1341+
UNION ALL SELECT 2, 1 UNION ALL SELECT 6, 2 UNION ALL SELECT 10, 3
1342+
UNION ALL SELECT 1, 1 UNION ALL SELECT 5, 2 UNION ALL SELECT 9, 3;
1343+
1344+
query II
1345+
SELECT * FROM (SELECT a, b FROM t_26162 ORDER BY b LIMIT 8) ORDER BY b, a;
1346+
----
1347+
1 1
1348+
2 1
1349+
3 1
1350+
4 1
1351+
5 2
1352+
6 2
1353+
7 2
1354+
8 2
1355+
1356+
query TT
1357+
EXPLAIN SELECT * FROM (SELECT a, b FROM t_26162 ORDER BY b LIMIT 8) ORDER BY b, a;
1358+
----
1359+
logical_plan
1360+
01)Sort: t_26162.b ASC NULLS LAST, t_26162.a ASC NULLS LAST
1361+
02)--Sort: t_26162.b ASC NULLS LAST, fetch=8
1362+
03)----TableScan: t_26162 projection=[a, b]
1363+
physical_plan
1364+
01)SortExec: expr=[b@1 ASC NULLS LAST, a@0 ASC NULLS LAST], preserve_partitioning=[false]
1365+
02)--SortPreservingMergeExec: [b@1 ASC NULLS LAST], fetch=8
1366+
03)----SortExec: TopK(fetch=8), expr=[b@1 ASC NULLS LAST], preserve_partitioning=[true]
1367+
04)------DataSourceExec: partitions=12, partition_sizes=[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
1368+
1369+
# Requirements from a window, an ordered aggregate and a UNION also reach the merge.
1370+
query III
1371+
SELECT a, b, row_number() OVER (ORDER BY b, a) FROM (SELECT a, b FROM t_26162 ORDER BY b LIMIT 8) ORDER BY b, a;
1372+
----
1373+
1 1 1
1374+
2 1 2
1375+
3 1 3
1376+
4 1 4
1377+
5 2 5
1378+
6 2 6
1379+
7 2 7
1380+
8 2 8
1381+
1382+
query ?
1383+
SELECT array_agg(a ORDER BY b, a) FROM (SELECT a, b FROM t_26162 ORDER BY b LIMIT 8);
1384+
----
1385+
[1, 2, 3, 4, 5, 6, 7, 8]
1386+
1387+
query II
1388+
SELECT * FROM (
1389+
SELECT * FROM (SELECT a, b FROM t_26162 ORDER BY b LIMIT 4)
1390+
UNION ALL
1391+
SELECT * FROM (SELECT a, b FROM t_26162 ORDER BY b LIMIT 4)
1392+
) ORDER BY b, a;
1393+
----
1394+
1 1
1395+
1 1
1396+
2 1
1397+
2 1
1398+
3 1
1399+
3 1
1400+
4 1
1401+
4 1
1402+
1403+
statement ok
1404+
DROP TABLE t_26162;

0 commit comments

Comments
 (0)