Horton

Re: Parallel tuplesort (for parallel B-Tree index creation)

Peter Geoghegan <pg@heroku.com>

View thread View on postgr.es
From: Peter Geoghegan <pg@heroku.com>
To: Heikki Linnakangas <hlinnaka@iki.fi>
Cc: Claudio Freire <klaussfreire@gmail.com>, Robert Haas <robertmhaas@gmail.com>, Pg Hackers <pgsql-hackers@postgresql.org>, Corey Huinker <corey.huinker@gmail.com>, Tom Lane <tgl@sss.pgh.pa.us>
Date: 2016-09-11T15:52:48Z
Lists: pgsql-hackers 
On Sun, Sep 11, 2016 at 6:28 AM, Heikki Linnakangas <hlinnaka@iki.fi> wrote:
> * I renamed "tuplesort_heap_siftup()" to "tuplesort_delete_top()". I realize
> that this is controversial, per the discussion on the "Is
> tuplesort_heap_siftup() a misnomer?" thread. However, now that we have a new
> function, "tuplesort_heap_replace_top()", which is exactly the same
> algorithm as the "delete_top()" algorithm, calling one of them "siftup"
> became just too confusing.

I feel pretty strongly that this was the correct decision. I would
have gone further, and removed any mention of "Sift up", but you can't
win them all.

> * Instead of "root_displace", I used the name "replace_top", and
> "delete_top" for the old siftup function. Because we use "top" to refer to
> memtuples[0] more commonly than "root", in the existing comments.

Fine by me.

> * I shared the code between the delete-top and replace-top. Delete-top now
> calls the replace-top function, with the last element of the heap. Both
> functions have the same signature, i.e. they both take the checkIndex
> argument. Peter's patch left that out for the "replace" function, on
> performance grounds, but if that's worthwhile, that seems like a separate
> optimization. Might be worth benchmarking that separately, but I didn't want
> to conflate that with this patch.

Okay.

> * I replaced a few more siftup+insert calls with the new combined
> replace-top operation. Because why not.

I suppose that the consistency has value, from a code clarity standpoint.

> Thanks for the patch, Peter, and thanks for the review, Claudio!

Thanks Heikki!

-- 
Peter Geoghegan

Commits

  1. Support parallel btree index builds.

  2. Report an ERROR if a parallel worker fails to start properly.

  3. Transfer state pertaining to pending REINDEX operations to workers.

  4. Add a barrier primitive for synchronizing backends.

  5. Allow DML commands that create tables to use parallel query.

  6. Refactor GetOldestXmin() to use flags

  7. Fix regression in parallel planning against inheritance tables.

  8. Don't create "holes" in BufFiles, in the new logtape code.

  9. Simplify the code for logical tape read buffers.

  10. Fix excessive memory consumption in the new sort pre-reading code.

  11. Implement binary heap replace-top operation in a smarter way.

  12. Cosmetic code cleanup in commands/extension.c.

  13. Speed up planner's scanning for parallel-query hazards.

  14. Read from the same worker repeatedly until it returns no tuple.

  15. Improve tuplesort.c to support variable merge order. The original coding