Re: WIP: further sorting speedup

The improvement was pre-Simon¹s patch, and it came from implementing a
single pass merge instead of a variable pass based on the number of tapes,
as it is in Knuth¹s tape algorithm. Also, the additional tricks in
logtape.c were higher in the profile than what I see here.

Simon¹s patch had the effect of reducing the number of passes by increasing
the number of tapes depending on the memory available, but that¹s a long
tail effect as seen in figure (70?) in Knuth.

Where I¹d like this to go is the implementation of a two pass ³create runs,
merge², where the second merge can be avoided unless random access is needed
(as discussed previously on list).

In the run creation phase, the idea would be to implement something like
quicksort or another L2-cache friendly algorithm (ideas?)

- Luke

On 2/19/06 8:19 PM, "Tom Lane" <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:

> "Luke Lonergan" <llonergan(at)greenplum(dot)com> writes:
>> > So you know, we=B9ve done some more work on the external sort to remove the
>> > =B3tape=B2 abstraction from the code, which makes a significant
>> improvement.
>
> Improvement where? That code's down in the noise so far as I can tell.
> I see results like this (with the patched code):
>
> CPU: P4 / Xeon with 2 hyper-threads, speed 2793.08 MHz (estimated)
> Counted GLOBAL_POWER_EVENTS events (time during which processor is not
> stopped)
> with a unit mask of 0x01 (mandatory) count 240000
> samples % symbol name
> 147310 31.9110 tuplesort_heap_siftup
> 68381 14.8130 comparetup_index
> 34063 7.3789 btint4cmp
> 22573 4.8899 AllocSetAlloc
> 19317 4.1845 writetup_index
> 18953 4.1057 tuplesort_gettuple_common
> 18100 3.9209 mergepreread
> 17083 3.7006 GetMemoryChunkSpace
> 12527 2.7137 LWLockAcquire
> 11686 2.5315 LWLockRelease
> 6172 1.3370 tuplesort_heap_insert
> 5392 1.1680 index_form_tuple
> 5323 1.1531 PageAddItem
> 4943 1.0708 LogicalTapeWrite
> 4525 0.9802 LogicalTapeRead
> 4487 0.9720 LockBuffer
> 4217 0.9135 heapgettup
> 3891 0.8429 IndexBuildHeapScan
> 3862 0.8366 ltsReleaseBlock
>
> It appears that a lot of the cycles blamed on tuplesort_heap_siftup are
> due to cache misses associated with referencing memtuples[] entries
> that have fallen out of L2 cache. Not sure how to improve that though.
>
> regards, tom lane
>
>