Re: Tuning current tuplesort external sort code for 8.2

On Mon, Oct 03, 2005 at 09:35:30PM +0100, Simon Riggs wrote:
> Based upon profiling of the initial stage of external sorting, it seems
> that this stage is overall CPU bound, with hotspots in comparetup_*
> accounting for around 50% of CPU time; lets just call that too much,
> since your exact experience may vary.

Indeed, however as I pointed out, if you arrange for
inlineApplySortFunction() actually be inlined, you can cut costs,
especially in the index creation case.

<snip>
> values from that could be cached ready for the next call. Caching would
> reduce number of *_getattr calls from 2N to N+1, where N is likely to go

My profiling indicates that the second getattr is half the cost of the
first, gcc optimisation at work. Note that setting CFLAGS=-pg for
configure disables optimisation, I missed that the first time.
Ofcourse, every call saved is time saved.

> 2. In comparetup_ the second attr value is always fetched, even when the
> first attr is null. When the first attr is null the value of the second
> need never be checked, just whether the second attr is null or not, so
> the full cost of the *_getattr need not actually be paid at all. The
> relevance of this is not reduced as a result of the caching suggested in
> (1).

Actually, attribute is null is the cheap case because you only need to
check the bitmap. But you could optimise stuff by expanding the
*_getattr calls and optimising directly. Possible problem with caching:
if you're called by the system qsort, can you assume anything about the
order of the comparisons?

Please note: if inlineApplySortFunction() is actually inlined (it isn't
by default), gcc does get very smart about this and sometimes optimises
out the Datum fetches depending on the isNull flags. So we need to
check we're actually making an improvement over the compiler.

<snip>

> is a subset of the PK (a typical one-many relationship) and groupings
> also. In the majority of cases, these attrs are at the start of a tuple.
> The *_getattr macros are particularly poor at handling NULLs. When
> *_getattr sees *any* NULL is present for a tuple it checks the
> nullability of all attrs up to the current attrnum before returning
> using the cached offsets. The macro could be altered so that if the
> current attrnum < firstNullableAttrnum (which we can set once for the

Maybe easier, in the macro use: bitmap & ((1<<attnum)-1) to quickly
check that no nulls precede the value we're looking for and hence we
can use the fast path anyway. Along the lines of:

#define index_getattr(tup, attnum, tupleDesc, isnull) \
( \
AssertMacro(PointerIsValid(isnull) && (attnum) > 0), \
*(isnull) = false, \
!IndexTupleHasNulls(tup) || (attnum < 32 && (NullBitmap(tup) & ((1<<attnum)-1)) == 0 ) ? \
( \
(tupleDesc)->attrs[(attnum)-1]->attcacheoff >= 0 ? \

Nice ideas though, a seperate run just for NULL keys is interesting. If
you only have one sort key it becomes a whole tape which doesn't need
to be sorted anymore, just emit it at the beginning or end. Could be
helpful.

Mind you, if you start creating seperate routines for different cases
you can go a long way. Elsewhere on this list I created a special case
for single-key integer index columns and got an 8% speed increase. Not
exactly a viable solution though.

Have a nice day,
--
Martijn van Oosterhout <kleptog(at)svana(dot)org> http://svana.org/kleptog/
> Patent. n. Genius is 5% inspiration and 95% perspiration. A patent is a
> tool for doing 5% of the work and then sitting around waiting for someone
> else to do the other 95% so you can sue them.