Re: [HACKERS] Is tuplesort_heap_siftup() a misnomer?

2016-09-08 Thread Claudio Freire
On Thu, Sep 8, 2016 at 2:19 PM, Peter Geoghegan wrote: >> Peter, looking at your "displace" patch in this light, I think >> tuplesort_heap_root_displace() and tuplesort_heap_delete_top() (as I'm >> calling it now), should share a common subroutine. Displace replaces the top >>

Re: [HACKERS] Is tuplesort_heap_siftup() a misnomer?

2016-09-08 Thread Peter Geoghegan
On Thu, Sep 8, 2016 at 2:09 PM, Tom Lane wrote: > Well, my vote is that it ain't broke and we shouldn't fix it. To take a step back, what prompted this whole discussion is the patch that I wrote that shifts down, replacing calls to tuplesort_heap_siftup() and

Re: [HACKERS] Is tuplesort_heap_siftup() a misnomer?

2016-09-08 Thread Tom Lane
Peter Geoghegan writes: > On Thu, Sep 8, 2016 at 1:14 PM, Andres Freund wrote: >> Is this issue really worth keeping several hackers busy? > I don't think it's fair to put it to me specifically that I'm doing > that. That said, I would like to see this

Re: [HACKERS] Is tuplesort_heap_siftup() a misnomer?

2016-09-08 Thread Peter Geoghegan
On Thu, Sep 8, 2016 at 1:14 PM, Andres Freund wrote: > Is this issue really worth keeping several hackers busy? I don't think it's fair to put it to me specifically that I'm doing that. That said, I would like to see this resolved without further bikeshedding. -- Peter

Re: [HACKERS] Is tuplesort_heap_siftup() a misnomer?

2016-09-08 Thread Andres Freund
Hi, Is this issue really worth keeping several hackers busy? Andres -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Is tuplesort_heap_siftup() a misnomer?

2016-09-08 Thread Peter Geoghegan
On Thu, Sep 8, 2016 at 12:46 PM, Tom Lane 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.

Re: [HACKERS] Is tuplesort_heap_siftup() a misnomer?

2016-09-08 Thread Tom Lane
Peter Geoghegan writes: > Attached patch does it that way, then. I stuck with the reference to > "shift down", though, since I think we all agree that that is > unambiguous. I dunno. What you've now got is /* * The tuple at state->memtuples[0] has been removed from the

Re: [HACKERS] Is tuplesort_heap_siftup() a misnomer?

2016-09-08 Thread Peter Geoghegan
Sift means shift up. There is no such thing as sift down, though, only shift down. That is my understanding, based on the Wikipedia article on heaps. -- Peter Geoghegan

Re: [HACKERS] Is tuplesort_heap_siftup() a misnomer?

2016-09-08 Thread Claudio Freire
On Thu, Sep 8, 2016 at 4:20 PM, Peter Geoghegan wrote: > On Thu, Sep 8, 2016 at 10:40 AM, Tom Lane wrote: >>> On Thu, Sep 8, 2016 at 12:01 AM, Heikki Linnakangas wrote: I still think tuplesort_heap_siftup is a confusing name, although

Re: [HACKERS] Is tuplesort_heap_siftup() a misnomer?

2016-09-08 Thread Peter Geoghegan
On Thu, Sep 8, 2016 at 10:40 AM, Tom Lane wrote: >> On Thu, Sep 8, 2016 at 12:01 AM, Heikki Linnakangas wrote: >>> I still think tuplesort_heap_siftup is a confusing name, although I'm not >>> sure that Peter's "compact" is much better. I suggest that we

Re: [HACKERS] Is tuplesort_heap_siftup() a misnomer?

2016-09-08 Thread Tom Lane
Peter Geoghegan writes: > On Thu, Sep 8, 2016 at 12:01 AM, Heikki Linnakangas wrote: >> I still think tuplesort_heap_siftup is a confusing name, although I'm not >> sure that Peter's "compact" is much better. I suggest that we rename it to >>

Re: [HACKERS] Is tuplesort_heap_siftup() a misnomer?

2016-09-08 Thread Peter Geoghegan
On Thu, Sep 8, 2016 at 12:01 AM, Heikki Linnakangas wrote: > I still think tuplesort_heap_siftup is a confusing name, although I'm not > sure that Peter's "compact" is much better. I suggest that we rename it to > tuplesort_heap_delete_top(). In comments within the function,

Re: [HACKERS] Is tuplesort_heap_siftup() a misnomer?

2016-09-08 Thread Heikki Linnakangas
On 09/08/2016 03:36 AM, Peter Geoghegan wrote: On Wed, Sep 7, 2016 at 2:42 PM, Tom Lane wrote: The reason it's called siftup is that that's what Knuth calls it. See Algorithm 5.2.3H (Heapsort), pp 146-147 in the first edition of Volume 3; tuplesort_heap_siftup corresponds

Re: [HACKERS] Is tuplesort_heap_siftup() a misnomer?

2016-09-07 Thread Peter Geoghegan
On Wed, Sep 7, 2016 at 2:42 PM, Tom Lane wrote: > The reason it's called siftup is that that's what Knuth calls it. > See Algorithm 5.2.3H (Heapsort), pp 146-147 in the first edition of > Volume 3; tuplesort_heap_siftup corresponds directly to steps H3-H8. I see that Knuth

Re: [HACKERS] Is tuplesort_heap_siftup() a misnomer?

2016-09-07 Thread Tom Lane
Peter Geoghegan writes: > On Fri, Aug 12, 2016 at 4:30 PM, Peter Geoghegan wrote: >> Doesn't tuplesort_heap_siftup() actually shift-down? The reason it's called siftup is that that's what Knuth calls it. See Algorithm 5.2.3H (Heapsort), pp 146-147 in the first

Re: [HACKERS] Is tuplesort_heap_siftup() a misnomer?

2016-09-07 Thread Peter Geoghegan
On Fri, Aug 12, 2016 at 4:30 PM, Peter Geoghegan wrote: > Doesn't tuplesort_heap_siftup() actually shift-down? > > The Wikipedia article on heaps [1] lists "shift-down" (never "sift > down", FWIW) as a common operation on a heap: > > "shift-down: move a node down in the tree,

[HACKERS] Is tuplesort_heap_siftup() a misnomer?

2016-08-12 Thread Peter Geoghegan
Doesn't tuplesort_heap_siftup() actually shift-down? The Wikipedia article on heaps [1] lists "shift-down" (never "sift down", FWIW) as a common operation on a heap: "shift-down: move a node down in the tree, similar to shift-up; used to restore heap condition after deletion or replacement."