Polyphase merge is obsolete - Mailing list pgsql-hackers

The beauty of the polyphase merge algorithm is that it allows reusing
input tapes as output tapes efficiently. So if you have N tape drives,
you can keep them all busy throughout the merge.

That doesn't matter, when we can easily have as many "tape drives" as we
want. In PostgreSQL, a tape drive consumes just a few kB of memory, for
the buffers. With the patch being discussed to allow a tape to be
"paused" between write passes [1], we don't even keep the tape buffers
around, when a tape is not actively read written to, so all it consumes
is the memory needed for the LogicalTape struct.

The number of *input* tapes we can use in each merge pass is still
limited, by the memory needed for the tape buffers and the merge heap,
but only one output tape is active at any time. The inactive output
tapes consume very few resources. So the whole idea of trying to
efficiently reuse input tapes as output tapes is pointless.

Let's switch over to a simple k-way balanced merge. Because it's
simpler. If you're severely limited on memory, like when sorting 1GB of
data with work_mem='1MB' or less, it's also slightly faster. I'm not too
excited about the performance aspect, because in the typical case of a
single-pass merge, there's no difference. But it would be worth changing
on simplicity grounds, since we're mucking around in tuplesort.c anyway.

I came up with the attached patch to do that. This patch applies on top
of my latest "Logical tape pause/resume" patches [1]. It includes
changes to the logtape.c interface, that make it possible to create and
destroy LogicalTapes in a tapeset on the fly. I believe this will also
come handy for Peter's parallel tuplesort patch set.

[1] Logical tape pause/resume,
https://www.postgresql.org/message-id/55b3b7ae-8dec-b188-b8eb-e07604052351%40iki.fi

PS. I finally bit the bullet and got self a copy of The Art of Computer
Programming, Vol 3, 2nd edition. In section 5.4 on External Sorting,
Knuth says:

"
When this book was first written, magnetic tapes were abundant and disk
drives were expensive. But disks became enormously better during the
1980s, and by the late 1990s they had almost completely replaced
magnetic tape units on most of the world's computer systems. Therefore
the once-crucial topic of tape merging has become of limited relevance
to current needs.

Yet many of the patterns are quite beautiful, and the associated
algorithms reflect some of the best research done in computer science
during its early days; the techniques are just too nice to be discarded
abruptly onto the rubbish heap of history. Indeed, the ways in which
these methods blend theory with practice are especially instructive.
Therefore merging patterns are discussed carefully and completely below,
in what may be their last grand appearance before they accept the final
curtain call.
"

Yep, the polyphase and other merge patterns are beautiful. I enjoyed
reading through those sections. Now let's put them to rest in PostgreSQL.

- Heikki