Re: A worst case for qsort

On Fri, Aug 8, 2014 at 5:54 AM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
> Well, I'm not sure why you're having a hard time imagining it.
> Presorted input is a common case in general; that's why we have a
> check for it. That check adds overhead in the non-pre-sorted case to
> improve the pre-sorted case, and nobody's ever argued for removing it
> that I can recall.

I think that there has been a fair amount of skepticism - e.g., [1]

But that's beside the point. What I mean is that I think that the
intersection of those three things - pre-sorted input, with all
differences after the first 8 bytes, and with a user requirement to
sort using the column - is fairly rare in practice. It's not
impossible, but it is fairly rare. If that was the only case that was
actually regressed, even taking into account fmgr elision, I think
that would be quite reasonable. It wouldn't be massively regressed
either, and it's a case that's already very fast relative to other
systems anyway, if you're lucky enough to get it.

You'd better have exactly sorted tuples, though. It's been my
observation that one slight difference can drastically alter the
outcome [2].

[1] http://www.postgresql.org/message-id/18033.1361789032@sss.pgh.pa.us
[2] http://www.postgresql.org/message-id/CAEYLb_W++UhrcWprzG9TyBVF7Sn-c1s9oLbABvAvPGdeP2DFSQ@mail.gmail.com
--
Peter Geoghegan