Horton

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

Robert Haas <robertmhaas@gmail.com>

View thread View on postgr.es
From: Robert Haas <robertmhaas@gmail.com>
To: Amit Kapila <amit.kapila16@gmail.com>
Cc: Peter Geoghegan <pg@heroku.com>, Heikki Linnakangas <hlinnaka@iki.fi>, Claudio Freire <klaussfreire@gmail.com>, Pg Hackers <pgsql-hackers@postgresql.org>, Corey Huinker <corey.huinker@gmail.com>, Tom Lane <tgl@sss.pgh.pa.us>
Date: 2016-10-19T14:39:57Z
Lists: pgsql-hackers 
On Mon, Oct 17, 2016 at 8:36 AM, Amit Kapila <amit.kapila16@gmail.com> wrote:
>> This project of mine is about parallelizing tuplesort.c, which isn't
>> really what you want for parallel query -- you shouldn't try to scope
>> the problem as "make the sort more scalable using parallelism" there.
>> Rather, you want to scope it at "make the execution of the entire
>> query more scalable using parallelism", which is really quite a
>> different thing, which necessarily involves the executor having direct
>> knowledge of partition boundaries.
>
> Okay, but what is the proof or why do you think second is going to
> better than first?  One thing which strikes as a major difference
> between your approach and Gather Merge is that in your approach leader
> has to wait till all the workers have done with their work on sorting
> whereas with Gather Merge as soon as first one is done, leader starts
> with merging.  I could be wrong here, but if I understood it
> correctly, then there is a argument that Gather Merge kind of approach
> can win in cases where some of the workers can produce sorted outputs
> ahead of others and I am not sure if we can dismiss such cases.

Gather Merge can't emit a tuple unless it has buffered at least one
tuple from every producer; otherwise, the next tuple it receives from
one of those producers might proceed whichever tuple it chooses to
emit.  However, it doesn't need to wait until all of the workers are
completely done.  The leader only needs to be at least slightly ahead
of the slowest worker.  I'm not sure how that compares to Peter's
approach.

What I'm worried about is that we're implementing two separate systems
to do the same thing, and that the parallel sort approach is actually
a lot less general.  I think it's possible to imagine a Parallel Sort
implementation which does things Gather Merge can't.  If all of the
workers collaborate to sort all of the data rather than each worker
sorting its own data, then you've got something which Gather Merge
can't match.  But this is not that.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

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