Re: The case for removing replacement selection sort

On Wed, Aug 30, 2017 at 3:01 PM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
> That may all be true, but my point is that if it wins in some cases,
> we should keep it -- and proving it no longer wins in those cases will
> require running tests.

That's not hard. On my laptop:

$ pgbench -i -s 100
...

postgres=# set work_mem = '2MB';
SET
postgres=# show replacement_sort_tuples ;
replacement_sort_tuples
─────────────────────────
150000
(1 row)
(30784) /postgres=# select count(distinct aid) from pgbench_accounts ;
count
────────────
10,000,000
(1 row)

Time: 4157.267 ms (00:04.157)
(30784) /postgres=# set replacement_sort_tuples = 0;
SET
(30784) /postgres=# select count(distinct aid) from pgbench_accounts ;
count
────────────
10,000,000
(1 row)

Time: 3343.789 ms (00:03.344)

This is significantly faster, in a way that's clearly reproducible and
consistent, despite the fact that we need about 10 merge passes
without replacement selection, and only have enough memory for 7
tapes. I think that I could find a case that makes replacement
selection look much worse, if I tried.

--
Peter Geoghegan