Re: [HACKERS] Tuning current tuplesort external sort code for 8.2
On Tue, 2005-10-04 at 00:21 -0400, Tom Lane wrote: Simon Riggs [EMAIL PROTECTED] writes: AFAICS the following opportunities exist, without changing any of the theoretical algorithms or the flexibility of definable datatypes: 1. tuplesort_heap_siftup and tuplesort_heap_insert make no attempt to cache the values of keys that have been obtained from *_getattr macros. The two routines navigate a tournament sort heap, so that on average 50% of comparisons use at least one immediately preceeding tuple and key values from that could be cached ready for the next call. Hmm ... this seems interesting, but you also have to look at the potential downside: what is the cost of doing the caching? Actually, nothing for the cache-1-tuple case. We just re-initialise the fcinfo based around whether we are caching 0,1 or 2 fields. We keep two fcinfo structures, so that when we cache=0 fields we do not pollute the cache for the cache=1 case. tuplesort_heap_insert allows us to cache one value each time round the inner loop, always using fcinfo1. (cache=1). tuplesort_heap_siftup has two comparisons per iteration; it allows us to cache 0 values on the first call, so we use fcinfo0. We can always cache one value for the second call, exactly same as _heap_insert case, so we use fcinfo1. Maybe we can also reuse the winner from the first call as the second input to the second call. ehem...It's easier to see when you look at the code. We need to work a bit harder to get the cache=2 case but its possible, though I take your point that it may not be worth it. I'll do the cache=1 case before attempting the cache=2 case, so we can measure the gain. We run _heap_insert and _heap_siftup once for each incoming tuple, so the saving should be good. All of the remaining ideas relate to NULL handling. I can't get excited about this. Most sort scenarios involve few if any nulls. The idea would be much less important anyway if you follow up on this next idea: One thought that comes to mind is that the current system structure encourages sorting on keys that are at the end of their tuples. For instance, SELECT foo, bar FROM ... ORDER BY baz will sort by the third column of the generated tuples, which is certainly the least efficient to access. Not sure what goes on in there. Are you saying heap sort cols are always at the end, or only in the cases you mention? What about where we're doing a GROUP BY, so all the sort columns are always part of the select list and frequently (by coding convention) at the front of the row? If the cols aren't always in resjunk we can come up with some performance test cases to check whether or not this is a problem, how big and where it starts to show itself. It'd be interesting to look into generating the working tuples with baz as the first column. I fear this is nontrivial, because there are a lot of places that expect resjunk columns to come last, but we should study it. It could be worth it to arrange the main select's attr list so that the sort keys always come first. I'd settle just for that if the second part is too much work. It sounds like hard work to optimise the case where the ORDER BY is on columns not mentioned in the select. The latter seems worth it for when we do a sort-merge based on join columns not mentioned in the SELECT, but not for optimizing sort-aggregate or one-table-select cases. (Note: this will do nada for Josh's original complaint about index build time, since btree index sorts will by definition use all the tuple's columns, but it seems like a significant issue for ordinary sorts.) Understood, but we do care about heap sorts too! Heap and index sorts have many dissimilarities, but both are important, so perhaps we should tune for each case separately. Best Regards, Simon Riggs ---(end of broadcast)--- TIP 4: Have you searched our list archives? http://archives.postgresql.org
Re: [HACKERS] Tuning current tuplesort external sort code for 8.2
On Tue, Oct 04, 2005 at 12:37:51AM +0100, Simon Riggs wrote: On Mon, 2005-10-03 at 23:25 +0200, Martijn van Oosterhout wrote: Please note: if inlineApplySortFunction() is actually inlined (it isn't by default) Can you explain your last post some more. Thats not what I get. The inline keyword is just a flag that you would like the compiler to inline it. GCC will decide itself. It has a limit on the size of functions that it will consider for inlining. Quote the gcc manual: -finline-limit-N By default, gcc limits the size of functions that can be inlined. This flag allows the control of this limit for functions that are explicitly marked as inline (ie marked with the inline keyword or defined within the class definition in c++). N is the size of functions that can be inlined in number of pseudo instructions (not counting parameter handling). It goes in to say that the limit is 1 for gcc 2.95, but if you examine the manual for gcc 3.3 it has the limit at 600. So it's entirely possible that at the time the person wrote that code, it *was* being inlined, but it sure isn't on some versions of some compilers. I experimented and found that -finline-limit-1500 causes it to start inlining. The -Winline flag causes gcc to print a warning if you specified inline but gcc didn't inline it, for whatever reason. Hopefully this clears that up. -- Martijn van Oosterhout kleptog@svana.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. pgpSmmXmACi5l.pgp Description: PGP signature
Re: [HACKERS] Tuning current tuplesort external sort code for 8.2
On Tue, Oct 04, 2005 at 11:55:58AM +0200, Martijn van Oosterhout wrote: It goes in to say that the limit is 1 for gcc 2.95, but if you examine the manual for gcc 3.3 it has the limit at 600. So it's entirely possible that at the time the person wrote that code, it *was* being inlined, but it sure isn't on some versions of some compilers. I experimented and found that -finline-limit-1500 causes it to start inlining. From searching the web, it appears the inline limit was dropped from 1 to 600 between gcc 3.0.0 and 3.0.1 in response to complaints about gcc memory usage. Any function that could be inlined needed to be kept in memory in semicompiled form and in C++ where lots of inlinable functions call eachother, the memory usage blew up completely. The difference between -O2 and -O3 is that the latter will consider any function for inlining, even if you didn't ask. For C programs that basically means any function declared static. Also, the number is pseudo-instructions and their meaning can change from version to version. Since we're pretty much relying on gcc to inline for performance, I still think we should add -Winline by default so we can tell when it's not doing what we want. Hope this helps, -- Martijn van Oosterhout kleptog@svana.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. pgpkTvFoZ4PXA.pgp Description: PGP signature
Re: [HACKERS] Tuning current tuplesort external sort code for 8.2
On Tue, 2005-10-04 at 12:37 +0200, Martijn van Oosterhout wrote: Since we're pretty much relying on gcc to inline for performance, I still think we should add -Winline by default so we can tell when it's not doing what we want. Very much agree to this. Can we put that in the build for 8.1 please? People need to know we expect certain code to be inlined and they need warnings when this does not occur. Best Regards, Simon Riggs ---(end of broadcast)--- TIP 1: if posting/reading through Usenet, please send an appropriate subscribe-nomail command to [EMAIL PROTECTED] so that your message can get through to the mailing list cleanly
Re: [HACKERS] 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 ((1attnum)-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) ((1attnum)-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@svana.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. pgpWTkP5cRja6.pgp Description: PGP signature
Re: [HACKERS] Tuning current tuplesort external sort code for 8.2
On Mon, 2005-10-03 at 23:25 +0200, Martijn van Oosterhout wrote: Possible problem with caching: if you're called by the system qsort, can you assume anything about the order of the comparisons? That applies only to the non-external sort case, which I'm not trying to improve with these suggestions. (No, you can't assume that, it was a heapsort only suggestion). Please note: if inlineApplySortFunction() is actually inlined (it isn't by default) Can you explain your last post some more. Thats not what I get. 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 ((1attnum)-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: You may be right, the exact code that brings the right benefit is somewhat trickier than spotting the opportunity. 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. But an interesting one. Once we've done everything else, that use case is close to the top of my list, if the performance gain was still as useful, all other things considered. Best Regards, Simon Riggs ---(end of broadcast)--- TIP 6: explain analyze is your friend
Re: [HACKERS] Tuning current tuplesort external sort code for 8.2
Simon Riggs [EMAIL PROTECTED] writes: AFAICS the following opportunities exist, without changing any of the theoretical algorithms or the flexibility of definable datatypes: 1. tuplesort_heap_siftup and tuplesort_heap_insert make no attempt to cache the values of keys that have been obtained from *_getattr macros. The two routines navigate a tournament sort heap, so that on average 50% of comparisons use at least one immediately preceeding tuple and key values from that could be cached ready for the next call. Hmm ... this seems interesting, but you also have to look at the potential downside: what is the cost of doing the caching? All of the remaining ideas relate to NULL handling. I can't get excited about this. Most sort scenarios involve few if any nulls. One thought that comes to mind is that the current system structure encourages sorting on keys that are at the end of their tuples. For instance, SELECT foo, bar FROM ... ORDER BY baz will sort by the third column of the generated tuples, which is certainly the least efficient to access. It'd be interesting to look into generating the working tuples with baz as the first column. I fear this is nontrivial, because there are a lot of places that expect resjunk columns to come last, but we should study it. (Note: this will do nada for Josh's original complaint about index build time, since btree index sorts will by definition use all the tuple's columns, but it seems like a significant issue for ordinary sorts.) regards, tom lane ---(end of broadcast)--- TIP 1: if posting/reading through Usenet, please send an appropriate subscribe-nomail command to [EMAIL PROTECTED] so that your message can get through to the mailing list cleanly
