On Thu, 15 Dec 2005, Greg Stark wrote:
>
> I have a related question. qsort is only used in the postgres source in a few
> places. If postgres used an internal implementation instead of the library
> source it could have implementations that don't use function pointers. This
> might perform faster for a few reasons. The comparator is much more likely to
> be eligible for inlining for one.
>
> It also opens the door to using different sort algorithms for different
> applications. There may be some cases where the input is never sorted and the
> sample size is small so qsort is a good choice, and others where the inputs
> can be large and using a better algorithm with worse overhead like mergesort
> might make more sense.
>
> Unfortunately there isn't just a single qsort call though. I count 6
> comparators in the source tree I have. So perhaps this is a non-starter.
> Having 6 qsort implementations around sounds pretty sketchy.
>
[also with reply to Tom] Both ideas look like doable (or at least
testable) for me. I agree that the only interesting pot is in tuplesort.c.
For the 2nd idea, for smaller range, we may consider radix sort, which is
definitely faster - but this may need some work that enable query
optimizer know the *exact* data range.
Regards,
Qingqing