jayzhan211 commented on issue #26481:
URL: https://github.com/apache/datafusion/issues/26481#issuecomment-6365171271
A proposal for where the analyzer/optimizer line should end up, and an order
of work to get there.
### Today vs proposed
```text
Today: one list, and correctness depends on the order
OutputRequirements (add)
AggregateStatistics, EliminateConstantJoin, JoinSelection,
LimitedDistinctAggregation, FilterPushdown, WindowTopN <- must run
before enforcement
EnsureRequirements <-
correctness and performance
CombinePartialFinalAggregate, OptimizeAggregateOrder, ProjectionPushdown
OutputRequirements (remove)
TopKAggregation, LimitPushPastWindows, HashJoinBuffering, LimitPushdown,
TopKRepartition, ProjectionPushdown, PushdownSort
EnsureCooperative <-
correctness
FilterPushdown (post-optimization) <- must run
last
SanityCheckPlan <- a check,
run as a rule
Proposed end state
Physical analyzer makes the plan executable
Physical optimizer makes it faster; valid in -> valid out, in any order
without losing correctness
Final check run by the planner, names the rule that broke the plan
```
Where each rule goes:
| Rule today | Proposed |
|---|---|
| `OutputRequirements` (add and remove) | Dropped. The planner passes the
root requirement to the analyzer. This also catches rules that drop the
top-level sort, which slip through today because the marker is removed before
`SanityCheckPlan` runs |
| `EnsureRequirements` | Split. The insert-only core (add repartition,
coalesce, merge and sort only where a requirement is unmet) goes to the
analyzer. The performance passes (join-key reorder, round-robin repartitioning,
sort parallelization, order-preserving variants, sort pushdown, partial sort)
stay together as one optimizer rule |
| `EnsureCooperative` | Dropped as a rule. Folded into the analyzer's core |
| `JoinSelection` | Split. Resolving `PartitionMode::Auto` and choosing
`SymmetricHashJoinExec` for unbounded inputs go to the analyzer (see open
questions). Build-side and `CollectLeft` choices go to the optimizer |
| `AggregateStatistics`, `EliminateConstantJoin`,
`LimitedDistinctAggregation`, `FilterPushdown`, `WindowTopN` | Optimizer. They
no longer have to run before enforcement; each keeps the plan valid |
| `FilterPushdown` (post-optimization) | Optimizer. "Must run last" is
replaced by nodes that hold a dynamic filter refusing to be restructured, as in
the fix for #26106 |
| `SanityCheckPlan` | Dropped as a rule. Replaced by the planner's final
check (#26461) |
| `CombinePartialFinalAggregate`, `OptimizeAggregateOrder`,
`ProjectionPushdown`, `TopKAggregation`, `LimitPushPastWindows`,
`HashJoinBuffering`, `LimitPushdown`, `TopKRepartition`, `PushdownSort` |
Optimizer, unchanged |
#25688 is the first step toward this; I think it needs a few changes before
it lands (see below).
### The boundary
The only invariant that crosses rule boundaries should be "the plan is
executable", judged only by what nodes declare (`required_input_distribution`,
`required_input_ordering`, scheduling type, `check_invariants(Executable)`).
Shape assumptions stay soft: missing one loses an optimization, never
correctness.
In the end state, the analyzer inserts `RepartitionExec`,
`CoalescePartitionsExec`, `SortPreservingMergeExec`, `SortExec` or
`CooperativeExec` only where a declared requirement or the query's output
requirement is unmet, and resolves undecided operators such as
`PartitionMode::Auto`. It makes no performance choices and changes nothing on a
valid plan. The one rewrite it keeps is turning an `InterleaveExec` whose
children are no longer co-partitioned back into a `UnionExec` (#21826). Because
it works from declarations, custom nodes take part automatically, including
custom exchanges that declare the same output properties.
### When an optimizer rule breaks a requirement
The rule repairs its own output by calling the enforcement core, so the core
becomes a public function. It has to run from the nearest ancestor whose
requirement the rewrite may have changed, not only on the rewritten subtree,
because the broken requirement belongs to the parent. Running it on the whole
plan is the simple default.
Today that repair is expensive and not safe to repeat: #25585 found that a
second `EnsureRequirements` pass changes 35 plans, and a second `PushdownSort`
pass returns wrong rows. The same applies to custom rule lists that still
contain `EnsureRequirements` once #25688 also runs it in the analyzer. A core
that only inserts where a requirement is unmet, and is a no-op on a valid plan,
makes the repair cheap and safe. It is also what any later fixed-point loop
(#25572) needs.
### Other proposals
- #25688 is the right vehicle, and keeping today's rule order in it keeps
the first step reviewable. So that it does not add new ways to get an invalid
plan, I think it needs these changes before it lands:
- Check that the plan is executable at the analyzer/optimizer boundary. A
`Session` that does not provide `physical_analyzers` (the default is an empty
list, and the FFI session does not forward it) silently skips enforcement, and
the plan only fails at execute time with `PartitionMode::Auto`. The check turns
that into a clear planning error.
- Keep the `OutputRequirements` add and remove steps paired. With add in
the analyzer and remove in the optimizer list, a custom optimizer list leaves
the marker in the final plan. Running the remove step from the planner after
the optimizer rules avoids that.
- Decide where `EliminateConstantJoin` (#26404, added after #25688 was
opened) goes. Keeping it in the analyzer just because it runs before
`JoinSelection` today would add another performance rule to the correctness
phase.
- #26360: the hard "requirements satisfied" region is the per-rule check I'd
add in debug and test builds, and its validation switch could control it. The
shape assumptions behind the soft regions are real (#26069 is a good example).
I'd document them on the rules that rely on them rather than enforce them,
since missing one only loses an optimization.
### Order
1. Land #25688 with today's order and the changes above.
2. Make violations visible: #26461, `HashJoinExec::check_invariants`
rejecting `PartitionMode::Auto`, an `Executable` check after each optimizer
rule in debug and test builds, and #26152.
3. Split `EnsureRequirements` internally into the insert-only core, exposed
as a public function, and its performance passes.
4. Let the planner hold the root requirement and deprecate
`OutputRequirements`.
5. Move the non-correctness rules from the analyzer to the optimizer one at
a time, each made valid in, valid out.
Steps 1 and 2 can go in parallel, and step 4 builds on step 1. Step 3 does
not block #25688; it is what step 5 and the repair model depend on. Steps 1 to
4 should leave EXPLAIN output and planning time unchanged; step 5 is the only
one that changes plans, and each move there comes with TPC-H/TPC-DS plan diffs
and planning-time benchmarks.
### Open questions
- Resolving `Auto` to `Partitioned` in the analyzer is always valid, but
plans may get worse unless `JoinSelection` can switch to `CollectLeft` and
repair locally.
- Choosing `SymmetricHashJoinExec` for two unbounded inputs decides whether
a query can run at all, so it belongs in the analyzer or in the planner.
- Distribution and sorting are decided together for a reason (#21973).
Keeping the performance passes inside `EnsureRequirements` limits the
plan-quality risk, but each step still needs TPC-H/TPC-DS plan diffs and
planning-time benchmarks.
- Should users be able to edit the analyzer list in the end state? An
editable list lets a custom pipeline drop enforcement. A fixed one leaves no
place for a new kind of requirement, such as row/columnar conversions, if a
downstream project needs one.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
