Thread: pgsql: Replace polyphase merge algorithm with a simple balanced k-way m

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(-)

On 18/10/2021 15:15, Heikki Linnakangas wrote:
> Replace polyphase merge algorithm with a simple balanced k-way merge.

This patch made some buildfarm animals fail in the isolation tests.

'eelpout' seems to have ran out of disk space:

> +setup failed: ERROR:  could not write to file "base/pgsql_tmp/pgsql_tmp915834.0.fileset/0.1": No space left on
device

Maybe I was unlucky. However, 'francolin', 'desmoxytes', 'dragonet' and 
'idiacanthus' also failed, in the same test:

> ==~_~===-=-===~_~== pgsql.build/src/test/isolation/output_iso/regression.diffs ==~_~===-=-===~_~==
> diff -U3
/mnt/resource/bf/build/francolin/HEAD/pgsql.build/../pgsql/src/test/isolation/expected/multiple-row-versions.out
/mnt/resource/bf/build/francolin/HEAD/pgsql.build/src/test/isolation/output_iso/results/multiple-row-versions.out
> --- /mnt/resource/bf/build/francolin/HEAD/pgsql.build/../pgsql/src/test/isolation/expected/multiple-row-versions.out
 2021-10-05 04:13:04.811944633 +0000
 
> +++ /mnt/resource/bf/build/francolin/HEAD/pgsql.build/src/test/isolation/output_iso/results/multiple-row-versions.out
  2021-10-18 12:34:35.036779419 +0000
 
> @@ -2,10 +2,9 @@
>  
>  starting permutation: rx1 wx2 c2 wx3 ry3 wy4 rz4 c4 c3 wz1 c1
>  step rx1: SELECT * FROM t WHERE id = 1000000;
> -     id|txt
> --------+---
> -1000000|   
> -(1 row)
> +id|txt
> +--+---
> +(0 rows)
>  
>  step wx2: UPDATE t SET txt = 'b' WHERE id = 1000000;
>  step c2: COMMIT;
> @@ -26,5 +25,4 @@
>  step c4: COMMIT;
>  step c3: COMMIT;
>  step wz1: UPDATE t SET txt = 'a' WHERE id = 1;
> -ERROR:  could not serialize access due to read/write dependencies among transactions
>  step c1: COMMIT;
> ==~_~===-=-===~_~== inst/logfile ==~_~===-=-===~_~==

The symptom is different, there is no "out of disk space" error, but it 
kind of looks like an index was built incorrectly, because the simple 
SELECT doesn't return the row that it should.

That sure smells like a bug in the new sorting code. I haven't been able 
to reproduce that yet, but I'll keep trying. It's strange that this 
doesn't happen in any other test, that is a very ordinary table with a 
very ordinary index.

- Heikki