Re: The case for removing replacement selection sort

On Wed, Aug 30, 2017 at 4:18 PM, Peter Geoghegan <pg(at)bowt(dot)ie> wrote:
> On Wed, Aug 30, 2017 at 12:51 PM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
>> On Fri, Jul 14, 2017 at 6:20 PM, Peter Geoghegan <pg(at)bowt(dot)ie> wrote:
>>> With the additional enhancements made to Postgres 10, I doubt that
>>> there are any remaining cases where it wins.
>>
>> The thing to do about that would be to come up with some cases where
>> someone might plausibly think it would win and benchmark them to find
>> out what happens. I find it really hard to believe that sorting a
>> long presorted stream of tuples (or, say, 2-1-4-3-6-5-8-7-10-9 etc.)
>> is ever going to be as fast with any other algorithm as it is with
>> replacement selection.
>
> Replacement selection as implemented in Postgres is supposed to be
> about the "single run, no merge" best case. This must use
> TSS_SORTEDONTAPE processing, which is optimized for random access,
> which is usually the wrong thing.
>
> In general, sorting is only one cost that is involved here, and is not
> the predominant cost with presorted input.

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.

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