perf: share encoder/reservation across PartitionedTopKExec partition … - #23096

## Which issue does this PR close?

- Related to apache#6899
(DENSE_RANK to follow in a separate PR will close it).
  
  ## Rationale for this change
  
PR apache#21479 introduced `WindowTopN` for `ROW_NUMBER` only; `RANK` and
`DENSE_RANK` were explicitly out of scope. This PR extends the rule to
`RANK`, replacing the full sort under `Filter(rk≤K) → Window(RANK) →
Sort` with a per-partition heap-of-K plus a boundary-tie buffer.
  
  ## What changes are included in this PR?

- **`datafusion/physical-plan/src/topk/mod.rs`** — new `pub(crate)
struct PartitionedTopKRank` (sibling of
`PartitionedTopK` from apache#23096) with per-partition `RankPartitionState {
TopKHeap, Vec<TieEntry> }`.
- **`datafusion/physical-plan/src/sorts/partitioned_topk.rs`** —
`WindowFnKind` enum (`RowNumber` / `Rank`).
`do_partitioned_topk` dispatches on `fn_kind` to
`PartitionedTopK::try_new` or `PartitionedTopKRank::try_new`;
- **`datafusion/physical-optimizer/src/window_topn.rs`** —
`is_row_number` → `supported_window_fn(expr) ->
Option<WindowFnKind>`; empty-`order_by` guard for RANK; `WindowFnKind`
plumbed through `PartitionedTopKExec::try_new`.
- **`datafusion/sqllogictest/test_files/window_topn.slt`** — RANK SLT
cases: basic, strict (`<`), flipped (`>=` / `>`),
boundary ties, ties spanning ob values, empty-`ORDER BY` (rule must NOT
fire), mixed window functions, ASC/DESC × NULLS FIRST/LAST, QUALIFY.
- **`datafusion/core/tests/physical_optimizer/window_topn.rs`** — 6 new
RANK rule unit tests covering predicate
  matching, partition-by/order-by guards, dense_rank skip.
- **`benchmarks/queries/h2o/window.sql`** — six new RANK queries
(Q14–Q17, Q22, Q23) covering partition counts from ~100 to ~100K, low
and heavy tie densities.

h2o `window` benchmark, 10M-row `large` table, RANK top-2, 3-iteration
average. Toggle via `DATAFUSION_OPTIMIZER_ENABLE_WINDOW_TOPN`.

 | Variant | Partitions | OFF (rule disabled) | ON (rule enabled) | Δ |
  |---|---:|---:|---:|:---:|
| RANK low ties (`id3 % 100`) | ~100 | 305 ms | **107 ms** | **2.84×
faster** ✓ |
| RANK low ties (`id3 % 1000`) | ~1K | 263 ms | **120 ms** | **2.19×
faster** ✓ |
| RANK heavy ties (`id3 % 1000`, `v2 % 10` OB) | ~1K | 282 ms | **125
ms** | **2.25× faster** ✓ |
| RANK low ties (`id2`) | ~10K | 363 ms | **140 ms** | **2.59× faster**
✓ |
| RANK heavy ties (`id2`, `v2 % 10` OB) | ~10K | 291 ms | **143 ms** |
**2.04× faster** ✓ |
| RANK low ties (`id3 % 100K`) | ~100K | 241 ms | 422 ms | 1.75× slower
|
  
  ## Are these changes tested?
  
  Yes:

  - `cargo test -p datafusion-physical-plan --lib` — 1455 passed
  - `cargo test -p datafusion-physical-optimizer --lib` — 27 passed
- `cargo test -p datafusion --test core_integration
physical_optimizer::window_topn::` — 13 passed (7 ROW_NUMBER + 6 RANK)
  - `cargo test --test sqllogictests -- window_topn` — passed

  ## Are there any user-facing changes?

The existing `optimizer.enable_window_topn` config flag (default
`false`) now also covers `RANK` queries. No public API additions

## Which issue does this PR close?

- Related to apache#6899
(DENSE_RANK to follow in a separate PR will close it).
  
  ## Rationale for this change
  
PR apache#21479 introduced `WindowTopN` for `ROW_NUMBER` only; `RANK` and
`DENSE_RANK` were explicitly out of scope. This PR extends the rule to
`RANK`, replacing the full sort under `Filter(rk≤K) → Window(RANK) →
Sort` with a per-partition heap-of-K plus a boundary-tie buffer.
  
  ## What changes are included in this PR?

- **`datafusion/physical-plan/src/topk/mod.rs`** — new `pub(crate)
struct PartitionedTopKRank` (sibling of
`PartitionedTopK` from apache#23096) with per-partition `RankPartitionState {
TopKHeap, Vec<TieEntry> }`.
- **`datafusion/physical-plan/src/sorts/partitioned_topk.rs`** —
`WindowFnKind` enum (`RowNumber` / `Rank`).
`do_partitioned_topk` dispatches on `fn_kind` to
`PartitionedTopK::try_new` or `PartitionedTopKRank::try_new`;
- **`datafusion/physical-optimizer/src/window_topn.rs`** —
`is_row_number` → `supported_window_fn(expr) ->
Option<WindowFnKind>`; empty-`order_by` guard for RANK; `WindowFnKind`
plumbed through `PartitionedTopKExec::try_new`.
- **`datafusion/sqllogictest/test_files/window_topn.slt`** — RANK SLT
cases: basic, strict (`<`), flipped (`>=` / `>`),
boundary ties, ties spanning ob values, empty-`ORDER BY` (rule must NOT
fire), mixed window functions, ASC/DESC × NULLS FIRST/LAST, QUALIFY.
- **`datafusion/core/tests/physical_optimizer/window_topn.rs`** — 6 new
RANK rule unit tests covering predicate
  matching, partition-by/order-by guards, dense_rank skip.
- **`benchmarks/queries/h2o/window.sql`** — six new RANK queries
(Q14–Q17, Q22, Q23) covering partition counts from ~100 to ~100K, low
and heavy tie densities.

h2o `window` benchmark, 10M-row `large` table, RANK top-2, 3-iteration
average. Toggle via `DATAFUSION_OPTIMIZER_ENABLE_WINDOW_TOPN`.

 | Variant | Partitions | OFF (rule disabled) | ON (rule enabled) | Δ |
  |---|---:|---:|---:|:---:|
| RANK low ties (`id3 % 100`) | ~100 | 305 ms | **107 ms** | **2.84×
faster** ✓ |
| RANK low ties (`id3 % 1000`) | ~1K | 263 ms | **120 ms** | **2.19×
faster** ✓ |
| RANK heavy ties (`id3 % 1000`, `v2 % 10` OB) | ~1K | 282 ms | **125
ms** | **2.25× faster** ✓ |
| RANK low ties (`id2`) | ~10K | 363 ms | **140 ms** | **2.59× faster**
✓ |
| RANK heavy ties (`id2`, `v2 % 10` OB) | ~10K | 291 ms | **143 ms** |
**2.04× faster** ✓ |
| RANK low ties (`id3 % 100K`) | ~100K | 241 ms | 422 ms | 1.75× slower
|
  
  ## Are these changes tested?
  
  Yes:

  - `cargo test -p datafusion-physical-plan --lib` — 1455 passed
  - `cargo test -p datafusion-physical-optimizer --lib` — 27 passed
- `cargo test -p datafusion --test core_integration
physical_optimizer::window_topn::` — 13 passed (7 ROW_NUMBER + 6 RANK)
  - `cargo test --test sqllogictests -- window_topn` — passed

  ## Are there any user-facing changes?

The existing `optimizer.enable_window_topn` config flag (default
`false`) now also covers `RANK` queries. No public API additions

…he#27197)

## Which issue does this PR close?

- Closes apache#24608.

## Rationale for this change

`enable_window_topn` has been off since apache#21479 because of
high-cardinality regressions against the sort plan. The work items in
apache#24608 are now done:

- apache#23096, 
- apache#25730, 
- apache#25968, 
- apache#26133

The h2o window benchmark's Top-N queries
(`benchmarks/queries/h2o/window.sql`, Q13–Q29, small dataset,
`J1_1e7_1e7_NA.parquet`) are now faster with the flag on in every case,
up to 100K partitions and including the heavy-ties variants. `dfbench
h2o --iterations 5`, median,
`DATAFUSION_OPTIMIZER_ENABLE_WINDOW_TOPN=false` for the baseline, same
binary, Apple M4 Max:

| Query | function, partitions | off (ms) | on (ms) | change |
|---|---|---:|---:|---|
| Q13 | ROW_NUMBER, id2 | 127.4 | 25.8 | 4.93x faster |
| Q14 | ROW_NUMBER, 100 | 190.8 | 35.9 | 5.32x faster |
| Q15 | ROW_NUMBER, 1K | 173.6 | 35.7 | 4.86x faster |
| Q16 | ROW_NUMBER, 10K | 149.7 | 33.0 | 4.54x faster |
| Q17 | ROW_NUMBER, 100K | 151.1 | 49.1 | 3.08x faster |
| Q18 | RANK, 100 | 226.3 | 28.8 | 7.86x faster |
| Q19 | RANK, 1K | 186.0 | 29.6 | 6.28x faster |
| Q20 | RANK, 1K, heavy ties | 209.8 | 57.1 | 3.67x faster |
| Q21 | RANK, id2 | 174.2 | 25.4 | 6.87x faster |
| Q22 | RANK, id2, heavy ties | 190.5 | 37.2 | 5.13x faster |
| Q23 | RANK, 100K | 188.1 | 63.5 | 2.96x faster |
| Q24 | DENSE_RANK, 100 | 248.4 | 38.6 | 6.43x faster |
| Q25 | DENSE_RANK, 1K | 199.6 | 36.9 | 5.40x faster |
| Q26 | DENSE_RANK, 1K, heavy ties | 232.2 | 43.3 | 5.37x faster |
| Q27 | DENSE_RANK, id2 | 211.3 | 45.7 | 4.63x faster |
| Q28 | DENSE_RANK, id2, heavy ties | 208.7 | 53.6 | 3.89x faster |
| Q29 | DENSE_RANK, 100K | 205.8 | 123.3 | 1.67x faster |

## What changes are included in this PR?

- `enable_window_topn` defaults to `true`; its doc comment now lists
ROW_NUMBER, RANK and DENSE_RANK and drops the high-cardinality warning.
- `window_topn.slt` restores the setting with `RESET` instead of `SET
... = false`.
- `configs.md` and `information_schema.slt` regenerated.
- The h2o `window_sorted` settings comment no longer says the flag
defaults to false (it still sets it explicitly).

## What is the testing strategy for this PR?

Existing coverage. With the flag on by default, the whole sqllogictest
suite and `core_integration` pass with only the `information_schema.slt`
default change; `qualify.slt`'s `rank <= 3` / `dense_rank <= 2` cases
now run through `PartitionedTopKExec` and return the same results.
`window_topn.slt` still covers the disabled path explicitly.

## Are there any user-facing changes?

Yes. Top-K-per-partition queries (`rn <= K`, `rn < K` over ROW_NUMBER /
RANK / DENSE_RANK) plan with `PartitionedTopKExec` instead of a full
sort, so `EXPLAIN` output changes; results don't. Set
`datafusion.optimizer.enable_window_topn = false` to get the old plan.

---------

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