Re: The case for removing replacement selection sort

On Wed, Aug 30, 2017 at 6:14 PM, Peter Geoghegan <pg(at)bowt(dot)ie> wrote:
> 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.

Wow. Just to be clear, I am looking for the BEST case for replacement
selection, not the worst case. But I would have expected that case to
be a win for replacement selection, and it clearly isn't. I can
reproduce your results here.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company