Repository navigation
Commit 5d24591
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
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
512 | 512 | | |
513 | 513 | | |
514 | 514 | | |
515 | | - | |
| 515 | + | |
516 | 516 | | |
| 517 | + | |
| 518 | + | |
| 519 | + | |
| 520 | + | |
| 521 | + | |
| 522 | + | |
| 523 | + | |
| 524 | + | |
517 | 525 | | |
518 | | - | |
| 526 | + | |
519 | 527 | | |
520 | | - | |
521 | | - | |
| 528 | + | |
| 529 | + | |
522 | 530 | | |
523 | | - | |
| 531 | + | |
| 532 | + | |
524 | 533 | | |
525 | 534 | | |
526 | | - | |
527 | | - | |
528 | | - | |
| 535 | + | |
529 | 536 | | |
530 | | - | |
| 537 | + | |
| 538 | + | |
| 539 | + | |
| 540 | + | |
| 541 | + | |
531 | 542 | | |
532 | 543 | | |
533 | 544 | | |
| |||
543 | 554 | | |
544 | 555 | | |
545 | 556 | | |
546 | | - | |
547 | 557 | | |
| 558 | + | |
548 | 559 | | |
549 | 560 | | |
550 | 561 | | |
| |||
0 commit comments