david-mollitor-db opened a new pull request, #58949: URL: https://github.com/apache/spark/pull/58949
### What changes were proposed in this pull request? The external-sort spill merge (`UnsafeSorterSpillMerger` / `UnsafeSorterBoundedSpillMerger`, reached via `UnsafeExternalSorter.getSortedIterator()`) orders spill-run heads by the 8-byte key prefix and, on a prefix tie, falls back to the full `RecordComparator` (which decodes and byte-compares the records). When the sort qualifies for radix sort (`canUseRadixSort` -- a single, prefix-sortable key), the prefix is a lossless, order-preserving **total order** for that key, so equal prefixes are equal keys and the `RecordComparator` tie-break always returns 0. This PR threads the already-computed `canUseRadixSort` flag (previously only forwarded to `UnsafeInMemorySorter` and then dropped) into both merge paths -- the single-round `UnsafeSorterSpillMerger` and the multi-round `UnsafeSorterBoundedSpillMerger` -- so the record comparator is skipped on prefix ties in that case. It is the merge-side analogue of the in-memory radix-sort optimization. No SQL-side changes are needed; the flag already arrives at `UnsafeExternalSorter.create()`. ### Why are the changes needed? `UnsafeExternalSorter` backs `SortExec` and key-based aggregation/window/join (via `UnsafeKVExternalSorter`). On a spilled sort with a single prefix-sortable key, every prefix collision in the merge currently pays for a full record decode + comparison that provably returns 0. Skipping it removes that dead work; the effect is largest for low-cardinality or duplicate-heavy keys where prefix ties are frequent, and neutral otherwise. ### Does this PR introduce _any_ user-facing change? No. The result is identical for all inputs. Skipping the tie-break is safe because `canUseRadixSort` guarantees the prefix fully determines the sort order (equal prefix = equal key), so the record comparator would have returned 0 anyway -- the same precondition the in-memory radix sort already relies on (each spilled run was ordered by prefix alone). Sorts with `canUseRadixSort=false` (multi-key sorts, strings/binary, large decimals) keep the record-comparator tie-break unchanged. ### How was this patch tested? `UnsafeExternalSorterSuite` and `UnsafeExternalSorterRadixSortSuite` pass (60 tests). Added `testSortingWithDuplicatePrefixesAcrossSpills`, which inserts many records with duplicated key prefixes across several spill files and asserts the merged output stays in non-decreasing prefix order with every record preserved. It runs in both the base suite (record-comparator path) and the radix subclass (the new skip path). ### 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]
