zhuqi-lucas opened a new pull request, #23840: URL: https://github.com/apache/datafusion/pull/23840
## Which issue does this PR close? - Closes #. ## Rationale for this change `SortPreservingMerge` compares cursors in a loser tree; each row emitted triggers `log2(num_streams)` `T::compare(l, l_idx, r, r_idx)` calls. Today only `PrimitiveValues` caches its current-row value — the other `CursorValues` implementations (`ByteArrayValues`, `StringViewArray`, `RowValues`) re-index the underlying buffers on every compare, and the `ArrayValues` null wrapper always runs two `is_null(idx)` checks even for null-free batches. Profiling sort-tpch showed `SortPreservingMergeStream::poll_next` at ~20% self-time on Q3 (single VARCHAR sort). This PR extends the pre-existing `PrimitiveValues` caching pattern to every other cursor type so the hot loser-tree compare reads pre-resolved state from adjacent cache lines instead of re-walking Arc chains or re-checking null bitmaps. ## What changes are included in this PR? Single file changed: `datafusion/physical-plan/src/sorts/cursor.rs`. All caches refresh once per `Cursor::advance` (via the existing `CursorValues::set_offset` hook) and are read by `compare`. `eq` / `eq_to_previous` still take arbitrary indices (cross-batch tie comparison) and continue to index the raw array. - **`ByteArrayValues`** (Utf8 / Binary / LargeUtf8 / LargeBinary): cache `(current_start, current_end)`. `compare` reads a slice from the values buffer without two `OffsetBuffer::get_unchecked` loads per side. - **New `StringViewCursorValues` wrapper** (replaces bare `impl CursorValues for StringViewArray`): snapshots `len`, `views_ptr`, and `all_inline` at construction. `set_offset` precomputes `inline_key_fast(view)` when every row is inline, otherwise resolves the view to `(ptr, len)` into the Arc-owned buffer heap. `compare` reads one `u128` (all-inline) or two `&[u8]`s (external). - **`RowValues`** (arrow `Rows` multi-column path): cache the current row's `(ptr, len)` from `Rows::row(offset).as_ref()`. Multi-column sort used to pay two `Rows::row(idx)` offset lookups per compare — this is where the biggest wins in this PR come from. - **`ArrayValues<T>`**: cache `has_nulls = null_count > 0`. When both sides have no nulls (the common case for sort keys) `compare` / `eq` skip the two `is_null(idx)` checks and go straight to the inner comparator. All cached raw pointers reference Arc-owned heap buffers (Rows data, StringView views + data_buffers), so they stay valid across struct moves. `Send`/`Sync` are hand-implemented for the two wrappers that hold raw pointers, matching the underlying array's guarantees. ## Are these changes tested? Yes — the 76 existing tests in `datafusion-physical-plan::sorts::*` (nulls, stable sort, streaming input/output, round-robin tie-breaker, congestion, single-partition with/without fetch, three-partition merge, spill, etc.) all pass in both debug and release mode. The correctness invariant added — \"cache is always in sync with the cursor's current offset\" — is exercised directly by every merge test, and `debug_assert`s in the caching path fail loudly if the invariant is ever violated. No new tests added: the invariant is a strengthening of existing behavior (same observable output as baseline) rather than new functionality. ## Are there any user-facing changes? No public API change. `sort-tpch` SF1 lineitem benchmark (6M rows, 3 iterations, `release-nonlto`, macOS ARM): | Q | Sort key | Baseline | Experim | Delta | |----|--------------------------------|---------:|--------:|:-------:| | Q1 | l_orderkey (i64) | 83.4ms | 76.6ms | -8.2% | | Q2 | l_orderkey, l_suppkey (i64x2) | 74.4ms | 70.1ms | -5.8% | | Q3 | l_comment (VARCHAR ~26c) | 542.2ms | 499.2ms | -7.9% | | Q4 | 4 col mixed | 133.2ms | 110.1ms | -17.4% | | Q5 | 5 col mixed | 240.3ms | 149.2ms | **-37.9%** | | Q6 | 3x fixed-len string | 253.1ms | 157.3ms | **-37.8%** | | Q7 | 3 col mixed | 379.4ms | 290.1ms | -23.5% | | Q8 | 3 col mixed | 261.9ms | 248.5ms | -5.1% | | Q9 | 3 col mixed | 271.6ms | 259.2ms | -4.6% | | Q10| 4 col + big payload | 386.4ms | 365.4ms | -5.4% | | Q11| l_shipmode (all-inline, card 7)| 167.6ms | 155.3ms | -7.3% | **Total across 11 queries: 2873ms → 2380ms (−17.2%). All queries improve, no regressions.** - Multi-column sorts (Q4–Q7) get the biggest wins from `RowValues` cache - Q3 gets its win from `StringViewCursorValues` - Q11 (originally regressed by +3% with the `StringViewCursorValues` wrapper alone) is now a −7% win thanks to `ArrayValues::has_nulls` short-circuit -- 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]
