jayzhan211 opened a new pull request, #26853:
URL: https://github.com/apache/datafusion/pull/26853
## Which issue does this PR close?
- None. This is a refactor of how `EquivalenceProperties` checks sort
requirements; it fixes no reported bug.
## Rationale for this change
The planner removes a sort when it can prove that its input is already
sorted the required way. For a
requirement like `[a, b]`, it first checks `a`. Then, since `b` only has to
be sorted among rows that tie on `a`,
it treats `a` as a constant: it clones the `EquivalenceProperties`, adds `a`
with `add_constants`, and checks `b`
against the clone.
This has three costs:
- **Planning time.** Every check with more than one key clones the
properties. Checks with four keys are 2-3x
faster without the clone (benchmarks below).
- **Plans depend on hash map order.** The clone finds orderings that follow
from the satisfied key through a side
effect of `add_constants` (it strips constants from the stored orderings
and re-runs ordering discovery once,
over the leading expressions in hash map order). For example, with
ordering `[k, x, y, z]`,
`x = CAST(y AS BIGINT)` and `y = CAST(z AS INT)`, the requirement `[k, z]`
holds. `main` proves it in about half
of the runs when a second ordering `[y, w]` exists, and never without it,
so the same query can plan with or
without a sort.
- **The trick is written three times.** `ordering_satisfy_requirement` and
`common_sort_prefix_length` are two
copies of the same loop, and `find_longest_permutation` does its own clone
plus `add_constants`. A "constant"
that only means "satisfied so far" is hard to tell apart from a real
constant when reading the code.
## What changes are included in this PR?
- First commit: benchmark cases in
`datafusion/physical-expr/benches/equivalence_properties.rs` for
`find_longest_permutation`, window-shaped orderings and a deeply nested
sort key, so they can run on `main` too.
- New `properties/walk.rs` with `Walk`: one pass along the keys that *pins*
each satisfied key (and its
equivalence class), and keeps, for each ordering, its *head*: the first
expression that is not fixed (pinned,
constant, or computed only from fixed expressions). After each pin, the
walk adds the orderings that the new
heads imply, until none is new.
- `ordering_satisfy_requirement` and `common_sort_prefix_length` both call
`Walk::sorted_prefix_len`.
`find_longest_permutation` pins found expressions in a `Walk` instead of
cloning and adding constants (and skips
the pins after its last round, which nothing reads). `get_expr_properties`
reads through a `Walk` with nothing
pinned.
- `sorted_prefix_len` accepts a key if any head is that key in the required
direction. `main` only looked at the
first ordering the key heads, in its stored order (see the plan
differences).
- Removed: `add_satisfied_key_constants` and the free function
`update_properties` (now a method of `Walk`).
- The body of `discover_new_orderings` is now `implied_ordering`, shared
with the walk, with a doc that says why the
implied ordering holds. The body of
`OrderingEquivalenceClass::is_expr_partial_const` is now `is_partial_const`,
shared with the walk.
- `OrderingEquivalenceClass::get_options` and `is_expr_partial_const` are no
longer called inside DataFusion; they
stay as public API.
- Last commit: `is_partial_const` now says what it checks, an expression
leading one ordering in some direction
and another in the exact reverse, instead of removing `(descending,
nulls_first)` tuples from two hash sets.
Its doc says why this exists: a whole-partition window aggregate, such as
`SUM(x) OVER (PARTITION BY k)`,
records that it is constant per `k` by adding `[k, w]` in all four
directions of `w`.
The `EquivalenceProperties` the walk reads never changes during a check.
### Plan differences
No plan changes in the existing tests (see testing). On hand-built inputs,
this PR proves an ordering where
`main` does not:
| Input | `main` | This PR |
|---|---|---|
| The chain of casts above | satisfied in some runs (hash map order) |
satisfied |
| Column `x` is the constant `5`, ordering `[k, b % 5]`,
`find_longest_permutation([5, k, b % 5])` (e.g. `GROUP BY 5, k, b % 5`) | `5,
k`: pinning the literal `5` adds it to `x`'s class, so `b % 5` normalizes to `b
% x` and no longer matches | `5, k, b % 5` |
| `a` leads orderings in two directions that are not opposite, such as `a
DESC NULLS FIRST` declared before `a ASC NULLS FIRST`, from the start or after
a satisfied `k`; requirement `[a ASC NULLS FIRST]` or `[k, a ASC NULLS FIRST]`
| depends on the order it stores orderings in (4 of the 6 declaration orders in
one example) | satisfied |
Each extra ordering really holds, so these can only remove sorts.
One case is worse: with orderings like the last row's, a requirement on an
expression *computed from* `a`, such as
`[k, CAST(a AS BIGINT) ASC NULLS FIRST]`. Both versions give `a` one
direction, from whichever ordering comes
first: `main` in its stored order, this PR in declaration order. In 2 of the
6 declaration orders of one example
`main` proves it and this PR does not, so a sort is kept. The reverse never
happens.
## What is the testing strategy for this PR?
- New unit tests in `walk.rs`: an ordering found only after pinning
(`ordering_found_after_pinning`), the chain of
casts above (`chained_orderings_found_after_pinning`, fails on `main`),
and the two-direction case
(`any_head_in_required_direction`). New unit test
`test_is_expr_partial_const` in `ordering.rs`; before it, no
test failed when `is_partial_const` always returned `false`.
- All existing tests pass unchanged.
- Checked locally, not part of this PR:
- Side by side: with the old algorithms kept next to the walk, every call
to the four entry points ran both and
logged any difference. The only difference was the chain-of-casts unit
test above, over the
`datafusion-physical-expr`, `datafusion-physical-plan` and
`datafusion-physical-optimizer` unit tests,
`core_integration`, all sqllogictests, and the equivalence fuzz tests
(`--features extended_tests`).
- Against data: a randomized test built small sorted tables, declared only
properties that hold on them
(orderings, cast equalities, constants, window-style orderings), and
checked every answer of the four entry
points against the rows. Over 9.6 million cases, neither version claimed
an ordering the rows do not have, and
both returned the same errors. The cases where `main` and this PR differ
are the ones listed above.
- The old and new `is_partial_const` agree on every sequence of up to 6
sort directions over two expressions
(299,593 sequences).
Benchmarks: `cargo bench -p datafusion-physical-expr --bench
equivalence_properties` with the first commit's cases on
both sides, `main` vs this PR, 5 alternating rounds, medians, time of this
PR / time of `main` (below 1 is faster).
Columns are the number of equivalence classes.
| Check | 2 | 8 | 32 |
|---|---|---|---|
| `ordering_satisfy`, 1 key | 0.81 | 0.82 | 0.81 |
| `ordering_satisfy`, 1 key, unsatisfied | 0.83 | 0.84 | 0.83 |
| `ordering_satisfy`, 4 keys | 0.37 | 0.35 | 0.29 |
| `ordering_satisfy_requirement`, 1 key | 0.77 | 0.76 | 0.76 |
| `ordering_satisfy_requirement`, 4 keys | 0.37 | 0.35 | 0.30 |
| `extract_common_sort_prefix`, 4 keys | 0.38 | 0.36 | 0.30 |
Other shapes:
| Case | Ratio |
|---|---|
| `find_longest_permutation`, 1 expression (2 / 32 classes) | 0.13 / 0.07 |
| `find_longest_permutation`, 5 expressions, one found per round (2 / 32
classes) | 0.44 / 0.38 |
| `W` window aggregates over `PARTITION BY k`, i.e. `[k, w_i]` in four
directions per window; requirement `[k, w_1]` (`W` = 4 / 16 / 32) | 0.20 / 0.11
/ 0.08 |
| Requirement `[c0, e, c1]` with `e = c1 + 1 + ... + 1` nested `d` deep (`d`
= 4 / 16 / 32) | 0.81 / 1.20 / 1.41 |
The last row is the one shape that is slower. For every node of `e`, both
versions check whether it is constant by
looking each sub-expression up in a hash map, which hashes the whole
sub-expression, so the cost grows with the
cube of the depth. This PR also looks each one up in its set of pinned
expressions, which `main` does not have.
Sort keys nested this deep are rare: at depth 4 this PR is faster.
## Are there any user-facing changes?
No public API change. Plans differ only in the cases listed above.
--
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]
