Uploaded image for project: 'Beam'
  1. Beam
  2. BEAM-11048

Add alternate Sorting transform as an implementation of CombineFn

    XMLWordPrintableJSON

    Details

    • Type: Improvement
    • Status: Open
    • Priority: P3
    • Resolution: Unresolved
    • Affects Version/s: None
    • Fix Version/s: None
    • Component/s: extensions-java-sorter
    • Labels:

      Description

      My team has been using the SortValues 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.

        Attachments

          Issue Links

            Activity

              People

              • Assignee:
                Unassigned
                Reporter:
                clairemcginty Claire McGinty
              • Votes:
                0 Vote for this issue
                Watchers:
                3 Start watching this issue

                Dates

                • Created:
                  Updated:

                  Time Tracking

                  Estimated:
                  Original Estimate - Not Specified
                  Not Specified
                  Remaining:
                  Remaining Estimate - 0h
                  0h
                  Logged:
                  Time Spent - 0.5h
                  0.5h