Re: Is tuplesort_heap_siftup() a misnomer?

On Thu, Sep 8, 2016 at 12:46 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>
> /*
> * The tuple at state->memtuples[0] has been removed from the heap.
> - * Decrement memtupcount, and sift up to maintain the heap invariant.
> + * Decrement memtupcount, and shift down to maintain the heap invariant.
> */
> static void
> -tuplesort_heap_siftup(Tuplesortstate *state, bool checkIndex)
> +tuplesort_heap_delete_top(Tuplesortstate *state, bool checkIndex)
>
> I don't find this clearer at all, because
>
> (1) As noted in the comment, the heap top has *already* been removed,
> we're just trying to re-establish the heap invariant. So maybe
> "delete_top" isn't the best name after all.

This is why I suggested tuplesort_heap_compact(). When merging, there
is a comment associated with a call to the function, "compact the
heap". I based my name off of that, thinking that that was really no
different to any other caller.

> (2) "shift down" seems a bit weird, since we're moving data closer to
> the heap top, not further away from it; why isn't that direction "up"?

Well, the fact that the routine does that makes it a higher level
thing than something like a sift or a shift. It might just as easily
be some other tuple (e.g., from the caller), as far as "shifting down"
goes. (I wrote a patch where for merging, it *is* from the caller, and
the heap stays the same size, which Heikki mentioned on this thread.)

> (3) "shift" makes it sound like it ought to be a simple memmove
> kind of operation, which it surely is not.

Then, how about the Sedgewick terminology, "sink"? I'm really not
attached to that aspect. I do think that "shift down" is unambiguous,
but I'd just as soon use "sink", or even explicitly spell it out.

--
Peter Geoghegan