Claire McGinty created BEAM-11048:
-------------------------------------
Summary: Add alternate Sorting transform as an implementation of
CombineFn
Key: BEAM-11048
URL: https://issues.apache.org/jira/browse/BEAM-11048
Project: Beam
Issue Type: Improvement
Components: extensions-java-sorter
Reporter: Claire McGinty
My team has been using the
[SortValues|https://github.com/apache/beam/blob/master/sdks/java/extensions/sorter/src/main/java/org/apache/beam/sdk/extensions/sorter/SortValues.java]
transform in `extensions-java-sorter` to sort pre-grouped values by a
secondary sorter key. However, for large key groups, we've run into many OOM
issues and have to increase disk size quite a bit to accommodate the larger key
groups spilling to disk, even if there are only a few large key groups and most
fit in memory.
I drafted a new iteration of a Sorter that's a distributed merge-sort
implemented as a `CombineFn`: each Accumulator maintains an always-sorted list
of elements, and those Accumulators can be merged simply by zipping their lists
together. This has the extra advantage that `extractOutput` can be lazily
evaluated as a merging Iterator rather than as a fully materialized list. I
also observed that this implementation is able to scale more effectively than
the old SortValues, and for several use cases where `SortValues` ran OOM, the
CombineFn-based implementation was able to complete using only the default
Dataflow disk specs.
Finally, from an API perspective, I think it's a little easier to use, because
the user doesn't have to extract the sortKey out into the PCollection itself,
but instead provide a function mapping each element type T to its sort key K,
which will be evaluated inside the combiner. So I think in that sense it's more
intuitive and similar to a Comparator-style sort.
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
