Uploaded image for project: 'Calcite'
  1. Calcite
  2. CALCITE-3820

EnumerableDefaults#orderBy should be lazily computed + support enumerator re-initialization

VotersWatch issueWatchersLinkCloneUpdate Comment AuthorReplace String in CommentUpdate Comment VisibilityDelete Comments
    XMLWordPrintableJSON

Details

    • Improvement
    • Status: Closed
    • Major
    • Resolution: Fixed
    • 1.21.0
    • 1.23.0
    • core

    Description

      Currently, EnumerableDefaults#orderBy (which is the actual implementation behind EnumerableSort) looks like this:

      public static <TSource, TKey> Enumerable<TSource> orderBy(
          Enumerable<TSource> source, Function1<TSource, TKey> keySelector,
          Comparator<TKey> comparator) {
        final Map<TKey, List<TSource>> map = new TreeMap<>(comparator);
        LookupImpl<TKey, TSource> lookup = toLookup_(map, source, keySelector,
            Functions.identitySelector());
        return lookup.valuesEnumerable();
      }
      

      This implementation has the following disadvantages:

      • 1) The TreeMap that performs the actual sorting is eagerly computed. This operation can be quite heavy if we have a very big source. The fact that it is eagerly computed might lead to bad performance in situations where the sort is executed, but it is actually not needed. For example, in a NestedLoopJoin, if the outer enumerator returns no results, the inner one is not even accessed. If we had a huge orderBy as inner, today it would be computed in that scenario, even though it is not actually required. For this reason, in terms of performance it seems clearly preferable to delay the sort operation as much as possible.
      • 2) The Enumerable / Enumerator returned by EnumerableDefaults#orderBy cannot be re-evaluated. Since the map and the subsequent LookupImpl that the Enumerable relies on are eagerly computed, every call to enumerator will return the same values, even if the source Enumerable has changed. This is a corner case, but we can see it if, for example, we have a MergeJoin, with EnumerableSort (i.e. using EnumerableDefaults#orderBy) inside a RepeatUnion (a.k.a. recursive union). In this situation, the RepeatUnion re-evaluates its right child, so that the output of the iteration N-1 is used as input for the iteration N. In this scenario, the EnumerableDefaults#orderBy will not work as expected, since it will not be actually re-computed (see EnumerableMethods#repeatUnion)

      Attachments

        Activity

          This comment will be Viewable by All Users Viewable by All Users
          Cancel

          People

            rubenql Ruben Q L
            rubenql Ruben Q L
            Votes:
            0 Vote for this issue
            Watchers:
            3 Start watching this issue

            Dates

              Created:
              Updated:
              Resolved:

              Time Tracking

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

                Slack

                  Issue deployment