zhuqi-lucas opened a new pull request, #25585:
URL: https://github.com/apache/datafusion/pull/25585
## Which issue does this PR close?
POC for the design discussion in #25572 (follow-up to #25355 and #25356).
Opened as a draft for discussion; if the direction holds I would split it into
separate reviewable PRs (see "Sequencing" below).
## What it builds
Two defaulted methods on `PhysicalOptimizerRule`, each naming a property of
the rule itself. The chain keeps full authorship of when and how often a rule
is called; the rule only states what may be done with those calls. With no
declarations, behavior is byte-identical to main.
```rust
/// Output is a pure function of the plan and the config.
/// Enables: skip a call whose input this rule has already been OBSERVED
/// to leave unchanged in this optimization run. Never re-applies anything.
fn deterministic(&self) -> bool { false }
/// May be applied to its own output (f(f(x)) == f(x)).
/// Enables: run this call site to convergence.
fn idempotent(&self) -> bool { false }
```
Plus `PhysicalPlanSignature` (node count + hash of the rendered plan and
each node's partitioning/orderings/equivalences; the physical analog of
`LogicalPlanSignature`, needed because `ExecutionPlan` implements neither
`Hash` nor `Eq`), and the dispatcher: a deterministic rule handed an observed
fixpoint is skipped (pointer fast path, then a full-fingerprint compare, full
rather than hashed because a collision would skip an enforcement pass that had
work to do); an idempotent rule runs to convergence at its call site (signature
`HashSet`, stopping on fixpoint or first cycle revisit); everything else runs
exactly once, in list order.
`EnsureRequirements` declares `deterministic()`. Nothing declares
`idempotent()`, and the findings below are why.
## What the POC found
Three empirical results from running the full sqllogictest suite against
speculative re-application (the earlier form of this branch partitioned the
chain and looped every segment):
1. **`FilterPushdown` is not idempotent**: re-application conjuncts the same
predicate onto the source again (`k < 10 AND k < 10 AND k < 10` after three
passes; 63 failures across 21 files, one signature).
2. **A second `PushdownSort` application returns wrong rows**:
`sort_pushdown.slt:2487` returns 4,5,6 for an `ORDER BY id ASC LIMIT 3` whose
answer is 1,2,3, because the re-push loses the cross-group merge. Probably
reachable today by any chain that lists the rule twice. Will file separately
with the repro.
3. **Even `EnsureRequirements` cannot declare `idempotent()`**, despite
being the one rule whose specification promises it: declaring it changed 35
plans across eight slt files, because a second application rewrites
sort-preserving merges to other members of the ordering equivalence class, in
one case replacing a `CoalescePartitionsExec` with a costlier merge. The
declaration is withdrawn with that evidence in a comment; fixing the rewrite is
the gate.
Every rule tested against the idempotence contract failed it, which is why
the convergence half ships dormant, and why `deterministic()` is the half that
pays now: chains that interleave rewrites with enforcement re-run enforcement
after every rewrite, and on most plans most rewrites do not fire. On the
downstream chain that motivated this line of work, 4 of 6 enforcement calls are
byte-identical no-ops at 79% of physical optimization time; the fork-carried
predecessor of this mechanism measured -29.3% physical optimization wall with
byte-identical `EXPLAIN VERBOSE`.
## Testing
- Full sqllogictest suite green with `EnsureRequirements` declaring
`deterministic()` (the default chain schedules it once, so the skip is
exercised by unit tests; parity holds).
- Nine unit tests across the two mechanisms: observed-fixpoint skip through
both the pointer and the rebuilt-tree fingerprint path, authored call counts
preserved for undeclared rules, convergence to fixpoint in needed-plus-one
applications, cycle termination on first revisit, one application at an
already-converged call site. The load-bearing comparisons are mutation-verified
(breaking them turns the tests red).
## Sequencing, if the direction holds
1. `PhysicalPlanSignature` + `deterministic()` + the skip, with the
`EnsureRequirements` declaration: the part with a user today.
2. `idempotent()` + per-call-site convergence: dormant until rules can earn
declarations (each gated on a fix plus a regression test).
3. The `PhysicalAnalyzerRule` phase split from #25355/#25572: structural,
removes the reason chains hand-repeat enforcement at all.
--
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]
