[IMPALA-3357] Sorter's quicksort implementation is very suboptimal for duplicate keys

• Type: Improvement
• Status: Resolved
• Priority: Minor
• Resolution: Later
• Affects Version/s: Impala 2.6.0
• Component/s: Backend
• Labels: perf ramp-up
• Target Version: Product Backlog
• Assignee: Norbert Luksa
• Reporter: Tim Armstrong
• Created: 14/Apr/16 17:55
• Updated: 08/Feb/22 11:58
• Resolved: 24/Oct/19 17:26

Description

void Sorter::TupleSorter::SortHelper(TupleIterator first, TupleIterator last) {
  if (UNLIKELY(state_->is_cancelled())) return;
  // Use insertion sort for smaller sequences.
  while (last.index_ - first.index_ > INSERTION_THRESHOLD) {
    TupleIterator iter(this, first.index_ + (last.index_ - first.index_) / 2);
    DCHECK(iter.current_tuple_ != NULL);
    // Partition() splits the tuples in [first, last) into two groups (<= pivot
    // and >= pivot) in-place. 'cut' is the index of the first tuple in the second group.
    TupleIterator cut = Partition(first, last,
        reinterpret_cast<Tuple*>(iter.current_tuple_));
    SortHelper(cut, last);
    last = cut;
    if (UNLIKELY(state_->is_cancelled())) return;
  }

  InsertionSort(first, last);
}

The quicksort implementation in the sorter is based on dividing the input into two partitions: <= pivot and >= pivot.

If all of the input values in a partition are equal, then it will still recursively divide and do insertion sort on the values. We could change the sorter to partition the input into three partitions: <, == and >. Then it doesn't need to recurse on the middle partition. This would mean it could sort a partition full of duplicate values in a single pass over the input.

Issue Links

• is duplicated by: IMPALA-10961 Implement 3-way quicksort in sorter
• is related to: IMPALA-6044 Analytic planner misses some opportunities to merge partition groups
• relates to: IMPALA-3354 Sorter can overflow stack on large sorts