> -----Original Message-----
> From: pgsql-hackers-owner@postgresql.org [mailtogsql-hackers-
> owner@postgresql.org] On Behalf Of Qingqing Zhou
> Sent: Thursday, December 15, 2005 3:16 PM
> To: Greg Stark
> Cc: Jim C. Nasby; Luke Lonergan; Tom Lane; Neil Conway; Bruce Momjian;
> pgsql-hackers@postgresql.org
> Subject: Re: [HACKERS] Which qsort is used
>
>
>
> 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.

Radix sort can also be made completely generic by using a callback
function.

The function gives back n-bits at a time, from the most significant bits
to the least significant.

So, for char string, and a radix of 256, you just return the first char,
then the second char, etc. to get the classical radix sort.

Radix sort is no advantage for long, similar strings. Suppose that you
have a comparison sort that is O(n*log(n)). If n is one billion items,
then log2(n) is 32 and therefore LSD radix 256 sorts of 33 character
fields will be slower than a comparison sort, even for one billion
items.


---------------------------(end of broadcast)---------------------------
TIP 2: Don't 'kill -9' the postmaster

"Dann Corbit" <DCorbit@connx.com> writes:
> Radix sort can also be made completely generic by using a callback
> function.
> The function gives back n-bits at a time, from the most significant bits
> to the least significant.

That's mighty handwavy --- it assumes that the datatype permits a simple
breakdown into small pieces that can be sorted lexicographically. Seems
to me that's a much stronger requirement than assuming that you can tell
which of two whole values is smaller. What's worse, it needs to be the
same number of pieces for every value, which makes it hard to deal with
variable-length data.

> So, for char string, and a radix of 256, you just return the first char,
> then the second char, etc. to get the classical radix sort.

Uh, no, you'd need to work right-to-left, after having padded all the
strings to the same length somehow.

regards, tom lane

---------------------------(end of broadcast)---------------------------
TIP 9: In versions below 8.0, the planner will ignore your desire to
choose an index scan if your joining column's datatypes do not
match