2010YOUY01 opened a new pull request, #26360:
URL: https://github.com/apache/datafusion/pull/26360
## Which issue does this PR close?
<!--
We generally require a GitHub issue to be filed for all bug fixes and
enhancements and this helps us generate change logs for our releases. You can
link an issue to this PR using the GitHub syntax. For example `Closes #123`
indicates that this PR will close issue #123.
-->
- Closes #.
## Rationale for this change
<!--
Why are you proposing this change? If this is already explained clearly in
the issue then this section is not needed.
Explaining clearly why changes are proposed helps reviewers understand your
changes and offer better suggestions for fixes.
Please explain the problem you are trying to solve in terms of the
user-visible
behavior, rather than the implementation.
For example, "The code in `foo.rs` doesn't handle nulls" is a symptom of the
implementation. "COUNT(DISTINCT) returns wrong results when the column
contains
nulls" is the user-visible problem.
-->
The default physical optimizer pipeline works for the optimizations
implemented in DataFusion core. However, there are many hidden assumptions
between optimizer rules that make the pipeline work as a whole (e.g., rule A
must run before rule B to produce a valid plan).
These implicit constraints make extensions harder, whether adding new rules
within DataFusion core or implementing custom pipelines downstream.
This PR introduces **explicit invariant regions** to make these hidden
constraints visible and verifiable, making the optimizer easier to understand,
extend, and maintain.
Note that this PR does not introduce new constraints. I think of this
primarily as a **"removing uncertainty"** step. The assumptions already exist;
this PR provides a mechanism to surface them so that:
1. Developers can understand the expectations between optimizer rules.
2. We can automatically test whether rules preserve those expectations.
3. Extensions can make more informed decisions about where to insert or
rearrange rules.
The tradeoff is a certain learning curve for this mechanism. After
prototyping the idea, I feel that once we become familiar with the concept, it
can make long-term maintenance easier. However, it definitely looks confusing
at first glance, and I'm still thinking about how to improve this part.
(Note: The implementation is currently underdocumented; most of the ideas
are explained in this writeup.)
### Two Types of Constraints
This section explains two types of constraints, with one example each. The
following figure illustrates two invariant regions in an example optimizer
pipeline, which will be explained further below.
```text
Invariant Regions
Rule List Aggr Req
--------------------------------------------------------
InitialPhysicalPlanner
+-- BEGIN
... |
LimitedDistinctAggregation |
... |
+-- END
EnsureRequirements
+-- BEGIN
... |
+-- END
ExtensionRule1 (inactive)
ExtensionRule2 (inactive)
EnsureRequirements (restore)
+-- BEGIN
... |
SanityCheckPlan |
+-- END
```
- **Region 1, CanonicalAggregatePlan (Aggr):** Maintains canonical
aggregation shapes in this region, the rules inside this region can kept
simpler by only handling the canonical aggregate shape
- **Region 2, InputRequirementsSatisfied (Req):** Ensures execution
requirements remain satisfied. The example demonstrated temporary turning
off/on in the middle to make extension easier.
### Type I: Optimization-Coverage Constraints (Soft)
#### Progressive refinement in the optimizer pipeline
The default optimizer pipeline is a progressive refinement process, where
the possible plan shapes vary across stages.
For example:
- At rule 1, a hash join might have only one canonical representation.
- At rule 20, the same logical join might have five possible physical
representations.
A rule that rewrites joins could be much simpler when placed at an earlier
stage.
Requiring every rule to handle every possible representation, regardless of
its position, can unnecessarily bloat the implementation of earlier rules.
#### Making soft constraints explicit
Built-in rules already rely on such canonicalization assumptions, allowing
them to match only canonical plan shapes and keep their implementations simple.
Soft constraints provide a mechanism to make these assumptions explicit and
verifiable, so custom optimizer pipelines can either:
- Follow the constraints to preserve the same optimization coverage.
(Another interpretation is that these constraints help extension rules find
suitable positions in the pipeline.)
- Opt out of the constraints, accepting the possibility of losing
optimization coverage from built-in rules.
#### Example: LimitedDistinctAggregation
See https://github.com/apache/datafusion/pull/26069 for a concrete example
of how relying on a canonical aggregation shape can simplify an optimizer rule.
The corresponding invariant region would be:
```text
CanonicalAggregatePlan
- Established: After InitialPhysicalPlanner
- Ends: After LimitedDistinctAggregation
```
This is illustrated as Region 1 (Aggr) in the figure above.
### Type II: Execution-Validity Constraints (Hard)
These constraints are required for correct execution. Extensions must
preserve them to ensure that plans remain runnable.
#### Example: EnsureRequirements
Consider a partitioned hash join.
Before enforcing requirements:
```text
HashJoinExec(mode=Partitioned, on=[t1.k = t2.k])
Scan(t1) <-- Not hash-partitioned on t1.k
Scan(t2) <-- Not hash-partitioned on t2.k
```
The plan represents the intended computation, but its children do not
satisfy the hash join's distribution requirements.
After `EnsureRequirements`:
```text
HashJoinExec(mode=Partitioned, on=[t1.k = t2.k])
RepartitionExec(hash(t1.k), N)
Scan(t1)
RepartitionExec(hash(t2.k), N)
Scan(t2)
```
Now the join's distribution requirements are satisfied.
We can express this as an invariant region, as shown in the figure above.
Within this region, every optimizer rule must preserve the invariant. If a
rule violates it, the checker reports the failure immediately after that rule
(when validation is enabled).
For extensions, the responsibility is explicitly one of the following:
1. Preserve the existing ordering/distribution guarantees.
2. If a transformation breaks those guarantees, repair the plan internally.
3. Alternatively, explicitly leave the region, perform transformations
without those guarantees, and restore them before reentering. (demonstrated in
the figure above)
## What changes are included in this PR?
<!--
There is no need to duplicate the description in the issue here, but it is
sometimes worth providing a summary of the individual changes in this PR.
-->
1. Add a configuration option, `validate_optimizer_invariants`, to control
invariant checking. Use a feature flag to enable validation in tests/CI while
skipping it in release builds.
2. The main change is in `physical-optimizer/src/optimizer.rs`, introducing
invariant regions into the existing optimizer rule list.
The PoC implements the following regions, which are not exactly the same as
the examples above:
- **NoEmbeddedProjection:** Soft constraint for projection shape
canonicalization.
- **HashJoinModeResolved:** Soft constraint for hash join mode resolution.
- **InputRequirementsSatisfied:** Hard constraint; see the example above.
One thing that remains implicit is **which optimizer rules establish the
invariants**.
For example, in the figure above, the canonical aggregation region is
established by initial physical planning, while the
`InputRequirementsSatisfied` region is established by `EnsureRequirements`.
Therefore, downstream custom optimizer pipelines must follow the same
assumptions and manually declare these regions after the corresponding rules
have established their invariants.
## What is the testing strategy for this PR?
<!--
We typically require tests for all PRs in order to:
1. Prevent the code from being accidentally broken by subsequent changes
2. Serve as another way to document the expected behavior of the code
Briefly describe how this PR is tested, and point to the specific tests you
added. For example: 'This new feature is covered by the `sqllogictest` cases
added in `foo.slt`'.
If this PR does not add tests, explain why. For example, if the change is
already covered by existing tests, please mention it.
You should also check the `codecov` bot reply on this PR to confirm the
changed code is exercised.
-->
## Are there any user-facing changes?
<!--
If there are user-facing changes then we may require documentation to be
updated before approving the PR.
If there are any breaking changes to public APIs, please add the `api
change` label.
-->
--
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]
