fix: align nested piecewise merge join sorting and comparison - #26043

…#26043)

## Which issue does this PR close?

- Closes apache#25957.

## Rationale for this change

Piecewise merge joins can return incorrect results for nested range keys
containing inner NULLs, and fail when sorting Struct or List-of-List
keys. Sorting, extreme-key selection, and comparison must use the same
ordering.

## What changes are included in this PR?

- Sort `<`/`<=` keys descending with NULLs last, reversing both value
and inner-NULL ordering to agree with SQL comparisons.
- Bound classic and left existence scans to non-null keys, preserving
trailing NULL rows in outer, anti, and mark results.
- Select nested min/max keys with Arrow's comparator.
- Sort streamed keys with `lexsort_to_indices`, supporting Struct and
List-of-List keys.
- Execute nested range joins with `PiecewiseMergeJoinExec`.

## What is the testing strategy for this PR?

SQL logic tests compare complete result multisets against NestedLoopJoin
for List, Struct, and List-of-List keys, all four range operators,
classic joins, semi/anti joins, and an EXISTS mark expression. The
matrix covers batch sizes 1, 2, and 8192 and partition counts 1 and 4.
Plan assertions check that Struct and List-of-List classic joins use
PWMJ.

Validation passed: PWMJ SQL logic tests and fuzz tests, the extended
workspace suite (including all 527 SQL test files), formatting, Clippy
with all targets/features, and the repository lint checks.

## Are there any user-facing changes?

Nested range joins produce correct results and support Struct and
List-of-List keys with piecewise merge joins enabled. No public API
changes.

---------

Co-authored-by: mikamikasuki <[email protected]>

apache#26287)

## Which issue does this PR close?

- Part of apache#18221 (and the PiecewiseMergeJoin EPIC apache#17427).

## Rationale for this change

On large inputs the classic `PiecewiseMergeJoin` (Inner/Left/Right/Full)
can be slower than `NestedLoopJoin`. For example, before apache#25840, `l JOIN
r ON l.a < r.b` over 100K×100K rows at the default `target_partitions`
took 1.41s with PWMJ and 1.26s with NLJ.

A profile of the 1K×1M case (`sample`, `target_partitions = 1`) shows
the time goes to copying output rather than to comparisons:

| where | share of busy samples |
|---|---|
| `take` repeating each matched streamed row | 32% |
| `BatchCoalescer` `memmove` of every column | 30% |
| downstream `sum` (the query itself) | 10% |
| per-streamed-row fixed cost (`RecordBatch`, allocations, coalescer
bookkeeping) | ~13% |

For every matched streamed row, the join takes
`UInt32Array::from_value(row, count)`, gathers the streamed row `count`
times, slices the buffered suffix, and builds a `RecordBatch` from them.
`BatchCoalescer` then copies all of it again, so the streamed columns
are written twice. apache#25840 made finding each row's first match a binary
search and settles never-matching rows before the sort, but it kept this
emission path, so on current `main` the cost above is still paid for
every matched streamed row.

## What changes are included in this PR?

The classic join builds each output batch directly, and `BatchCoalescer`
is removed from this path.

Matched rows:
- The output is kept as runs: `(buffered start, len)`, paired with one
streamed row index per output row.
- Once `batch_size` rows are pending, or the stream batch ends:
- Buffered columns are copied run by run with
`MutableArrayData::try_extend`, which is a `memcpy` for fixed-width
types.
  - Streamed columns are gathered with one `take` per column.

Rows that match nothing are emitted with null columns for the other
side, in batches of at most `batch_size`:
- Streamed rows that can never match (`Right`/`Full`), which apache#25840
settles before the sort, are selected with one `filter_record_batch` and
emitted as slices of its output (`push_unmatched_streamed`). When every
row of a stream batch is unmatched, `filter` returns the input columns
as a slice and copies nothing.
- Unmatched buffered rows (`Left`/`Full`), in the final pass, are the
prefix before the `min_marked` watermark plus any trailing NULL keys
(apache#26043). They are copied out of the buffered batch
(`push_unmatched_buffered`), not sliced: a slice would keep the whole
buffered batch alive and report its full buffers to downstream memory
accounting once per output batch

## Benchmarks

The pwmj suite from apache#25839
(100K buffered keys, 2M streamed rows, five match regimes ×
INNER/LEFT/RIGHT/FULL). Reproduce with:

`cargo run -p datafusion-benchmarks --release --bin benchmark_runner --
pwmj`

| regime | main (ms) | this PR (ms) | speedup |
|---|---|---|---|
| no_match, null_heavy: Inner, Left | 2.2–2.3 | 2.1 | 1.05× |
| no_match, null_heavy: Right, Full | 3.2–3.3 | 2.4–2.5 | **1.29–1.33×**
|
| half_match | 231–233 | 27–29 | **8.1–8.4×** |
| selective | 453–455 | 47–48 | **9.5–9.7×** |
| all_match (200M output rows) | 167–168 | 159–161 | 1.05–1.06× |

## What is the testing strategy for this PR?

Six new unit tests in `classic_join.rs`:
- `join_full_less_than_splits_suffixes_across_batches`: at `batch_size =
4`, a buffered suffix straddles an output batch, and never-matching
streamed rows, matched rows and unmatched buffered rows all appear. It
asserts both the rows and the batch sizes `[1, 4, 2, 1]`.
- `join_inner_less_than_one_row_completes_several_batches`: one streamed
row whose buffered suffix fills several output batches.
- `join_right_less_than_empty_buffered`: a Right join with an empty
buffered side, where every streamed row is padded with nulls.
- `join_right_less_than_never_matching_rows_split_by_batch_size`: more
never-matching streamed rows than `batch_size`, which must be split into
batches of at most `batch_size`, in input order, ahead of the matched
rows.
- `join_left_less_than_unmatched_prefix_and_trailing_nulls`: a Left join
on `<` whose unmatched buffered rows are a prefix longer than
`batch_size` plus trailing NULL keys, which sort last for `<`.
- `join_left_unmatched_buffered_batches_report_own_memory`: each
unmatched-buffered output batch reports only its own rows' memory, not
the whole buffered batch.

## Are there any user-facing changes?

No API changes. `EXPLAIN ANALYZE` reports a smaller `output_bytes` for
`PiecewiseMergeJoin`, because output batches no longer share the
coalescer's buffers (`explain_analyze.slt`: 128.0 KB → 96.0 B).