Skip to content

Commit 20c7daf

Browse files
committed
Run the rules that decide requirements before enforcing them
Enforcing requirements first and having the rules that change them repair afterwards was out of order for joins, not merely slow. A hash join starts as PartitionMode::Auto, which declares UnspecifiedDistribution for its children and UnknownPartitioning for its output, so the enforcement pass did nothing for joins; only once JoinSelection picked a mode did the plan acquire requirements nothing satisfied, and the repair then re-derived them over the whole tree, on a tree the first pass had already expanded. Profiling tpch q21 put that second enforce_distribution_requirements pass at 152 us, 72% of the planning regression. FilterPushdown repaired for a different reason: pushing a predicate into a source flips its row count from Exact to Inexact, which changes whether the scan is parallelized, so enforcement wants to see the statistics as they are after pushdown. Both rules now run in the analyzer phase ahead of EnforceDistribution, and neither re-enforces anything. JoinSelection follows the FilterPushdown pattern: one rule constructed per phase. JoinSelection::new_before_enforcement is what the default analyzer registers and leaves materialising distribution to the pass that follows; JoinSelection::new keeps re-establishing distribution for the joins it changes, so it stays safe to register at any position. Both still normalise InterleaveExec back to UnionExec, which is what fixes the panic in apache#21826 and holds in either order. WindowTopN keeps its repair: it needs the enforced plan to rebuild the window over a hash-partitioned PartitionedTopKExec, and it genuinely disturbs both distribution and ordering, so it is the one optimizer rule the contract is for. Measured on tpch q21, same machine: merge-base 1.2312 ms, this branch as reviewed 1.3973 ms, now 1.1823 ms. The split into EnforceDistribution and EnforceSorting is not where the cost was: on main EnsureRequirements already runs distribution and sorting as two separate bottom-up walks, and the two phases measured at 2.3 us and 6.6 us against 292 us for distribution itself. Plan changes across the full sqllogictest suite are now limited to the rule trace in explain.slt. window_topn.slt keeps the improved plan, and repartition_scan.slt keeps its four file groups without any repair, since enforcement now runs after the predicate reaches the source. The thirty standalone FilterPushdown snapshots lose the RoundRobin repartition the old repair added; in the real pipeline EnforceDistribution runs right after it. Review feedback folded in: PR-history comments removed from optimizer.rs, analyzer.rs and the ensure_requirements test header, and the EnforceSorting docs now say its PhysicalOptimizerRule impl is only a compatibility shim.
1 parent e0c199a commit 20c7daf

11 files changed

Lines changed: 321 additions & 272 deletions

File tree

‎datafusion/core/src/optimizer_rule_reference.md‎

Lines changed: 41 additions & 42 deletions
Original file line numberDiff line numberDiff line change
@@ -42,24 +42,21 @@ Rule order matters. The default pipeline may change between releases.
4242
│
4343
│ PhysicalAnalyzer ... make the plan VALID
4444
│ 1. OutputRequirements (add) establish the output boundary
45-
│ 2. EnforceDistribution satisfy required_input_distribution
46-
│ 3. EnforceSorting satisfy required_input_ordering
45+
│ 2. join_selection resolve each join's PartitionMode::Auto
46+
│ 3. FilterPushdown push predicates into sources
47+
│ 4. EnforceDistribution satisfy required_input_distribution
48+
│ 5. EnforceSorting satisfy required_input_ordering
4749
│
4850
│ ==> from here on every PhysicalOptimizerRule receives a valid plan
4951
│ and must leave a valid plan
5052
│
5153
│ PhysicalOptimizer .. make the plan FASTER
5254
│ aggregate_statistics
53-
│ join_selection ─┐ changes partition mode / build side
54-
│ FilterPushdown ─┤ changes a source's row-count precision
55-
│ WindowTopN ─┤ rebuilds the window over a partitioned TopK
56-
│ OptimizeSorts │
55+
│ WindowTopN ───▶ re-enforces distribution + ordering for what it rewrote
56+
│ OptimizeSorts
5757
│ ... (full list in the table below)
5858
│ OutputRequirements (remove)
59-
│ SanityCheckPlan │
60-
│ └─▶ each re-establishes validity itself, scoped
61-
│ to what it changed, and only when it
62-
│ actually rewrote the plan
59+
│ SanityCheckPlan
6360
▼
6461
valid, optimized ExecutionPlan
6562
```
@@ -110,16 +107,20 @@ lives here. `OutputRequirements` (add phase) first establishes the
110107
output-requirement boundary so enforcement can see it (top-level scan
111108
parallelism, final-ordering preservation); `EnforceDistribution` then enforces
112109
distribution; `EnforceSorting` then enforces ordering on the distribution-fixed
113-
plan. The only optimizer rules that later change these requirements
114-
(`join_selection`, `WindowTopN`, `FilterPushdown`) re-establish validity
115-
themselves, so enforcement runs exactly once. The optimizer phase keeps only the
116-
sort _optimizations_ (`OptimizeSorts`), which make an already-valid plan faster.
110+
plan. Before that, `join_selection` resolves each join's partition mode and
111+
`FilterPushdown` pushes predicates into sources, so enforcement sees the plan's
112+
real requirements and final statistics and runs exactly once. The optimizer
113+
phase keeps only the sort _optimizations_ (`OptimizeSorts`), which make an
114+
already-valid plan faster; `WindowTopN` is the one optimizer rule that still
115+
changes a requirement, and it re-establishes validity itself.
117116

118117
| order | rule | summary |
119118
| ----- | --------------------- | ----------------------------------------------------------------------------------------- |
120119
| 1 | `OutputRequirements` | Adds helper nodes so output requirements survive enforcement and later physical rewrites. |
121-
| 2 | `EnforceDistribution` | Enforces the distribution requirements each operator declares (repartition / coalesce). |
122-
| 3 | `EnforceSorting` | Enforces ordering requirements (inserts SortExecs) on the distribution-fixed plan. |
120+
| 2 | `join_selection` | Resolves each join's partition mode and build side, so enforcement sees its requirements. |
121+
| 3 | `FilterPushdown` | Pushes supported physical filters into sources, so enforcement sees final statistics. |
122+
| 4 | `EnforceDistribution` | Enforces the distribution requirements each operator declares (repartition / coalesce). |
123+
| 5 | `EnforceSorting` | Enforces ordering requirements (inserts SortExecs) on the distribution-fixed plan. |
123124

124125
### Physical Optimizer Rules
125126

@@ -128,29 +129,27 @@ in multiple phases.
128129

129130
All enforcement (the `OutputRequirements` add boundary, `EnforceDistribution`,
130131
`EnforceSorting`) runs first, in the analyzer phase (see above), so it does not
131-
appear in this list; the rules that change those requirements (`join_selection`,
132-
`WindowTopN`, `FilterPushdown`) re-establish validity themselves. The matching
133-
`OutputRequirements` remove phase still runs here, late, once planning is done.
134-
135-
| order | rule | phase | summary |
136-
| ----- | ------------------------------ | ----------------------- | ----------------------------------------------------------------------------------------------------------------------- |
137-
| 1 | `aggregate_statistics` | - | Uses exact source statistics to answer some aggregates without scanning data. |
138-
| 2 | `join_selection` | - | Chooses join implementation, build side, and partition mode; re-establishes distribution validity for joins it changes. |
139-
| 3 | `LimitedDistinctAggregation` | - | Pushes limit hints into grouped distinct-style aggregations when only a small result is needed. |
140-
| 4 | `FilterPushdown` | pre-optimization phase | Pushes supported physical filters down toward data sources; re-establishes validity for what it changes. |
141-
| 5 | `WindowTopN` | - | Replaces eligible row-number window and filter patterns with per-partition TopK execution; re-enforces validity. |
142-
| 6 | `OptimizeSorts` | - | Sort optimizations: parallelize sorts, order-preserving variants, sort pushdown, partial sort. |
143-
| 7 | `CombinePartialFinalAggregate` | - | Collapses adjacent partial and final aggregates when the distributed shape makes them redundant. |
144-
| 8 | `OptimizeAggregateOrder` | - | Updates aggregate expressions to use the best ordering once sort requirements are known. |
145-
| 9 | `ProjectionPushdown` | early pass | Pushes projections toward inputs before later physical rewrites add more limit and TopK structure. |
146-
| 10 | `OutputRequirements` | remove phase | Removes the temporary output-requirement helper nodes after requirement-sensitive planning is done. |
147-
| 11 | `LimitAggregation` | - | Passes a limit hint into eligible aggregations so they can keep fewer accumulator buckets. |
148-
| 12 | `LimitPushPastWindows` | - | Pushes fetch limits through bounded window operators when doing so keeps the result correct. |
149-
| 13 | `HashJoinBuffering` | - | Adds buffering on the probe side of hash joins so probing can start before build completion. |
150-
| 14 | `LimitPushdown` | - | Moves physical limits into child operators or fetch-enabled variants to cut data early. |
151-
| 15 | `TopKRepartition` | - | Pushes TopK below hash repartition when the partition key is a prefix of the sort key. |
152-
| 16 | `ProjectionPushdown` | late pass | Runs projection pushdown again after limit and TopK rewrites expose new pruning opportunities. |
153-
| 17 | `PushdownSort` | - | Pushes sort requirements into data sources that can already return sorted output. |
154-
| 18 | `EnsureCooperative` | - | Wraps non-cooperative plan parts so long-running tasks yield fairly. |
155-
| 19 | `FilterPushdown(Post)` | post-optimization phase | Pushes dynamic filters at the end of optimization, after plan references stop moving. |
156-
| 20 | `SanityCheckPlan` | - | Validates that the final physical plan meets ordering, distribution, and infinite-input safety requirements. |
132+
appear in this list, and neither do `join_selection` and `FilterPushdown`, which
133+
run there ahead of it. The matching `OutputRequirements` remove phase still runs
134+
here, late, once planning is done.
135+
136+
| order | rule | phase | summary |
137+
| ----- | ------------------------------ | ----------------------- | ---------------------------------------------------------------------------------------------------------------- |
138+
| 1 | `aggregate_statistics` | - | Uses exact source statistics to answer some aggregates without scanning data. |
139+
| 2 | `LimitedDistinctAggregation` | - | Pushes limit hints into grouped distinct-style aggregations when only a small result is needed. |
140+
| 3 | `WindowTopN` | - | Replaces eligible row-number window and filter patterns with per-partition TopK execution; re-enforces validity. |
141+
| 4 | `OptimizeSorts` | - | Sort optimizations: parallelize sorts, order-preserving variants, sort pushdown, partial sort. |
142+
| 5 | `CombinePartialFinalAggregate` | - | Collapses adjacent partial and final aggregates when the distributed shape makes them redundant. |
143+
| 6 | `OptimizeAggregateOrder` | - | Updates aggregate expressions to use the best ordering once sort requirements are known. |
144+
| 7 | `ProjectionPushdown` | early pass | Pushes projections toward inputs before later physical rewrites add more limit and TopK structure. |
145+
| 8 | `OutputRequirements` | remove phase | Removes the temporary output-requirement helper nodes after requirement-sensitive planning is done. |
146+
| 9 | `LimitAggregation` | - | Passes a limit hint into eligible aggregations so they can keep fewer accumulator buckets. |
147+
| 10 | `LimitPushPastWindows` | - | Pushes fetch limits through bounded window operators when doing so keeps the result correct. |
148+
| 11 | `HashJoinBuffering` | - | Adds buffering on the probe side of hash joins so probing can start before build completion. |
149+
| 12 | `LimitPushdown` | - | Moves physical limits into child operators or fetch-enabled variants to cut data early. |
150+
| 13 | `TopKRepartition` | - | Pushes TopK below hash repartition when the partition key is a prefix of the sort key. |
151+
| 14 | `ProjectionPushdown` | late pass | Runs projection pushdown again after limit and TopK rewrites expose new pruning opportunities. |
152+
| 15 | `PushdownSort` | - | Pushes sort requirements into data sources that can already return sorted output. |
153+
| 16 | `EnsureCooperative` | - | Wraps non-cooperative plan parts so long-running tasks yield fairly. |
154+
| 17 | `FilterPushdown(Post)` | post-optimization phase | Pushes dynamic filters at the end of optimization, after plan references stop moving. |
155+
| 18 | `SanityCheckPlan` | - | Validates that the final physical plan meets ordering, distribution, and infinite-input safety requirements. |

‎datafusion/core/src/physical_planner.rs‎

Lines changed: 1 addition & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -3100,9 +3100,7 @@ impl DefaultPhysicalPlanner {
31003100
/// declares. The optimizer phase then makes that already-valid plan
31013101
/// *faster*, so every [`PhysicalOptimizerRule`] receives a valid plan and
31023102
/// is expected to leave one. See [`PhysicalAnalyzerRule`] for the phase
3103-
/// diagram and for how the rules that change a requirement
3104-
/// (`JoinSelection`, `FilterPushdown`, `WindowTopN`) re-establish validity
3105-
/// themselves.
3103+
/// diagram.
31063104
///
31073105
/// [`PhysicalOptimizerRule`]: datafusion_physical_optimizer::PhysicalOptimizerRule
31083106
/// [`PhysicalAnalyzerRule`]: datafusion_physical_optimizer::analyzer::PhysicalAnalyzerRule

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

Lines changed: 5 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -1566,16 +1566,14 @@ fn test_sort_pushed_below_limit_with_skip_keeps_skip_rows() -> Result<()> {
15661566
}
15671567

15681568
// ========================================================================
1569-
// Decomposition tests: `EnsureRequirements` was split into three rules
1570-
// (`EnforceDistribution` / `EnforceSorting` / `OptimizeSorts`). These pin
1571-
// the invariants that make the split behavior-preserving:
1572-
// 1. the three rules in sequence reproduce the monolithic rule exactly;
1573-
// 2. `EnforceDistribution` is idempotent (so it can run in the analyzer
1574-
// phase *and* be re-run in the optimizer phase);
1569+
// Invariants of the enforcement rules `EnforceDistribution`,
1570+
// `EnforceSorting` and `OptimizeSorts`:
1571+
// 1. run in sequence they produce the same plan as `EnsureRequirements`;
1572+
// 2. `EnforceDistribution` is idempotent;
15751573
// 3. `EnforceDistribution` behaves identically whether driven as a
15761574
// `PhysicalAnalyzerRule` or a `PhysicalOptimizerRule`;
15771575
// 4. `EnforceDistribution` only settles distribution; ordering is
1578-
// enforced later by `EnforceSorting`.
1576+
// enforced by `EnforceSorting`.
15791577
// ========================================================================
15801578

15811579
/// Run the decomposed pipeline (`EnforceDistribution` → `EnforceSorting` →

0 commit comments

Comments
 (0)