[I] Select a null-free sort-merge cursor when the schema rules nulls out [datafusion]

["zhuqi-lucas (via GitHub)" <gi...@apache.org>]

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: github-unsubscribe@datafusion.apache.org.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org