Re: qsort, once again

Well, my point was that it is a snap to implement and test.

It will be better, worse, or the same.

I agree that Bentley is a bloody genius.

> -----Original Message-----
> From: Tom Lane [mailto:tgl@sss.pgh.pa.us]
> Sent: Thursday, March 16, 2006 9:27 PM
> To: Dann Corbit
> Cc: Jonah H. Harris; pgsql-hackers@postgresql.org; Jerry Sievers
> Subject: Re: [HACKERS] qsort, once again
>
> "Dann Corbit" <DCorbit@connx.com> writes:
> >> So my feeling is we should just remove the swap_cnt code and return
> >> to the original B&M algorithm.
>
> > Even if "hunks" of the input are sorted, the test is a very good
idea.
>
> Yah know, guys, Bentley and McIlroy are each smarter than any five of
> us, and I'm quite certain it occurred to them to try prechecking for
> sorted input.  If that case is not in their code then it's probably
> because it's a net loss.  Unless you have reason to think that sorted
> input is *more* common than other cases for the Postgres environment,
> which is certainly a fact not in evidence.
>
> (Bentley was my thesis adviser for awhile before he went to Bell Labs,
> so my respect for him is based on direct personal experience.  McIlroy
> I only know by reputation, but he's sure got a ton of that.)
>
> > Imagine also a table that was clustered but for which we have not
> > updated statistics.  Perhaps it is 98% sorted.  Checking for order
in
> > our partitions is probably a good idea.
>
> If we are using the sort code rather than the recently-clustered index
> for such a case, then we have problems elsewhere.  This scenario is
not
> a good argument that the sort code needs to be specialized to handle
> this case at the expense of other cases; the place to be fixing it is
> the planner or the statistics-management code.
>
>             regards, tom lane