You are viewing a plain text version of this content. The canonical link for it is here.
Posted to reviews@spark.apache.org by "david-mollitor-db (via GitHub)" <gi...@apache.org> on 2026/09/23 14:34:25 UTC
[PR] [SPARK-59748][CORE] Loser tree + small-k linear merge for UnsafeSorterSpillMerger [spark]
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: reviews-unsubscribe@spark.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
Re: [PR] [SPARK-59748][CORE] Loser tree + small-k linear merge for UnsafeSorterSpillMerger [spark]
Posted by "david-mollitor-db (via GitHub)" <gi...@apache.org>.
david-mollitor-db commented on PR #58998:
URL: https://github.com/apache/spark/pull/58998#issuecomment-5874864711
Hi @vboo123, thanks again for the thorough review! I have addressed all five points -- the long-counter termination fix (covering the bounded final round too), the PriorityQueue baseline with committed per-JDK results and the k=9/12 crossover points, the real 9-plus-spill loser-tree test, the exactly-8/9-run boundary tests, and the single-use guard. Ready for another pass whenever you have a moment. Thank you!
--
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: reviews-unsubscribe@spark.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
Re: [PR] [SPARK-59748][CORE] Loser tree + small-k linear merge for UnsafeSorterSpillMerger [spark]
Posted by "david-mollitor-db (via GitHub)" <gi...@apache.org>.
david-mollitor-db commented on PR #58998:
URL: https://github.com/apache/spark/pull/58998#issuecomment-6195632336
Hi @mridulm, you mentioned on #56804 that a loser tree gave a nontrivial improvement for the k-way merge, so I was hoping you might be able to take a look at this one when you have a moment. It replaces the `PriorityQueue` inside `UnsafeSorterSpillMerger` itself, so both the single-round merge and the final round of the bounded merge use it, with a linear scan for up to 8 runs and cached key prefixes. The description covers how it relates to #56804, and @vboo123 has reviewed it. Thank you!
--
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: reviews-unsubscribe@spark.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org