Skip to content

Commit 5d24591

Browse files
Dandandanclaude
andauthored
Perf: avoid redundant comparison in SortPreservingMerge round-robin tie-breaker; optimize inner loop (#23107)
## Which issue does this PR close? - Closes: #23108 ## Rationale for this change `SortPreservingMergeStream` (the loser-tree k-way merge behind `SortPreservingMergeExec`, and `SortExec`'s spill/streaming merge) uses a round-robin tie-breaker — enabled by default — applied at the root comparison. Two small inefficiencies on the hot `update_loser_tree` path: 1. At the root it compared the two finalists with `==` and then, when not equal, again with `>` — up to **two** comparisons per output row where the non-tie-breaker path does one. For byte-wise row comparisons (multi-column keys) and string keys the extra comparison per row is measurable. 2. The round-robin handling only applies at the root (`cmp_node == 1`), yet the per-node loop tested `cmp_node == 1` (and carried the tie-breaker branch) on every node. On sort_tpch it shows some nice gains: ``` │ Q4 │ 213.82 / 216.41 ±2.86 / 221.41 ms │ 196.81 / 200.38 ±3.91 / 206.99 ms │ +1.08x faster │ │ Q5 │ 300.12 / 300.95 ±0.45 / 301.43 ms │ 280.25 / 281.01 ±1.13 / 283.25 ms │ +1.07x faster │ │ Q6 │ 313.95 / 318.37 ±7.24 / 332.81 ms │ 293.26 / 294.82 ±1.24 / 296.98 ms │ +1.08x faster │ ``` ## What changes are included in this PR? - Collapse the root `==` + `>` into a single `Ord::cmp` and match on the `Ordering`. - Lift the root comparison out of the per-node loop, leaving a tight `is_gt` inner loop (`while cmp_node > 1`) that no longer checks `cmp_node == 1` per node. ## Are these changes tested? Covered by the existing tests in `sorts/merge.rs` and `sorts/sort_preserving_merge.rs` (including `test_round_robin_tie_breaker_success` / `test_round_robin_tie_breaker_fail` and the merge ordering tests). Behavior-preserving, so no new tests are added. ## Are there any user-facing changes? No. Co-authored-by: Claude Opus 4.8 (1M context) <[email protected]>
1 parent dc92bb8 commit 5d24591

1 file changed

Lines changed: 21 additions & 10 deletions

File tree

  • datafusion/physical-plan/src/sorts

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

Lines changed: 21 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -512,22 +512,33 @@ impl<C: CursorValues> SortPreservingMergeStream<C> {
512512
let mut cmp_node = self.lt_leaf_node_index(winner);
513513

514514
// Traverse up the tree to adjust comparisons until reaching the root.
515-
while cmp_node != 0 {
515+
while cmp_node > 1 {
516516
let challenger = self.loser_tree[cmp_node];
517+
if self.is_gt(winner, challenger) {
518+
self.update_winner(cmp_node, &mut winner, challenger);
519+
}
520+
cmp_node = self.lt_parent_node_index(cmp_node);
521+
}
522+
523+
if cmp_node == 1 {
524+
let challenger = self.loser_tree[1];
517525
// If round-robin tie-breaker is enabled and we're at the final comparison (cmp_node == 1)
518-
if self.enable_round_robin_tie_breaker && cmp_node == 1 {
526+
if self.enable_round_robin_tie_breaker {
519527
match (&self.cursors[winner], &self.cursors[challenger]) {
520-
(Some(ac), Some(bc)) => {
521-
if ac == bc {
528+
(Some(ac), Some(bc)) => match ac.cmp(bc) {
529+
std::cmp::Ordering::Equal => {
522530
self.handle_tie(cmp_node, &mut winner, challenger);
523-
} else {
531+
}
532+
std::cmp::Ordering::Greater => {
524533
// Ends of tie breaker
525534
self.round_robin_tie_breaker_mode = false;
526-
if ac > bc {
527-
self.update_winner(cmp_node, &mut winner, challenger);
528-
}
535+
self.update_winner(cmp_node, &mut winner, challenger);
529536
}
530-
}
537+
std::cmp::Ordering::Less => {
538+
// Ends of tie breaker
539+
self.round_robin_tie_breaker_mode = false;
540+
}
541+
},
531542
(None, _) => {
532543
// Challenger wins, update winner
533544
// Ends of tie breaker
@@ -543,8 +554,8 @@ impl<C: CursorValues> SortPreservingMergeStream<C> {
543554
} else if self.is_gt(winner, challenger) {
544555
self.update_winner(cmp_node, &mut winner, challenger);
545556
}
546-
cmp_node = self.lt_parent_node_index(cmp_node);
547557
}
558+
548559
self.loser_tree[0] = winner;
549560
self.loser_tree_adjusted = true;
550561
}

0 commit comments

Comments
 (0)