david-mollitor-db opened a new pull request, #58998: URL: https://github.com/apache/spark/pull/58998
### What changes were proposed in this pull request? `UnsafeExternalSorter` merges its sorted spill runs (plus the in-memory run) in `UnsafeSorterSpillMerger` using a `java.util.PriorityQueue<UnsafeSorterIterator>`. Emitting each record does `poll()` + `add()` -- two O(log k) sift passes -- and every comparison calls `getKeyPrefix()` on both runs, falling to the record comparator on a prefix tie. This replaces the heap with two run-count-dependent strategies and caches the prefix: - a **linear min-scan** for a small number of runs (`<= 8`), and - a **loser (tournament) tree** above that -- one replace-top adjustment (~`log2(k)` comparisons) per record, with no re-insertion; - each live run's current key prefix is cached in a parallel `long[]`, refreshed when the run advances, so comparisons read a cached `long` instead of calling `getKeyPrefix()`, falling to the record comparator only on a prefix tie. The `UnsafeSorterSpillMerger` constructor and its `addSpillIfNotEmpty` / `getSortedIterator` methods are unchanged, so both the single-round merge and the bounded multi-round merge (`UnsafeSorterBoundedSpillMerger`) benefit. Ordering is preserved: key prefix first, then the record comparator on a tie. A `UnsafeSorterSpillMergerBenchmark` is added under `core` to measure the merge in isolation. ### Why are the changes needed? The `PriorityQueue` does two sift passes per record (poll + add) and its comparison indirection is comparatively expensive. A loser tree does a single replace-top per record at the same O(log k), and for a handful of runs a flat linear scan is cheaper still. Low-cardinality / duplicate-heavy keys -- frequent prefix ties -- are exactly the workloads that spill and merge most. `UnsafeSorterSpillMergerBenchmark` (merge CPU only: in-memory runs, 4.19M records) reports time-per-record vs. the `PriorityQueue` baseline, by run count `k`: ``` distinct prefixes: k=2 1.46x k=4 2.00x k=8 2.14x k=16 1.88x k=64 1.79x duplicate prefixes: k=2 1.32x k=4 1.50x k=8 1.48x k=16 1.60x k=64 1.42x ``` This isolates merge CPU and excludes spill read/decode I/O, so it is an upper bound on the end-to-end effect; a forced-spill end-to-end measurement is a reasonable follow-up. This PR is a draft pending that measurement. ### Does this PR introduce _any_ user-facing change? No. This is an internal change to the external-sort spill merge. The merged output ordering is unchanged (key prefix, then the record comparator on a tie), and there are no API or configuration changes. ### How was this patch tested? Existing `UnsafeExternalSorterSuite` and its radix subclass `UnsafeExternalSorterRadixSortSuite` pass (58 tests); their multi-spill and bounded-merge cases exercise both the linear and loser-tree paths, and ordering semantics are unchanged. Added `UnsafeSorterSpillMergerBenchmark` for the numbers above (the results file is not committed). ### Was this patch authored or co-authored using generative AI tooling? Generated-by: Isaac This pull request and its description were written by Isaac. -- 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]
