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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
