jayzhan211 opened a new pull request, #24800:
URL: https://github.com/apache/datafusion/pull/24800
## Which issue does this PR close?
- Closes #.
## Rationale for this change
Physical planning asks "is this ordering already satisfied?" constantly —
sort
removal, `EnforceSorting`, `EnforceDistribution`, and the requirement checks
for
windows, joins and aggregates all call into
`EquivalenceProperties::ordering_satisfy`, `ordering_satisfy_requirement` and
`extract_common_sort_prefix`.
Each of those calls deep-clones the entire `EquivalenceProperties` — every
equivalence class, every equivalent ordering, and the normalized ordering
cache —
before doing anything else, even when it never modifies the copy.
The clone exists for a real reason: as the check walks a multi-key ordering
left
to right, it registers each satisfied key as a constant so the next key is
evaluated within that key's tie group. That mutates state, so it needs its
own
copy. But two cases pay for it and get nothing back:
1. **A single-key check never mutates anything.** There is no "next key" to
set up
for, so the whole clone is wasted. This is the most common shape of these
calls.
2. **The last key of *any* check registers constants nobody reads.** After
the
final key is verified, the code still calls `add_satisfied_key_constants`,
which rebuilds the ordering cache and re-runs ordering discovery — and
then the
object is dropped.
## What changes are included in this PR?
Two changes in `EquivalenceProperties`, to `ordering_satisfy_requirement` and
`common_sort_prefix_length` (the latter backs `ordering_satisfy`,
`extract_common_sort_prefix` and `reorder`):
- **Clone on first write instead of up front.** The loop borrows `self` and
clones
only when it actually needs to register a constant. Single-key checks never
clone at all.
- **Skip the registration after the last key.** Nothing reads it.
Plus a new criterion benchmark, `equivalence_properties`, covering these
entry
points.
This only changes *when* the copy is made — the results of these functions
are
unchanged.
## Metrics
Apple M4 Pro, rustc 1.97.0, criterion. All changes significant at p = 0.00.
Properties under test: 3 equivalent orderings (`[c0,c1,c2,c3]`, `[c4,c5]`,
`[c6]`)
and a varying number of equivalence classes.
**At 8 equivalence classes:**
| benchmark | before | after | change |
|---|---:|---:|---|
| `ordering_satisfy` — 1 key | 2.72 µs | 0.41 µs | **−84.9%** |
| `ordering_satisfy` — 1 key, unsatisfied | 1.47 µs | 0.41 µs | **−72.5%** |
| `ordering_satisfy_requirement` — 1 key | 2.70 µs | 0.36 µs | **−86.3%** |
| `ordering_satisfy_requirement` — 4 keys | 7.15 µs | 6.07 µs | −13.8% |
| `ordering_satisfy` — 4 keys | 6.99 µs | 6.20 µs | −11.6% |
| `extract_common_sort_prefix` — 4 keys | 7.22 µs | 6.38 µs | −9.2% |
**How it scales** (`ordering_satisfy`, 1 key):
| equivalence classes | before | after | change |
|---:|---:|---:|---|
| 2 | 2.44 µs | 0.43 µs | −82.5% |
| 8 | 2.72 µs | 0.41 µs | −84.9% |
| 32 | 4.63 µs | 0.41 µs | **−90.8%** |
Reading the tables: for an *N*-key check the work goes from
`1 clone + N registrations` to `(N > 1 ? 1 : 0) clones + (N − 1)
registrations`.
- **1-key checks** drop both the clone and the registration. Note the "after"
column is flat at ~0.41 µs regardless of how many equivalence classes
exist —
with the clone gone, the check no longer scales with the size of the
equivalence group at all. The "before" column does, which is why the win
grows
from −82% to −91%.
- **Multi-key checks** still clone once and save one of *N* registrations.
Since a
registration rebuilds the ordering cache and re-runs ordering discovery,
that
single saved call is worth 9–14% here, rising to −37.8% for `4_keys` at 32
classes.
### Reproducing
The benchmark is included in this PR, so reverting just the one source file
gives
you the baseline:
```bash
# baseline: this PR's parent version of the file, with the new benchmark kept
git checkout HEAD^ --
datafusion/physical-expr/src/equivalence/properties/mod.rs
cargo bench -p datafusion-physical-expr --bench equivalence_properties --
--save-baseline before
# with the change
git checkout HEAD --
datafusion/physical-expr/src/equivalence/properties/mod.rs
cargo bench -p datafusion-physical-expr --bench equivalence_properties --
--baseline before
```
The second run prints criterion's own `change: [...] (p = ...)` line per
benchmark.
## Are these changes tested?
No new correctness tests: this does not change what any of these functions
return, so existing coverage is the right check. Covered by the `equivalence`
unit tests in `datafusion/physical-expr` and, for plan-shape regressions, by
sqllogictest — these functions decide whether a `SortExec` can be removed,
so a
behavior change would surface as a diff in an `EXPLAIN` plan.
Full workspace suite
(`--features
avro,json,backtrace,extended_tests,recursive_protection,parquet_encryption`):
10,981 passed, 0 failed, and all 505 sqllogictest files pass.
`./dev/rust_lint.sh`
is clean.
## Are there any user-facing changes?
No. No public API or behavior changes — planning is just faster.
--
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]
