Skip to content

Commit 97728ad

Browse files
committed
docs: tighten EnsureRequirements module doc; add explicit apache#21973 tests
- Replace inaccurate "single bottom-up pass" framing in the top-level module doc with a per-phase breakdown. Phase 2 is the single combined distribution+sorting bottom-up pass; the surrounding phases (top-down join-key reorder, parallelize_sorts, replace_with_order_preserving_variants, pushdown_sorts, replace_with_partial_sort) are independent traversals. - Restore the parallelism-via-repartitioning ASCII diagram that was dropped when the standalone EnforceDistribution rule was retired, now re-framed for the unified rule. - Add a "joint distribution + sorting" example showing the parallel SPM + Sort(preserve=true) plan EnsureRequirements produces, plus the strictest-distribution-match contract for joins. - Rename `test_idempotent_spm_sort_multi_partition` to `test_issue_21973_idempotent_spm_sort_multi_partition` and update the docstring to make the apache#21973 linkage explicit. - Add `test_issue_21973_parallel_sort_survives_multiple_passes`: a fresh 3-pass regression that asserts `Sort + Coalesce + multi-partition` is rewritten into `SPM + Sort(preserve=true) + multi-partition` on pass 1 and the parallel shape (SPM present, preserve_partitioning=true, no CoalescePartitionsExec) survives passes 2 and 3.
1 parent f6f8f5a commit 97728ad

2 files changed

Lines changed: 188 additions & 19 deletions

File tree

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

Lines changed: 87 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -631,16 +631,24 @@ fn test_idempotent_projection_over_multi_partition_with_single_partition_require
631631
assert_idempotent(output_req);
632632
}
633633

634-
/// Idempotency: `SPM → Sort(preserve=true) → multi-partition`.
635-
/// This is the topology that caused `test_pushdown_through_spm` to fail.
634+
/// Regression for #21973 (the issue this PR fixes).
635+
///
636+
/// Topology: `SPM → Sort(preserve=true) → multi-partition`. Under the old
637+
/// two-rule pipeline `EnforceSorting::pushdown_sorts` could mutate
638+
/// `preserve_partitioning` after `EnforceDistribution` had settled
639+
/// distribution, so pass 2 could regress this parallel plan into a serial
640+
/// one. This is the exact topology that caused
641+
/// [`test_pushdown_through_spm`](../enforce_sorting.rs) to fail before this
642+
/// PR; `EnsureRequirements` must keep the SPM-over-parallel-sort shape
643+
/// stable across passes.
636644
///
637645
/// Also acts as the "no extra SPM when already optimal" check — the
638646
/// input plan already contains exactly one `SortPreservingMergeExec`,
639647
/// so the optimised plan must too (we used to have a separate test for
640648
/// this property, but on this input it is implied by idempotency
641649
/// combined with the SPM-count assertion).
642650
#[test]
643-
fn test_idempotent_spm_sort_multi_partition() {
651+
fn test_issue_21973_idempotent_spm_sort_multi_partition() {
644652
let source: Arc<dyn ExecutionPlan> = Arc::new(MockMultiPartitionExec::new(10));
645653
let sort_expr = sort_expr_on("a", 0, true, true);
646654

@@ -668,6 +676,82 @@ fn test_idempotent_spm_sort_multi_partition() {
668676
assert_idempotent(limit);
669677
}
670678

679+
/// Regression for #21973: the `parallelize_sorts` rewrite path.
680+
///
681+
/// Input: `Sort(DESC) ← CoalescePartitionsExec ← multi-partition`. The first
682+
/// pass must rewrite this into a parallel plan
683+
/// `SortPreservingMergeExec ← Sort(preserve=true) ← multi-partition`, and
684+
/// subsequent passes must keep that parallel shape. Under the old two-rule
685+
/// pipeline `pushdown_sorts` could regress this back into a serial sort.
686+
///
687+
/// Runs 3 passes (one more than the standard idempotency check) and asserts
688+
/// the parallel plan structure survives each one.
689+
#[test]
690+
fn test_issue_21973_parallel_sort_survives_multiple_passes() {
691+
let source: Arc<dyn ExecutionPlan> = Arc::new(MockMultiPartitionExec::new(8));
692+
let coalesce: Arc<dyn ExecutionPlan> = Arc::new(CoalescePartitionsExec::new(source));
693+
694+
let sort_expr = sort_expr_on("a", 0, true, true);
695+
let sort: Arc<dyn ExecutionPlan> = Arc::new(SortExec::new(sort_expr, coalesce));
696+
let limit: Arc<dyn ExecutionPlan> = Arc::new(GlobalLimitExec::new(sort, 0, Some(10)));
697+
698+
let config = ConfigOptions::default();
699+
700+
let p1 = EnsureRequirements::new()
701+
.optimize(Arc::clone(&limit), &config)
702+
.expect("pass 1");
703+
let s1 = plan_string(&p1);
704+
705+
let p2 = EnsureRequirements::new()
706+
.optimize(Arc::clone(&p1), &config)
707+
.expect("pass 2");
708+
let s2 = plan_string(&p2);
709+
710+
let p3 = EnsureRequirements::new()
711+
.optimize(Arc::clone(&p2), &config)
712+
.expect("pass 3");
713+
let s3 = plan_string(&p3);
714+
715+
// The parallel-sort shape must appear after pass 1 and survive every
716+
// subsequent pass. Specifically: SortPreservingMergeExec on top of a
717+
// Sort with preserve_partitioning=true (no CoalescePartitionsExec).
718+
for (i, plan_str) in [&s1, &s2, &s3].iter().enumerate() {
719+
assert!(
720+
plan_str.contains("SortPreservingMergeExec"),
721+
"pass {} regressed to serial: missing SortPreservingMergeExec:\n{plan_str}",
722+
i + 1
723+
);
724+
assert!(
725+
plan_str.contains("preserve_partitioning=[true]"),
726+
"pass {} regressed to serial: Sort lost preserve_partitioning=true (#21973):\n{plan_str}",
727+
i + 1
728+
);
729+
assert!(
730+
!plan_str.contains("CoalescePartitionsExec"),
731+
"pass {} regressed to serial: CoalescePartitionsExec re-introduced (#21973):\n{plan_str}",
732+
i + 1
733+
);
734+
}
735+
736+
assert_eq!(
737+
s1, s2,
738+
"not idempotent between pass 1 and 2 (#21973):\n{s1}\nvs\n{s2}"
739+
);
740+
assert_eq!(
741+
s2, s3,
742+
"not idempotent between pass 2 and 3 (#21973):\n{s2}\nvs\n{s3}"
743+
);
744+
745+
// All passes must produce sanity-checkable plans.
746+
for (i, p) in [p1, p2, p3].into_iter().enumerate() {
747+
SanityCheckPlan::new()
748+
.optimize(p, &config)
749+
.unwrap_or_else(|e| {
750+
panic!("SanityCheckPlan failed on pass {}: {e:?}", i + 1)
751+
});
752+
}
753+
}
754+
671755
/// Idempotency: Sort → Aggregate → Sort → Aggregate pattern (#18989).
672756
/// This tests the multi-aggregate topology that caused SanityCheckPlan
673757
/// failures in upstream issue #18989.

‎datafusion/physical-optimizer/src/ensure_requirements/mod.rs‎

Lines changed: 101 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -15,8 +15,8 @@
1515
// specific language governing permissions and limitations
1616
// under the License.
1717

18-
//! [`EnsureRequirements`] optimizer rule that enforces both distribution and
19-
//! sorting requirements in a **single bottom-up pass**.
18+
//! [`EnsureRequirements`] optimizer rule that enforces distribution and
19+
//! sorting requirements together so that the two never invalidate each other.
2020
//!
2121
//! This rule replaces the separate `EnforceDistribution` + `EnforceSorting`
2222
//! rules with a unified approach inspired by Apache Spark's `EnsureRequirements`
@@ -32,28 +32,113 @@
3232
//!
3333
//! # Architecture
3434
//!
35+
//! `optimize` runs several tree traversals. The defining property of this
36+
//! rule is **Phase 2**: a single combined bottom-up pass that resolves
37+
//! distribution *and* sorting for each node together. The surrounding phases
38+
//! are independent traversals (top-down join-key reorder, then several
39+
//! follow-up sort/order rewrites). Some of those could be consolidated
40+
//! further in a follow-up.
41+
//!
3542
//! ```text
3643
//! EnsureRequirements::optimize(plan)
3744
//! │
38-
//! ├─ Phase 1 (optional): reorder_join_keys (top-down)
39-
//! │ └─ Same as existing adjust_input_keys_ordering
45+
//! ├─ Phase 1: top-down join-key reorder (adjust_input_keys_ordering)
46+
//! │
47+
//! ├─ Phase 2: combined distribution + sorting (single bottom-up pass)
48+
//! │ └─ For each node (bottom-up), for each child:
49+
//! │ Step 1: ensure distribution requirement
50+
//! │ └─ insert RepartitionExec / CoalescePartitionsExec /
51+
//! │ SortPreservingMergeExec as needed
52+
//! │ Step 2: ensure ordering requirement (distribution-aware)
53+
//! │ └─ insert SortExec with the correct `preserve_partitioning`,
54+
//! │ with SortPreservingMergeExec on top if needed
4055
//! │
41-
//! └─ Phase 2: ensure_requirements (single bottom-up pass)
42-
//! └─ For each node (bottom-up), for each child:
43-
//! Step 1: Ensure distribution requirement
44-
//! └─ Add RepartitionExec / CoalescePartitionsExec / SortPreservingMergeExec
45-
//! Step 2: Ensure ordering requirement (distribution-aware)
46-
//! └─ Add SortExec with correct preserve_partitioning + SPM if needed
56+
//! └─ Phase 3: small follow-up passes (bottom-up unless noted)
57+
//! ├─ parallelize_sorts
58+
//! ├─ replace_with_order_preserving_variants
59+
//! ├─ pushdown_sorts (recursive walk)
60+
//! └─ replace_with_partial_sort
4761
//! ```
4862
//!
4963
//! # Key Properties
5064
//!
51-
//! - **Idempotent**: Running the rule twice produces the same plan.
52-
//! - **Distribution before sorting**: For each child, distribution is resolved
53-
//! before ordering, so sorting decisions always have full distribution context.
54-
//! - **No separate `pushdown_sorts`**: Sort pushdown is implicit — the bottom-up
55-
//! pass only adds `SortExec` where the child doesn't already satisfy the
56-
//! ordering requirement, naturally placing sorts at the deepest valid position.
65+
//! - **Idempotent across the whole rule**: Running `EnsureRequirements`
66+
//! twice produces the same plan. This is the property that fixes
67+
//! <https://github.com/apache/datafusion/issues/21973>, where the old
68+
//! two-rule pipeline could regress a parallel sort plan into a serial one
69+
//! on pass 2.
70+
//! - **Distribution before sorting**: For each child, distribution is
71+
//! resolved before ordering, so sorting decisions always have full
72+
//! distribution context.
73+
//! - **Sort pushdown is implicit**: Phase 2 only adds `SortExec` where the
74+
//! child doesn't already satisfy the ordering requirement, so sorts land
75+
//! at the deepest valid position without a separate destructive pass.
76+
//!
77+
//! # Behavior: parallelism via repartitioning
78+
//!
79+
//! Phase 2 Step 1 inserts `RepartitionExec` to satisfy distribution
80+
//! requirements. When configuration allows, it also increases parallelism by
81+
//! repartitioning over otherwise-serial inputs. For example, given two
82+
//! 1-partition inputs feeding an operator that can run with more
83+
//! parallelism:
84+
//!
85+
//! ```text
86+
//! ┌─────────────────────────────────┐
87+
//! │ ExecutionPlan │
88+
//! └─────────────────────────────────┘
89+
//! ▲ ▲
90+
//! │ │
91+
//! ┌───────────┐ ┌───────────┐
92+
//! │ batch A │ │ batch B │ Input: 2 partitions
93+
//! └───────────┘ └───────────┘
94+
//! ```
95+
//!
96+
//! `EnsureRequirements` inserts a `RepartitionExec` so the operator runs
97+
//! with three partitions:
98+
//!
99+
//! ```text
100+
//! ┌─────────────────────────────────┐
101+
//! │ ExecutionPlan │ Input now has 3 partitions
102+
//! └─────────────────────────────────┘
103+
//! ▲ ▲ ▲
104+
//! └──────┼───────┘
105+
//! │
106+
//! ┌─────────────────────────────────┐
107+
//! │ RepartitionExec(3) │ batches are repartitioned
108+
//! │ RoundRobin │
109+
//! └─────────────────────────────────┘
110+
//! ▲ ▲
111+
//! ┌───────────┐ ┌───────────┐
112+
//! │ batch A │ │ batch B │
113+
//! └───────────┘ └───────────┘
114+
//! ```
115+
//!
116+
//! # Behavior: joint distribution + sorting
117+
//!
118+
//! Resolving distribution and sorting together lets Phase 2 produce a
119+
//! parallel sort plan in cases where the two-rule pipeline historically
120+
//! risked a serial one. Given `Sort(DESC) ← Coalesce ← MultiPartitionSource`,
121+
//! `EnsureRequirements` rewrites it into:
122+
//!
123+
//! ```text
124+
//! SortPreservingMergeExec: [a DESC] (cheap k-way merge of sorted streams)
125+
//! SortExec: [a DESC], preserve_partitioning=true (N sorts run in parallel)
126+
//! MultiPartitionSource
127+
//! ```
128+
//!
129+
//! Each input partition is sorted in parallel, then a `SortPreservingMergeExec`
130+
//! at the top performs a cheap merge of pre-sorted streams. For TopK queries
131+
//! (`fetch=K`), each parallel sort only keeps K rows per partition, so total
132+
//! memory is `N × K` rather than coalescing the entire stream first.
133+
//!
134+
//! # Behavior: strictest distribution match for joins
135+
//!
136+
//! Distribution requirements are met in the strictest way. For example, a
137+
//! hash join with keys `(a, b, c)` requires `Distribution(a, b, c)`. This
138+
//! can in principle be satisfied by partitioning on any superset of any
139+
//! subset of `(a, b, c)`, but this rule always partitions on the exact key
140+
//! tuple `(a, b, c)`. This is sometimes more aggressive than strictly
141+
//! necessary, but the strictest match helps avoid data skew in joins.
57142
58143
// Internal implementation modules. Re-exported from `crate` root for tests
59144
// in `core/tests/physical_optimizer/{enforce_distribution,enforce_sorting}.rs`.

0 commit comments

Comments
 (0)