You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
Commit 35eb7f9
Browse filesBrowse the repository at this point in the historyBrowse files
Perf: cache primitive sort key in SortPreservingMerge to drop per-comparison bounds checks
The primary cost of `SortPreservingMergeStream` (the loser-tree k-way merge
behind `SortPreservingMergeExec` and `SortExec`'s streaming/spill merge) is the
per-row comparison loop, not the output `interleave`. Profiling a single
primitive sort column shows ~60% of time in the loop + cursor comparison and
only ~7% in `interleave`.
Two issues on that hot path:
1. The single-column primitive/array cursor comparison was not being inlined
(it showed up as a separate ~21% symbol), and every comparison
bounds-checked the underlying `ScalarBuffer` twice.
2. `maybe_poll_stream` was called on every row even though it is a no-op
whenever the winner's cursor is still live.
Changes:
- Inline the lightweight primitive/array cursor comparisons. `RowValues` is
left out-of-line on purpose: its variable-length byte comparison is heavy
and force-inlining it regresses the multi-column path.
- Skip the per-row `maybe_poll_stream` call unless the winner's cursor is
actually exhausted and needs a new `RecordBatch`.
- Cache the current (and previous) value of a primitive cursor, refreshed once
per `advance()` via a new `CursorValues::set_offset` hook (default no-op;
`ArrayValues` forwards to the inner cursor). The hot `compare`/`eq_to_previous`
then read cached fields instead of indexing the buffer, so the per-comparison
bounds checks disappear. The single remaining buffer access in `set_offset`
is dominated by the `offset < len` guard in `advance`, so the optimizer elides
its bounds check: the length is checked once per row, not per comparison. No
`unsafe` is used.
Benchmarks (`sort_preserving_merge`, 3 partitions x 1M rows):
- single u64 column: ~-15%
- multiple u64 columns: ~-6%
- single large string col: ~-5%
Covered by the existing `sorts/` tests (merge ordering, nulls, stable sort,
round-robin tie-breaker), which also exercise the new cache invariant via a
`debug_assert!` when run with debug assertions.
Co-Authored-By: Claude Opus 4.8 <[email protected]>
0 commit comments