zhuqi-lucas opened a new issue, #26252:
URL: https://github.com/apache/datafusion/issues/26252
### Is your feature request related to a problem or challenge?
Follow-up to a review comment from @alamb on #26215.
`ArrayValues` wraps every sort-key cursor to add null handling, so its
`compare` / `eq` / `eq_to_previous` sit in the merge's inner loop. #26215 skips
the `is_null` checks when neither cursor has nulls, but it has to test
`has_nulls` on every comparison, because a batch's null count is only known
once that batch arrives:
```rust
if !l.has_nulls && !r.has_nulls {
```
As @alamb put it:
> this still basically dynamically dispatches each row
>
> I wonder if there is some way to parameterize `ArrayValues` so we could
dispatch just once
That per-row test is not free. Stripping the null handling from
`ArrayValues` outright (incorrect — measured only as a ceiling) is worth
another **-6.7% to -7.5%** on `sort_preserving_merge`'s tied-key benchmark, p =
0.00 on all four cases.
### Describe the solution you'd like
Making `ArrayValues` itself const-generic over null-ness does not work:
`SortPreservingMergeStream` holds `cursors: Vec<Option<Cursor<C>>>` with a
single `C`, and null-ness varies per batch, so both variants would have to
coexist in one loser tree.
But the decision can be hoisted one level up, to where the merge is built.
`StreamingMergeBuilder` already reads `sort.expr.data_type(schema)?` to pick a
cursor; reading `sort.expr.nullable(schema)?` next to it lets a non-nullable
sort key select a cursor with no null bookkeeping at all, and the whole stream
monomorphizes on it:
```rust
/// `CursorValues` for a sort key the schema proves non-nullable.
pub struct NonNullArrayValues<T: CursorValues> {
values: T,
options: SortOptions,
_reservation: MemoryReservation,
}
```
Measured on a prototype, `sort_preserving_merge` tied-keys bench (UInt64
key, `nullable: false`):
| case | #26215 | with this | change |
|---|---|---|---|
| 2 partitions / tie breaker on | 82.145 ms | 77.029 ms | **-6.23%** |
| 2 partitions / tie breaker off | 146.36 ms | 137.12 ms | **-6.31%** |
| 4 partitions / tie breaker on | 220.99 ms | 208.62 ms | **-5.60%** |
| 4 partitions / tie breaker off | 290.10 ms | 270.94 ms | **-6.61%** |
all p = 0.00. TPC-H declares these keys non-nullable (`l_orderkey`,
`l_shipmode`), so this applies to the `sort_tpch` workload.
### Describe alternatives you've considered
Schema nullability is a claim about the data, not a fact about it — a sort
expression whose `nullable()` is imprecise could still evaluate to a null,
which this cursor would compare as an ordinary value and silently mis-order.
Two options:
1. Check the already-maintained null count once per batch and return an
error. No per-row cost, and a wrong schema fails loudly instead of producing
wrong results. This is what the prototype does, and it accounts for roughly the
1% gap against the ceiling above.
2. Fall back to `ArrayValues` for that batch — not possible once the stream
is monomorphized, so it would need an enum cursor and bring the per-row branch
back.
Worth settling in review which of these is wanted.
### Additional context
Prototype is implemented and green: `datafusion-physical-plan` 2533 tests
pass, clippy and fmt clean, workspace builds. Includes a test that proves the
dispatch actually selects the new cursor (it feeds the merge a batch violating
the schema's claim; only the non-null cursor can report that), verified
non-vacuous by mutation.
### Willingness to contribute
I can contribute to this feature.
--
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]
