Uploaded image for project: 'IMPALA'
  1. IMPALA
  2. IMPALA-10961

Implement 3-way quicksort in sorter

    XMLWordPrintableJSON

Details

    • Improvement
    • Status: Resolved
    • Major
    • Resolution: Fixed
    • None
    • Impala 4.1.0
    • Backend
    • ghx-label-9

    Description

      Using 3-way partitioning in quicksort could massively speed up sorting if there is a large number of duplicate elements. This is very common in sorts before partitioned inserts.

      Attachments

        1. checksorted.patch
          4 kB
          Kurt Deschler
        2. qsort.cc
          9 kB
          Kurt Deschler

        Issue Links

          causes

          Bug - A problem which impairs or prevents the functions of the product. IMPALA-11144 verifyApproxCardinality() failed in testAggregationNodeGroupByCardinalityCapping

          • Major - Major loss of function.
          • Resolved
          duplicates

          Improvement - An improvement or enhancement to an existing feature or task. IMPALA-3357 Sorter's quicksort implementation is very suboptimal for duplicate keys

          • Minor - Minor loss of function, or other problem where easy workaround is present.
          • Resolved
          fixes

          Bug - A problem which impairs or prevents the functions of the product. IMPALA-11230 Crash in partitioned top-N codegen'd code

          • Critical - Crashes, loss of data, severe memory leak.
          • Resolved
          relates to

          Sub-task - The sub-task of the issue IMPALA-6692 When partition exchange is followed by sort each sort node becomes a synchronization point across the cluster

          • Critical - Crashes, loss of data, severe memory leak.
          • Reopened

          Activity

            People

              noemi Noemi Pap-Takacs
              csringhofer Csaba Ringhofer
              Votes:
              0 Vote for this issue
              Watchers:
              7 Start watching this issue

              Dates

                Created:
                Updated:
                Resolved: