Stephen, On 3/9/06 3:48 PM, "Stephen Frost" <[EMAIL PROTECTED]> wrote:
> So, if we get a huge performance increase, what's wrong with: > if [ sqrt(est(total)) <= work_mem ]; then > two-pass-sort(); > else > tape-sort(); > fi I have something similar but less complex in mind. One of the observed behaviors with the current approach is that increasing work_mem actually slows external sorting down. This is because the heapsort embedded in the replacement selection algorithm in the tape sort is not L2 cache friendly. The easiest, simplest algorithm to employ here would be to quicksort in chunks of work_mem to produce the runs, output them in a simple manner to heap files, then merge them in one pass, materializing if necessary for random access. Granted there are seek optimizations necessary to make the merge pass efficient, but these are obviously tractable in a simple manner as evidenced by others (Nyquist) and our own internal experiments. The simplicity of this is that the current approach switches from a quicksort to the polyphase tape sort when work_mem is exceeded, which involves a fairly complex chunk of code right now. In this new approach, when the sort set exceeds work_mem, we just write it out and continue. > If the intent is to remove it and then ask for the default work_mem to > be increased- I doubt going about it this way would work very well. :) Yep - the main question to address is whether work_mem is always sufficient to buffer the merge results in one pass, or whether degenerating to a multi-pass can be done gracefully if not. Tim Kordas here plans to work on this sometime next week using code he's already written, and I'd expect a pretty quick set of improvements through this simplified approach. - Luke ---------------------------(end of broadcast)--------------------------- TIP 5: don't forget to increase your free space map settings
