Re: The case for removing replacement selection sort

On Mon, Sep 11, 2017 at 8:32 AM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
> On Sun, Sep 10, 2017 at 9:39 PM, Peter Geoghegan <pg(at)bowt(dot)ie> wrote:
>> To be clear, you'll still need to set replacement_sort_tuples high
>> when testing RS, to make sure that we really use it for at least the
>> first run when we're expected to. (There is no easy way to have
>> testing mechanically verify that we really do only have one run in the
>> end with RS, but I assume that such paranoia is unneeded.)
>
> I seem to recall that raising replacement_sort_tuples makes
> replacement selection look worse in some cases -- the optimization is
> more likely to apply, sure, but the heap is also bigger, which hurts.

But that was only because work_mem was set relatively high. If you're
going to test work_mem values that are slightly on the high side for
replacement selection (like, 8MB or 32MB), then increasing
replacement_sort_tuples ensures that replacement selection is actually
used for at least the first run, and you don't waste time comparing a
behavior (quicksorting runs) to itself.

All that matters is whether or not replacement_sort_tuples exceeds the
number of tuples that the first run would have if quicksorted
immediately. replacement_sort_tuples is only ever used to answer a
single yes/no question.

--
Peter Geoghegan