Skip to content

Commit 19b165f

Browse files
committed
perf(sort-merge): cache current-row key per cursor to speed up SortPreservingMerge
Every `SortPreservingMerge` compare walks `T::compare(l, l_idx, r, r_idx)`. Only `PrimitiveValues` cached its current-row value; the other `CursorValues` implementations re-indexed the underlying buffers on every compare, and the `ArrayValues` null wrapper always ran two `is_null(idx)` checks even when the batch had no nulls at all. This change refreshes a per-cursor cache once per `Cursor::advance` (via `CursorValues::set_offset`) so the hot loser-tree compare reads pre-resolved state from adjacent cache lines instead of re-walking Arc chains. Changes to `CursorValues` implementations in `sorts/cursor.rs`: - `ByteArrayValues` (`Utf8` / `Binary` / `LargeUtf8` / `LargeBinary`): cache `(current_start, current_end)` for the current row so `compare` reads a slice from the values buffer without two `OffsetBuffer::get_unchecked` loads per side. - `StringViewArray` → new `StringViewCursorValues` wrapper: snapshot `len`, `views_ptr`, and `all_inline` at construction; on `set_offset` precompute `inline_key_fast(view)` when every row is inline, otherwise resolve 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 was paying two `Rows::row(idx)` offset lookups per compare — the biggest hot path savings in this diff. - `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, StringView 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. `eq` / `eq_to_previous` still take arbitrary indices (cross-batch tie comparison), so those paths continue to index the raw array rather than reading the current-row cache. Benchmarks: sort-tpch SF1 on lineitem (6M rows), 3 iterations each: | 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 the `RowValues` cache; Q3 from `StringViewCursorValues`; Q11 from `ArrayValues::has_nulls`. Test coverage: existing `sorts::*` tests (76 total, incl. null / stable sort / streaming / round-robin tie-breaker) all pass. No new tests needed — the invariants added (cache always in sync with cursor offset) are exercised by the merge tests directly.
1 parent 1bdff19 commit 19b165f

1 file changed

Lines changed: 337 additions & 45 deletions

File tree

0 commit comments

Comments
 (0)