[jira] [Created] (SPARK-59748) Replace the PriorityQueue k-way spill merge with a loser tree and small-k linear scan

["David Mollitor (Jira)" <ji...@apache.org>]

David Mollitor created SPARK-59748:
--------------------------------------

             Summary: Replace the PriorityQueue k-way spill merge with a loser tree and small-k linear scan
                 Key: SPARK-59748
                 URL: https://issues.apache.org/jira/browse/SPARK-59748
             Project: Spark
          Issue Type: Improvement
          Components: Spark Core
    Affects Versions: 4.1.0
            Reporter: David Mollitor


h3. Summary

{{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 that 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.
h3. Why

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. Code-column / low-cardinality keys (frequent prefix ties, many duplicate keys) are exactly where merges spill most and benefit most.



--
This message was sent by Atlassian Jira
(v8.20.10#820010)

---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@spark.apache.org
For additional commands, e-mail: issues-help@spark.apache.org