Repository navigation
Commit 19b165f
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
0 commit comments