Re: The case for removing replacement selection sort

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.

--
Peter Geoghegan