[ENG] Re: [Bizgres-general] Slow glibc qsort, two versions that are much faster

[Luke Lonergan]

Kurt,

On 12/9/05 1:03 AM, "Kurt Harriman" <kharriman at greenplum.com> wrote:

> Luke Lonergan wrote:
>> How does the existing logic work to choose between the N-tape algorithm and
>> the in-memory one?  Is it based on the estimated stats?
> 
> It accumulates tuples in memory until it runs into the memory limit of
> work_mem * 1024 bytes.  If the supply of tuples is exhausted before
> hitting the work_mem limit, it uses qsort; otherwise it uses heapsort /
> replacement selection / 6-way merge.  It does not use estimated stats.

Thanks, yah - estimated stats would be pretty fragile.

We've found some queries in the past that benefit tremendously with a better
qsort(), they must have been able to fit the sort set in RAM.

It seems like we should suggest the use of a postgres supplied qsort
implementation if it shows substantial performance benefits over current
vendor implementations.  Interesting that the GNU implementation is now the
performance loser compared to BSD and Solaris :-)

The only benefit to the BSD routine compared to the qsortG routine seems to
be the degenerate case of a sort set with identical keys.  It appears that
there is a fast exit in that case for the BSD qsort, not a big loss in the
qsortG case.  The degenerate set sorts in time slightly faster than the
random set for qsortG.

- Luke