feat: Optimize ORDER BY by Pruning Functionally Redundant Sort Keys - #21362

…pache#21362)

## Which issue does this PR close?

- Closes apache#21361 .

## Rationale for this change

This PR adds functional-dependency-based simplification for `ORDER BY`
clauses. When an earlier sort key already functionally determines a
later key, the later key is redundant and can be removed without
changing query semantics. This reduces unnecessary sorting work and
avoids carrying extra sort keys through planning and execution.

## What changes are included in this PR?

This PR extends the existing functional dependency utilities with a
helper for pruning redundant sort keys, and wires that helper into
`eliminate_duplicated_expr` so `Sort` nodes can be simplified during
optimization. It also adds regression coverage for both the positive
case, where a trailing sort key is removed, and the negative case, where
sort order prevents pruning.

## Are these changes tested?

Yes. I added unit tests covering:
- removal of a functionally redundant trailing `ORDER BY` key
- preservation of ordering when the dependent column appears before its
determinant

I also ran `cargo test -p datafusion-optimizer eliminate_duplicated_expr
-- --nocapture` successfully, and `cargo fmt --all` passes.

## Are there any user-facing changes?

Yes, but only in query planning behavior. Some queries with redundant
`ORDER BY` keys may produce simpler plans and run more efficiently.
There are no public API changes.

---------

Co-authored-by: Andrew Lamb <[email protected]>

…pache#26150)

## Which issue does this PR close?

- None yet. The bug and its repro are below.

## Rationale for this change

If `x` is a primary key, the optimizer treats `CAST(x AS ...)` as `x`.
It then drops the other ORDER BY or GROUP BY keys that `x` determines,
so the query returns wrong results:

```sql
CREATE TABLE t (x DOUBLE, y VARCHAR, PRIMARY KEY (x))
  AS VALUES (1.1, 'b'), (1.2, 'a'), (2.1, 'c');

SELECT x, y FROM t ORDER BY CAST(x AS INT), y;
-- main:     1.1 b / 1.2 a / 2.1 c   (`y` is dropped from the sort)
-- expected: 1.2 a / 1.1 b / 2.1 c

SELECT CAST(x AS INT) k, count(*) n FROM t GROUP BY CAST(x AS INT), y;
-- main:     (1, 2) / (2, 1)         (`y` is dropped from the grouping)
-- expected: (1, 1) / (1, 1) / (2, 1)

SELECT y, count(*) FROM t GROUP BY CAST(x AS INT);
-- main:     accepted
-- expected: Error: Column in SELECT must be in GROUP BY or an aggregate function
```

`CAST(x AS INT)` is named `t.x`, because casts are left out of
expression names. The functional dependency helpers matched GROUP BY and
ORDER BY expressions to key columns by comparing names, so the cast
matched the key `t.x`.

The same happens with `TRY_CAST`, with a `UNIQUE NOT NULL` key, and with
a key that comes from an inner GROUP BY. The ORDER BY case comes from
the sort key pruning added in apache#21362 (54.0.0).

## What changes are included in this PR?

- **Index-based helpers.** The four helpers in
`functional_dependencies.rs` now take, for each GROUP BY or ORDER BY
expression, the index of the input field it references (`Option<usize>`)
instead of its name. A computed expression has no index, so it never
matches a key. The new `datafusion_expr::utils::passthrough_field_index`
returns the index for a column reference, aliased or not.
- **One GROUP BY list.** The dependencies of an `Aggregate`'s output use
the GROUP BY list that its schema is built from
(`grouping_set_to_exprlist`). Before, they used a list de-duplicated by
name, which merged `CAST(x AS INT)` and `x`.
- **Projections resolve columns.** A projection now finds each input
column with `DFSchema::index_of_column_by_name` instead of comparing
`"qualifier.name"` strings. The unit test
`projection_duplicate_flattened_name_uses_first_input_index` asserted
the old string behaviour: a column named `"orders.id"` got the
dependency of the different field `orders.id`. It is renamed and now
asserts that each column keeps its own dependency.

## What is the testing strategy for this PR?

- **New tests.** Section 6 of `functional_dependencies.slt` has one
query for each user of the helpers:
  - ORDER BY pruning;
  - GROUP BY pruning;
  - `Aggregate` output dependencies;
  - GROUP BY expansion.

On `main`, each of these returns a wrong result or accepts an invalid
query. The same queries also run over `TRY_CAST` on a `UNIQUE NOT NULL`
key and over a key from an inner GROUP BY. One more query pins that a
widening cast (`INT` to `BIGINT`) of a key does not carry its
dependencies.
- **New unit tests.** `passthrough_field_index` resolves an ambiguous
unqualified column to nothing. A key that is in the GROUP BY list two
times (`id, id AS k`, builder API only) still determines the row.
- **Existing tests** are unchanged, apart from the rewritten unit test.
- **Planning time.** Planning is not slower. The `sql_planner` TPC-H and
TPC-DS benchmarks, whose tables have primary keys, are about 5% faster,
because the new code no longer renders expression names.

<details><summary>Benchmark numbers (3 interleaved runs per
side)</summary>

| Benchmark | `main` | This PR |
|---|---|---|
| `physical_plan_tpch_all` | 17.3 / 17.8 / 18.0 ms | 16.1 / 17.0 / 17.2
ms |
| `physical_plan_tpcds_all` | 291 / 300 / 301 ms | 276 / 280 / 282 ms |

</details>

## Are there any user-facing changes?

- **Results.** The queries above return correct results.
- **Rejected queries.** Only a column reference to a key carries its
dependencies. A query that selects other columns while grouping by an
expression over the key is now rejected, even when the expression keeps
distinct values distinct, like `GROUP BY CAST(x AS BIGINT)` over an
`INT` key. `main` accepts it and its result is correct. PostgreSQL and
DuckDB reject it too. Group by the key column itself instead.
- **API change.** Four `pub` functions in `datafusion_common` take
`&[Option<usize>]` instead of `&[String]`:
  - `aggregate_functional_dependencies`
  - `get_target_functional_dependencies`
  - `get_required_group_by_exprs_indices`
  - `get_required_sort_exprs_indices`

  The upgrade guide has a migration note.