Skip to content

Commit 35eb7f9

Browse files
Dandandanclaude
andcommitted
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]>
1 parent 5d24591 commit 35eb7f9

2 files changed

Lines changed: 130 additions & 11 deletions

File tree

‎datafusion/physical-plan/src/sorts/cursor.rs‎

Lines changed: 118 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -44,6 +44,21 @@ pub trait CursorValues {
4444

4545
/// Returns comparison of `l[l_idx]` and `r[r_idx]`
4646
fn compare(l: &Self, l_idx: usize, r: &Self, r_idx: usize) -> Ordering;
47+
48+
/// Notifies the values that the owning [`Cursor`] has moved to `offset`,
49+
/// which is guaranteed to be `< len()`.
50+
///
51+
/// Implementations may use this to cache the value(s) at the current
52+
/// position so that the (hot) loser-tree comparisons — which always compare
53+
/// values at the cursors' *current* offsets — can avoid repeatedly indexing
54+
/// (and bounds-checking) the underlying buffer. The default is a no-op for
55+
/// implementations that do not benefit from caching (e.g. variable-length
56+
/// byte / row cursors, whose comparison cost is dominated by the byte
57+
/// comparison itself rather than the index).
58+
#[inline]
59+
fn set_offset(&mut self, offset: usize) {
60+
let _ = offset;
61+
}
4762
}
4863

4964
/// A comparable cursor, used by sort operations
@@ -89,14 +104,23 @@ impl<T: CursorValues> Cursor<T> {
89104
}
90105

91106
/// Returns true if there are no more rows in this cursor
107+
#[inline]
92108
pub fn is_finished(&self) -> bool {
93109
self.offset == self.values.len()
94110
}
95111

96112
/// Advance the cursor, returning the previous row index
113+
#[inline]
97114
pub fn advance(&mut self) -> usize {
98115
let t = self.offset;
99116
self.offset += 1;
117+
// Keep any cached current value in sync with the new position. Guard on
118+
// `is_finished` so implementations never have to index out of bounds:
119+
// when the cursor is exhausted the cache is left stale, but a finished
120+
// cursor is taken (set to `None`) before it is compared again.
121+
if self.offset < self.values.len() {
122+
self.values.set_offset(self.offset);
123+
}
100124
t
101125
}
102126

@@ -112,6 +136,7 @@ impl<T: CursorValues> Cursor<T> {
112136
}
113137

114138
impl<T: CursorValues> PartialEq for Cursor<T> {
139+
#[inline]
115140
fn eq(&self, other: &Self) -> bool {
116141
T::eq(&self.values, self.offset, &other.values, other.offset)
117142
}
@@ -142,6 +167,7 @@ impl<T: CursorValues> PartialOrd for Cursor<T> {
142167
}
143168

144169
impl<T: CursorValues> Ord for Cursor<T> {
170+
#[inline]
145171
fn cmp(&self, other: &Self) -> Ordering {
146172
T::compare(&self.values, self.offset, &other.values, other.offset)
147173
}
@@ -180,10 +206,18 @@ impl RowValues {
180206
}
181207

182208
impl CursorValues for RowValues {
209+
#[inline]
183210
fn len(&self) -> usize {
184211
self.rows.num_rows()
185212
}
186213

214+
// NOTE: `eq`/`eq_to_previous`/`compare` are deliberately NOT `#[inline]`.
215+
// The `Rows` byte-wise comparison is comparatively heavyweight (it
216+
// materializes `Row` views and compares variable-length byte slices), and
217+
// forcing it into the already-large `update_loser_tree`/`poll_next` hot loop
218+
// regresses the multi-column merge path. Leaving it as an out-of-line call
219+
// keeps that loop compact. (The lightweight primitive/byte cursors below DO
220+
// benefit from inlining.)
187221
fn eq(l: &Self, l_idx: usize, r: &Self, r_idx: usize) -> bool {
188222
l.rows.row(l_idx) == r.rows.row(r_idx)
189223
}
@@ -209,29 +243,85 @@ impl<T: ArrowPrimitiveType> CursorArray for PrimitiveArray<T> {
209243
type Values = PrimitiveValues<T::Native>;
210244

211245
fn values(&self) -> Self::Values {
212-
PrimitiveValues(self.values().clone())
246+
PrimitiveValues::new(self.values().clone())
213247
}
214248
}
215249

250+
/// [`CursorValues`] for a primitive column.
251+
///
252+
/// The value at the cursor's current offset — and the one immediately before it
253+
/// — are cached in [`Self::set_offset`] (called once per [`Cursor::advance`]).
254+
/// The hot loser-tree comparisons (`compare`/`eq_to_previous`), which always
255+
/// operate at the cursor's *current* position, then read these cached fields
256+
/// instead of indexing (and bounds-checking) the buffer on every comparison.
216257
#[derive(Debug)]
217-
pub struct PrimitiveValues<T: ArrowNativeTypeOp>(ScalarBuffer<T>);
258+
pub struct PrimitiveValues<T: ArrowNativeTypeOp> {
259+
values: ScalarBuffer<T>,
260+
/// Cached value at the current offset (`values[offset]`).
261+
current: T,
262+
/// Cached value at the previous offset (`values[offset - 1]`); meaningful
263+
/// once the cursor has advanced past offset 0 (the only case in which
264+
/// `eq_to_previous` reads it).
265+
previous: T,
266+
/// The current offset. Kept solely to `debug_assert!` that the cache is read
267+
/// at the position the caller claims, guarding the invariant the cache
268+
/// relies on; it is not used to index the buffer.
269+
offset: usize,
270+
}
271+
272+
impl<T: ArrowNativeTypeOp> PrimitiveValues<T> {
273+
fn new(values: ScalarBuffer<T>) -> Self {
274+
// Cursors are only built over non-empty batches; the `unwrap_or_default`
275+
// merely avoids a panic for the (unreachable) empty case.
276+
let first = values.first().copied().unwrap_or_default();
277+
Self {
278+
values,
279+
current: first,
280+
previous: first,
281+
offset: 0,
282+
}
283+
}
284+
}
218285

219286
impl<T: ArrowNativeTypeOp> CursorValues for PrimitiveValues<T> {
287+
#[inline(always)]
220288
fn len(&self) -> usize {
221-
self.0.len()
289+
self.values.len()
222290
}
223291

292+
#[inline(always)]
224293
fn eq(l: &Self, l_idx: usize, r: &Self, r_idx: usize) -> bool {
225-
l.0[l_idx].is_eq(r.0[r_idx])
294+
// Arbitrary indices (used when comparing across batch boundaries), so
295+
// this path indexes the buffer directly rather than using the cache.
296+
l.values[l_idx].is_eq(r.values[r_idx])
226297
}
227298

299+
#[inline(always)]
228300
fn eq_to_previous(cursor: &Self, idx: usize) -> bool {
229301
assert!(idx > 0);
230-
cursor.0[idx].is_eq(cursor.0[idx - 1])
302+
debug_assert_eq!(idx, cursor.offset);
303+
cursor.current.is_eq(cursor.previous)
231304
}
232305

306+
#[inline(always)]
233307
fn compare(l: &Self, l_idx: usize, r: &Self, r_idx: usize) -> Ordering {
234-
l.0[l_idx].compare(r.0[r_idx])
308+
debug_assert_eq!(l_idx, l.offset);
309+
debug_assert_eq!(r_idx, r.offset);
310+
l.current.compare(r.current)
311+
}
312+
313+
#[inline(always)]
314+
fn set_offset(&mut self, offset: usize) {
315+
// `offset < len` is guaranteed by the caller (`Cursor::advance`), which
316+
// performs that exact comparison immediately before calling this. With
317+
// this method inlined, the bounds check on `self.values[offset]` is
318+
// dominated by — and identical to — that comparison, so the optimizer
319+
// elides it: the length is checked once per advanced row, not on every
320+
// (per-comparison) buffer access. The old `current` holds
321+
// `values[offset - 1]`, so it becomes `previous`.
322+
self.previous = self.current;
323+
self.current = self.values[offset];
324+
self.offset = offset;
235325
}
236326
}
237327

@@ -241,6 +331,7 @@ pub struct ByteArrayValues<T: OffsetSizeTrait> {
241331
}
242332

243333
impl<T: OffsetSizeTrait> ByteArrayValues<T> {
334+
#[inline]
244335
fn value(&self, idx: usize) -> &[u8] {
245336
assert!(idx < self.len());
246337
// Safety: offsets are valid and checked bounds above
@@ -253,19 +344,23 @@ impl<T: OffsetSizeTrait> ByteArrayValues<T> {
253344
}
254345

255346
impl<T: OffsetSizeTrait> CursorValues for ByteArrayValues<T> {
347+
#[inline]
256348
fn len(&self) -> usize {
257349
self.offsets.len() - 1
258350
}
259351

352+
#[inline]
260353
fn eq(l: &Self, l_idx: usize, r: &Self, r_idx: usize) -> bool {
261354
l.value(l_idx) == r.value(r_idx)
262355
}
263356

357+
#[inline]
264358
fn eq_to_previous(cursor: &Self, idx: usize) -> bool {
265359
assert!(idx > 0);
266360
cursor.value(idx) == cursor.value(idx - 1)
267361
}
268362

363+
#[inline]
269364
fn compare(l: &Self, l_idx: usize, r: &Self, r_idx: usize) -> Ordering {
270365
l.value(l_idx).cmp(r.value(r_idx))
271366
}
@@ -394,16 +489,19 @@ impl<T: CursorValues> ArrayValues<T> {
394489
}
395490
}
396491

492+
#[inline(always)]
397493
fn is_null(&self, idx: usize) -> bool {
398494
(idx < self.null_threshold) == self.options.nulls_first
399495
}
400496
}
401497

402498
impl<T: CursorValues> CursorValues for ArrayValues<T> {
499+
#[inline(always)]
403500
fn len(&self) -> usize {
404501
self.values.len()
405502
}
406503

504+
#[inline(always)]
407505
fn eq(l: &Self, l_idx: usize, r: &Self, r_idx: usize) -> bool {
408506
match (l.is_null(l_idx), r.is_null(r_idx)) {
409507
(true, true) => true,
@@ -412,15 +510,20 @@ impl<T: CursorValues> CursorValues for ArrayValues<T> {
412510
}
413511
}
414512

513+
#[inline(always)]
415514
fn eq_to_previous(cursor: &Self, idx: usize) -> bool {
416515
assert!(idx > 0);
417516
match (cursor.is_null(idx), cursor.is_null(idx - 1)) {
418517
(true, true) => true,
419-
(false, false) => T::eq(&cursor.values, idx, &cursor.values, idx - 1),
518+
// Delegate to the inner `eq_to_previous` (rather than `eq` at
519+
// `idx`/`idx - 1`) so cursors that cache their current/previous
520+
// value can answer without indexing.
521+
(false, false) => T::eq_to_previous(&cursor.values, idx),
420522
_ => false,
421523
}
422524
}
423525

526+
#[inline(always)]
424527
fn compare(l: &Self, l_idx: usize, r: &Self, r_idx: usize) -> Ordering {
425528
match (l.is_null(l_idx), r.is_null(r_idx)) {
426529
(true, true) => Ordering::Equal,
@@ -438,6 +541,13 @@ impl<T: CursorValues> CursorValues for ArrayValues<T> {
438541
},
439542
}
440543
}
544+
545+
#[inline(always)]
546+
fn set_offset(&mut self, offset: usize) {
547+
// Forward to the wrapped values so a caching inner cursor (e.g.
548+
// `PrimitiveValues`) can refresh its cached current/previous value.
549+
self.values.set_offset(offset);
550+
}
441551
}
442552

443553
#[cfg(test)]
@@ -463,7 +573,7 @@ mod tests {
463573
let reservation = consumer.register(&memory_pool);
464574

465575
let values = ArrayValues {
466-
values: PrimitiveValues(values),
576+
values: PrimitiveValues::new(values),
467577
null_threshold,
468578
options,
469579
_reservation: reservation,

‎datafusion/physical-plan/src/sorts/merge.rs‎

Lines changed: 12 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -294,9 +294,18 @@ impl<C: CursorValues> SortPreservingMergeStream<C> {
294294
// Adjust the loser tree if necessary, returning control if needed
295295
if !self.loser_tree_adjusted {
296296
let winner = self.loser_tree[0];
297-
if let Err(e) = ready!(self.maybe_poll_stream(cx, winner)) {
298-
self.done = true;
299-
return Poll::Ready(Some(Err(e)));
297+
// Fast path: the winner's cursor is still live for almost every
298+
// row, so avoid the `maybe_poll_stream` call (and its `Poll`
299+
// plumbing) unless the cursor is actually exhausted and needs a
300+
// fresh `RecordBatch`.
301+
if self.cursors[winner].is_none() {
302+
match ready!(self.maybe_poll_stream(cx, winner)) {
303+
Ok(()) => {}
304+
Err(e) => {
305+
self.done = true;
306+
return Poll::Ready(Some(Err(e)));
307+
}
308+
}
300309
}
301310
self.update_loser_tree();
302311
}

0 commit comments

Comments
 (0)