Re: Using quicksort and a merge step to significantly improve on tuplesort's single run "external sort"

On 07/31/2015 02:01 AM, Peter Geoghegan wrote:
> What prevents the tuple at the top of the in-memory heap at the point
> of tuplesort_performsort() (say, one of the ones added to the heap as
> our glut of memory was*partially* consumed) being less than the
> last/greatest tuple on tape? If the answer is "nothing", a merge step
> is clearly required.

Oh, ok, I was confused on how the heap works. You could still abstract
this as "in-memory tails" of the tapes, but it's more complicated than I
thought at first:

When it's time to drain the heap, in performsort, divide the array into
two arrays, based on the run number of each tuple, and then quicksort
the arrays separately. The first array becomes the in-memory tail of the
current tape, and the second array becomes the in-memory tail of the
next tape.

You wouldn't want to actually allocate two arrays and copy SortTuples
around, but keep using the single large array, just logically divided
into two. So the bookkeeping isn't trivial, but seems doable.

Hmm, I can see another possible optimization here, in the way the heap
is managed in TSS_BUILDRUNS state. Instead of keeping a single heap,
with tupindex as the leading key, it would be more cache efficient to
keep one heap for the currentRun, and an unsorted array of tuples
belonging to currentRun + 1. When the heap becomes empty, and currentRun
is incemented, quicksort the unsorted array to become the new heap.

That's a completely separate idea from your patch, although if you did
it that way, you wouldn't need the extra step to divide the large array
into two, as you'd maintain that division all the time.

- Heikki