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: [email protected]
For additional commands, e-mail: [email protected]
