[
https://issues.apache.org/jira/browse/SPARK-59748?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
ASF GitHub Bot updated SPARK-59748:
-----------------------------------
Labels: pull-request-available (was: )
> 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
> Priority: Minor
> Labels: pull-request-available
>
> 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]
