Peter Geoghegan <p...@heroku.com> writes: > On Thu, Sep 8, 2016 at 12:01 AM, Heikki Linnakangas <hlinn...@iki.fi> 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, explain that >> the *loop* corresponds to the "siftup" in Knuth's book.
> I'm also fine with that name. I can live with it too. >> Interestingly, as Knuth explains the siftup algorithm, it performs a >> "replace the top" operation, rather than "remove the top". But we use it to >> remove the top, by moving the last element to the top and running the >> algorithm after that. Peter's other patch, to change the way we currently >> replace the top node, to do it in one pass rather than as delete+insert, is >> actually Knuth's siftup algorithm. > Knuth must have a strange sense of humor. I'm too lazy to get the book back down off the shelf to check, but I think that Knuth uses sift-up to describe two different algorithms that have essentially the same inner loop. regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers