fix: do not fail when an expression's ordering cannot be derived - #26884

… constants (apache#26853)

## Which issue does this PR close?

- None. This is a refactor of how `EquivalenceProperties` checks sort
requirements. It also makes the planning that
depends on hash map order, described below, deterministic; there is no
issue for that.

## 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, and every
`find_longest_permutation` call, clones the
properties. Without the clone, checks with four keys are 2-4x faster and
`find_longest_permutation` 2-18x
  (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.

This PR keeps the idea, but records the satisfied keys in a separate
`SortKeyWalk`, which *pins* them, instead of changing
a copy of the `EquivalenceProperties`.

## What changes are included in this PR?

**How the walk works.** `SortKeyWalk`, in the new file
`properties/walk.rs`, checks the keys of a requirement one by one
and keeps a set of *pinned* expressions: the keys satisfied so far.
Within rows that tie on the pinned keys, a pinned
expression has a single value, so every ordering can skip it. For each
ordering, the walk keeps its *head*: its first
expression that is not fixed (a literal, a constant, pinned, or computed
only from fixed expressions). A key is
satisfied if it is fixed, if it is a head in the required direction, or,
as before, if its order follows from such
expressions (e.g. `CAST(a AS BIGINT)` when `a` is a head).

For example, with orderings `[a, b]` and `[b, c]` and the requirement
`[a, b, c]`: `a` heads `[a, b]`, so it is
satisfied and pinned. `b` now heads both orderings, so it is satisfied
and pinned. `[a, b]` is used up, `[b, c]` now
has head `c`, and `c` is satisfied.

Pinning a key also pins its equivalence class and, as before, the
arguments it determines (`a` for
`CAST(a AS BIGINT)`). After each pin, the walk adds the orderings that
the new heads imply (the rule of
`discover_new_orderings`), until none is new. The walk never changes the
`EquivalenceProperties` it reads.

**Commits.**

1. 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.
2. The walk:
- `ordering_satisfy_requirement` and `common_sort_prefix_length` both
call `SortKeyWalk::sorted_prefix_len` instead of
each cloning the properties and adding constants.
`find_longest_permutation` pins found expressions in a
`SortKeyWalk` instead of cloning (and skips pinning once every
expression is found). `get_expr_properties` reads
     through a `SortKeyWalk` with nothing pinned.
- One rule is new: a key is also satisfied if *any* head is that key in
the required direction. `main` looked
only at the first ordering the key leads (see the plan differences).
- Removed `add_satisfied_key_constants` (its job is now
`SortKeyWalk::pin_key`). The free function `update_properties`
is now a method of `SortKeyWalk`. The per-ordering check in
`discover_new_orderings` is now `implied_ordering`, and
the body of `OrderingEquivalenceClass::is_expr_partial_const` is now
`is_partial_const`; the walk shares both.
- `OrderingEquivalenceClass::get_options` and `is_expr_partial_const`
are no longer called inside DataFusion;
     they stay as public API.
- The walk follows two rules that landed on `main` while this PR was
open: properties that cannot be derived
are unknown rather than an error (apache#26884), and a volatile expression is
never fixed, while a leaf that reports
itself as a singleton, such as an uncorrelated scalar subquery, is
(apache#26836).
3. `is_partial_const` now says what it checks: the expression leads one
ordering in some direction and another in
the exact reverse (`main` removed `(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`.
4. Review follow-ups: `Walk` is renamed `SortKeyWalk`, and
`find_longest_permutation` pins what it finds in normal
form (a new row under plan differences). New unit tests, and the
benchmarks check each answer before timing it.
5. Randomized tests in `datafusion/core/tests/fuzz_cases/equivalence`
with cast equalities and whole-partition window
   orderings (see testing).
6. A unit test for the walk's rules from apache#26836.

**Where to start reading:** the `SortKeyWalk` doc comment, then
`SortKeyWalk::sorted_prefix_len` and
`SortKeyWalk::pin`.

**Risk:** if the walk claims an ordering the data does not have, a
needed sort is removed and results are wrong.
The randomized tests compare every answer with real rows to test exactly
this.

### 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])` | `5, k`: adding the literal
`5` as a constant puts it into `x`'s class, so `b % 5` normalizes to `b
% x` and no longer matches | `5, k, b % 5` |
| `b = c`, ordering `[a + b, d]`, `find_longest_permutation([a + c, d])`
| `a + c`: it pins `a + c` as given, which does not match the stored `a
+ b` | `a + c, d` |
| `a` leads orderings in two directions that are not opposite, e.g. `[a
DESC NULLS FIRST, k, c]`, `[k, a DESC NULLS FIRST, c]` and `[k, a ASC
NULLS FIRST]`; requirement `[k, a ASC NULLS FIRST]` | satisfied in 4 of
the 6 declaration orders | satisfied in all 6 |

Each extra ordering really holds, so these can only remove sorts.

One case is worse: the same orderings with a requirement on an
expression *computed from* `a`,
`[k, CAST(a AS BIGINT) ASC NULLS FIRST]`. For a computed expression,
both versions give `a` one direction, from the
first ordering `a` leads. `main` looks at its clone, where removing `k`
makes the first two orderings duplicates and
deduplication reorders the rest; this PR looks at the orderings as
stored. `main` proves it in 4 of the 6
declaration orders and this PR in 2, so in 2 of them a sort is kept that
`main` removes. This PR never proves it
where `main` does not.

## 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`, which fails without the any-head
check above; `main` passes it), the partial
constant check of a computed key after a pin
(`partial_constant_after_pinning`, fails without that check), and the
two `find_longest_permutation` rows above
(`find_longest_permutation_with_literal` fails on `main`,
`find_longest_permutation_pins_normal_form` fails without the normal
form), and volatile functions and scalar
subqueries (`volatile_function_and_scalar_subquery_keys`, fails without
either rule from apache#26836). The rule from
apache#26884 is covered by its own tests, which now run through the walk. New
unit test `test_is_expr_partial_const`
  in `ordering.rs`.
- New randomized tests in `datafusion/core/tests/fuzz_cases/equivalence`
(run with `--features extended_tests`):
`test_ordering_satisfy_with_casts_and_windows_random` and
`test_find_longest_permutation_with_casts_and_windows_random`.
They build sorted tables and declare only properties that hold on them:
a lossy and a lossless cast equality,
`[k, w]` in all four directions of a `w` that has one value per `k`, a
second independent ordering and a constant.
Every ordering claimed or found must hold on the rows, and orderings
that follow from the declared properties
must be proven. They also pass on `main`. Removing the walk's partial
constant check, or the orderings it adds
after a pin, makes them fail, while the existing equivalence fuzz tests
still pass. They take 1-2 seconds each in
  a debug build.
- 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 (`ordering_satisfy_requirement`,
`common_sort_prefix_length`, `find_longest_permutation`,
`get_expr_properties`) 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, at a larger scale than the randomized tests above: small
sorted tables with only true properties,
every answer of the four entry points checked 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

From the benchmark bot on this PR (`c4a-highmem-16`, Neoverse-V2).
`equivalence_properties` compares this PR
with its first commit, which is `main` plus the new benchmark cases.
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.85 | 0.85 | 0.85 |
| `ordering_satisfy`, 1 key, unsatisfied | 0.87 | 0.87 | 0.87 |
| `ordering_satisfy`, 4 keys | 0.42 | 0.38 | 0.28 |
| `ordering_satisfy_requirement`, 1 key | 0.78 | 0.77 | 0.77 |
| `ordering_satisfy_requirement`, 4 keys | 0.39 | 0.36 | 0.26 |
| `extract_common_sort_prefix`, 4 keys | 0.42 | 0.38 | 0.28 |

Other shapes:

| Case | Ratio |
|---|---|
| `find_longest_permutation`, 1 expression (2 / 32 classes) | 0.12 /
0.06 |
| `find_longest_permutation`, 5 expressions, one found per round (2 / 32
classes) | 0.48 / 0.35 |
| `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.16
/ 0.08 / 0.06 |
| Requirement `[c0, e, c1]` with `e = c1 + 1 + ... + 1` nested `d` deep
(`d` = 4 / 8 / 16 / 32); `+` may overflow, so `e` is unordered and both
versions stop at `e` | 0.79 / 0.99 / 1.13 / 1.28 |

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 roughly 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: up to depth 8 this PR is as fast or
faster. Measured locally (laptop, where
the ratios at depth 16 and 32 run a bit higher than on the bot), a
right-nested key `1 + (1 + (... + c1))` and a `+`
with overflow checks, where `e` is ordered and the check goes on to
`c1`, give the same ratios as this row.

After rebasing on apache#26884 and apache#26836, a local run of
`equivalence_properties` against the new `main` (laptop, 5 rounds)
gives the same picture: 0.31 to 0.88 for the checks in the first table,
0.08 to 0.49 for the other shapes, and
0.82 / 1.00 / 1.22 / 1.45 for the deep key.

Planning time end to end (`sql_planner`, this PR / `main`): TPC-H 1.00,
TPC-DS 1.00, ClickBench 1.01. The physical
planning cases range from 0.95 (sorted unions of Int64 inputs) to 1.03.
The logical planning cases, which run no code
this PR changes, range from 0.97 to 1.05, which is the noise of this
runner.

## Are there any user-facing changes?

No public API change. Plans differ only in the cases listed above.