Re: [HACKERS] Tuplesort merge pre-reading

On 04/14/2017 08:19 AM, Peter Geoghegan wrote:
> BTW, I'm skeptical of the idea of Heikki's around killing polyphase
> merge itself at this point. I think that keeping most tapes active per
> pass is useful now that our memory accounting involves handing over an
> even share to each maybe-active tape for every merge pass, something
> established by Heikki's work on external sorting.

The pre-read buffers are only needed for input tapes; the total number 
of tapes doesn't matter.

For comparison, imagine that you want to perform a merge, such that you 
always merge 7 runs into one. With polyphase merge, you would need 8 
tapes, so that you always read from 7 of them, and write onto one. With 
balanced merge, you would need 14 tapes: you always read from 7 tapes, 
and you would need up to 7 output tapes, of which one would be active at 
any given time.

Those extra idle output tapes are practically free in our 
implementation. The "pre-read buffers" are only needed for input tapes, 
the number of output tapes doesn't matter. Likewise, maintaining the 
heap is cheaper if you only merge a small number of tapes at a time, but 
that's also dependent on the number of *input* tapes, not the total 
number of tapes.

- Heikki