Re: Inlining comparators as a performance optimisation

On Fri, Nov 18, 2011 at 12:20:26AM -0500, Robert Haas wrote:
> I think that we should really consider doing with this patch what Tom
> suggested upthread; namely, looking for a mechanism to allow
> individual datatypes to offer up a comparator function that doesn't
> require bouncing through FunctionCall2Coll(). It seems to me that
> duplicating the entire qsort() algorithm is a little iffy. Sure, in
> this case it works out to a win. But it's only a small win -
> three-quarters of it is in the uncontroversial activity of reducing
> the impedance mismatch - and how do we know it will always be a win?

There's always the old idea of a data type providing a function mapping
f:(type -> int64) in such a way that it preserves order. That is, in the
sense that:

f(x) < f(y) => x < y

When sorting, you add f(x) as hidden column and change "ORDER BY x" to
"ORDER BY f(x), x". Then you only need to special case the int64
version. This would mean that in most cases you may be able to skip
the call because you're comparing integers. The downside is you need
to call f on each input. It depends on the datatype if that's cheaper
or not, but for all numerics types I think it's an easy win.

I don't think anyone has written a proof of concept for this. It does
have the advantage of scaling better than coding a qsort for each
individual type.

Have a nice day,
--
Martijn van Oosterhout <kleptog(at)svana(dot)org> http://svana.org/kleptog/
> He who writes carelessly confesses thereby at the very outset that he does
> not attach much importance to his own thoughts.
-- Arthur Schopenhauer