|
15 | 15 | // specific language governing permissions and limitations |
16 | 16 | // under the License. |
17 | 17 |
|
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. |
20 | 20 | //! |
21 | 21 | //! This rule replaces the separate `EnforceDistribution` + `EnforceSorting` |
22 | 22 | //! rules with a unified approach inspired by Apache Spark's `EnsureRequirements` |
|
32 | 32 | //! |
33 | 33 | //! # Architecture |
34 | 34 | //! |
| 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 | +//! |
35 | 42 | //! ```text |
36 | 43 | //! EnsureRequirements::optimize(plan) |
37 | 44 | //! │ |
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 |
40 | 55 | //! │ |
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 |
47 | 61 | //! ``` |
48 | 62 | //! |
49 | 63 | //! # Key Properties |
50 | 64 | //! |
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. |
57 | 142 |
|
58 | 143 | // Internal implementation modules. Re-exported from `crate` root for tests |
59 | 144 | // in `core/tests/physical_optimizer/{enforce_distribution,enforce_sorting}.rs`. |
|
0 commit comments