Re: [PATCH] Incremental sort

On Wed, Apr 26, 2017 at 7:56 PM, Peter Geoghegan <pg(at)bowt(dot)ie> wrote:

> On Wed, Apr 26, 2017 at 8:39 AM, Alexander Korotkov
> <a(dot)korotkov(at)postgrespro(dot)ru> wrote:
> > That appears to be wrong. I intended to make cost_sort prefer plain sort
> > over incremental sort for this dataset size. But, that appears to be not
> > always right solution. Quick sort is so fast only on presorted data.
>
> As you may know, I've often said that the precheck for sorted input
> added to our quicksort implementation by a3f0b3d is misguided. It
> sometimes throws away a ton of work if the presorted input isn't
> *perfectly* presorted. This happens when the first out of order tuple
> is towards the end of the presorted input.
>
> I think that it isn't fair to credit our qsort with doing so well on a
> 100% presorted case, because it doesn't do the necessary bookkeeping
> to not throw that work away completely in certain important cases.
>

OK, I get it. Our qsort is so fast not only on 100% presorted case.
However, that doesn't change many things in context of incremental sort.

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company