Horton

Re: Polyphase merge is obsolete

Tom Lane <tgl@sss.pgh.pa.us>

View thread View on postgr.es
From: Tom Lane <tgl@sss.pgh.pa.us>
To: Heikki Linnakangas <hlinnaka@iki.fi>
Cc: pgsql-hackers <pgsql-hackers@postgresql.org>
Date: 2016-10-12T17:27:25Z
Lists: pgsql-hackers 
Heikki Linnakangas <hlinnaka@iki.fi> writes:
> The beauty of the polyphase merge algorithm is that it allows reusing 
> input tapes as output tapes efficiently ... So the whole idea of trying to 
> efficiently reuse input tapes as output tapes is pointless.

It's been awhile since I looked at that code, but I'm quite certain that
it *never* thought it was dealing with actual tapes.  Rather, the point of
sticking with polyphase merge was that it allowed efficient incremental
re-use of temporary disk files, so that the maximum on-disk footprint was
only about equal to the volume of data to be sorted, rather than being a
multiple of that.  Have we thrown that property away?

			regards, tom lane

Commits

  1. Fix and clarify function comment on LogicalTapeSetCreate.

  2. Refactor LogicalTapeSet/LogicalTape interface.

  3. Replace polyphase merge algorithm with a simple balanced k-way merge.

  4. logtape.c: do not preallocate for tapes when sorting