s-unscrupulous opened a new pull request, #56804: URL: https://github.com/apache/spark/pull/56804
### What changes were proposed in this pull request? Add a loser tree based k-way merger as an opt-in alternative to the existing priority-queue (binary heap) based `UnsafeSorterSpillMerger` used by `UnsafeExternalSorter` to merge spill files. The new merger is gated behind config `spark.unsafe.sorter.spill.merger.useLoserTree`, defaulting to `false` so behavior is unchanged unless explicitly enabled. ### Why are the changes needed? When `UnsafeExternalSorter` produces many spill files, the merge phase is dominated by comparator cost. A loser tree performs one comparison and one loser-slot read per level on each replay, versus two comparisons plus two child reads for heap sift-down. For k-way merges this roughly halves both the number of comparisons and the array touches per popped record, improving end-to-end sort latency for spill-heavy workloads. ### Does this PR introduce _any_ user-facing change? No. The new behavior is gated behind an internal config defaulted to `false`. Existing behavior is unchanged. ### How was this patch tested? - New unit test suite `UnsafeLoserTreeSpillMergerSuite` (12 tests, all pass) - Extended `UnsafeExternalSorterSuite` to cover the loser tree path - New `SpillMergerBenchmark` for performance comparison - Ran `./dev/scalastyle` and `./dev/lint-java` locally — both pass ### Was this patch authored or co-authored using generative AI tooling? Generated-by: Claude (Anthropic) -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
