Replace polyphase merge algorithm with a simple balanced k-way merge.
authorHeikki Linnakangas <[email protected]>
Mon, 18 Oct 2021 11:33:42 +0000 (14:33 +0300)
committerHeikki Linnakangas <[email protected]>
Mon, 18 Oct 2021 11:46:01 +0000 (14:46 +0300)
commit65014000b351d5725eb00d133416ab1b4f8245b1
tree5af1e1b2ac788c2945752065c6eaedb93465f34a
parentc4649cce39a41b27db874e75ddd47adaec1b0ea4
Replace polyphase merge algorithm with a simple balanced k-way merge.

The advantage of polyphase merge is that it can reuse the input tapes as
output tapes efficiently, but that is irrelevant on modern hardware, when
we can easily emulate any number of tape drives. The number of input tapes
we can/should use during merging is limited by work_mem, but output tapes
that we are not currently writing to only cost a little bit of memory, so
there is no need to skimp on them.

This makes sorts that need multiple merge passes faster.

Discussion: https://www.postgresql.org/message-id/420a0ec7-602c-d406-1e75-1ef7ddc58d83%40iki.fi
Reviewed-by: Peter Geoghegan, Zhihong Yu, John Naylor
src/backend/utils/sort/tuplesort.c