From: Heikki Linnakangas <heikki.linnakangas@iki.fi>
To: pgsql-committers@lists.postgresql.org
Subject: pgsql: Replace polyphase merge algorithm with a simple balanced k-way m
Date: Mon, 18 Oct 2021 12:15:09 +0000
Message-ID: <E1mcRXp-0000e9-0Y@gemulon.postgresql.org> (raw)
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
Branch
------
master
Details
-------
https://git.postgresql.org/pg/commitdiff/65014000b351d5725eb00d133416ab1b4f8245b1
Modified Files
--------------
src/backend/utils/sort/tuplesort.c | 662 ++++++++++++++++---------------------
1 file changed, 293 insertions(+), 369 deletions(-)
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients from your mail client; the link fills in
the headers below: reply via email
Some clients, webmail especially, drop In-Reply-To and References from
a link, and the reply then starts a new thread: use the mbox below.
To: pgsql-committers@postgresql.org
Cc: heikki.linnakangas@iki.fi
Subject: Re: pgsql: Replace polyphase merge algorithm with a simple balanced k-way m
In-Reply-To: <E1mcRXp-0000e9-0Y@gemulon.postgresql.org>
References: <E1mcRXp-0000e9-0Y@gemulon.postgresql.org>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox