zhuqi-lucas opened a new pull request, #23990: URL: https://github.com/apache/datafusion/pull/23990
## Which issue does this PR close? Part of the SortPreservingMerge cursor-cache work in #23840, split into smaller PRs for easier review (per @alamb / @rluvaton). This one carries the largest share of the win. ## Rationale for this change `SortPreservingMerge` compares cursor heads in a loser tree; every emitted row triggers `log2(k)` `compare` calls. For multi-column sort keys the key is serialized into arrow `Rows` and wrapped in `RowValues`, and each `compare` called `Rows::row(idx)` for both sides — walking `Arc<Rows>` → `offsets[idx]` / `offsets[idx+1]` → buffer slice. The offsets buffer (~65 KB per batch per partition, ×16 partitions) is far too large to stay cache-resident, so those lookups typically land in L2/L3 with a DRAM tail — and they are repeated for the same `idx` on every compare of a stable loser-tree head, even though the answer never changes until the cursor advances. ## What changes are included in this PR? Cache the current row's `(ptr, len)` once per `Cursor::advance` (via the existing `CursorValues::set_offset` hook) and read it in `compare`, so the hot path resolves to two plain field loads plus a `memcmp` instead of two Arc-chased offset walks. - The pointer is into the Arc-owned buffer heap and stays valid across struct moves (a cursor is written into a `Vec<Option<Cursor<..>>>` slot), so `Send`/`Sync` are implemented by hand with a SAFETY note. - `eq` / `eq_to_previous` take arbitrary cross-batch indices and continue to index `Rows` directly (the cache only holds the current offset). - `compare` keeps a debug-only assert that the cache invariant holds (indices equal the cursors' current offsets). Only `datafusion/physical-plan/src/sorts/cursor.rs` changes. Follow-up PRs will apply the same pattern to the single-column string cursors (`ByteArrayValues`, `StringViewArray`) and add a null-wrapper fast path. ## Are these changes tested? Yes: - `test_row_values_cache_matches_rows_index` drives the cache across every offset of a multi-row batch and asserts identical ordering to per-row `Rows` indexing, plus the cross-batch `eq` path. - `test_row_values_single_row_batch` covers the up-front row-0 cache and the length snapshot. - Verified red/green: breaking `set_offset` (skip the refresh) makes the first test fail as expected. - Existing `sorts::*` merge tests (83) pass. ## Are there any user-facing changes? No API changes. The `sort_tpch10` benchmark from the combined series (#23840) showed the multi-column queries driven by this cache: Q4 +1.23x, Q9 +1.15x, Q8 +1.13x, Q5 / Q6 / Q11 ~+1.12x; no regressions. CI benchmark to confirm on this split. -- 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]
