On 06/02/14 18:21, Jeff Janes wrote:
> How big of
> sets were you sorting in each case?
Big enough to go external. The timings and compare-counts given are
purely for the heapify stage not the total for the sort, so are
constrained by the work_mem not by the sort size per se.
I'm limited to working on a small machine, so the work_mem value
of 1e+6 is approaching my top limit of sort-time pain unless I rip the
heapify out into a test harness. What range of work_mem is it useful
to test over?
> Was it always just slightly bigger
> than would fit in work_mem?
I didn't check.
> Did you try sorting already-sorted, reverse
> sorted, or pipe-organ shaped data sets?
Not yet, but I can. What variety of pipe-organ shape is of
interest (I can think of several that might be called that)?
> We will also need to test it on
> strings. I usually use md5(random()::text) to generate strings for such
> purposes, at least for a first pass.
OK.
>
> The name of the attached patch is a bit unfortunate.
Is there a project standard for this?
> And I'm not sure what
> you are doing with tupindex, the change there doesn't seem to be necessary
> to the rest of your work, so some explanation on that would be helpful.
I'll add commentary.
> The project coding style usually has comments in blocks before loops on
> which they comment, rather than interspersed throughout the clauses of the
> "for" statement.
I'll adjust that.
> Another optimization that is possible is to do only one comparison at each
> level (between the two children) all the way down the heap, and then
> compare the parent to the chain of smallest children in reverse order.
> This can substantially reduce the number of comparisons on average,
> because most tuples sift most of the way down the heap (because most of the
> tuples are at the bottom of the heap).
Sounds interesting; I'll see if I can get that going.
> (Also, I think you should make your siftdown code look more like the
> existing siftdown code.)
A function called by the outer loop? Can do; the existing does that
because the function is called from multiple places but this will only
be used the once.
Thanks for the review.
--
Jeremy
