Horton

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

Amit Kapila <amit.kapila16@gmail.com>

View thread View on postgr.es
From: Amit Kapila <amit.kapila16@gmail.com>
To: Peter Geoghegan <pg@heroku.com>
Cc: Robert Haas <robertmhaas@gmail.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-21T10:57:55Z
Lists: pgsql-hackers 
On Fri, Oct 21, 2016 at 4:25 PM, Amit Kapila <amit.kapila16@gmail.com> wrote:
> On Tue, Oct 18, 2016 at 3:48 AM, Peter Geoghegan <pg@heroku.com> wrote:
>> On Mon, Oct 17, 2016 at 5:36 AM, Amit Kapila <amit.kapila16@gmail.com> wrote:
>>
>> I read the following paragraph from the Volcano paper just now:
>>
>> """
>> During implementation and benchmarking of parallel sorting, we added
>> two more features to exchange. First, we wanted to implement a merge
>> network in which some processors produce sorted streams merge
>> concurrently by other processors. Volcano’s sort iterator can be used
>> to generate a sorted stream. A merge iterator was easily derived from
>> the sort module. It uses a single level merge, instead of the cascaded
>> merge of runs used in sort. The input of a merge iterator is an
>> exchange. Differently from other operators, the merge iterator
>> requires to distinguish the input records by their producer. As an
>> example, for a join operation it does not matter where the input
>> records were created, and all inputs can be accumulated in a single
>> input stream. For a merge operation, it is crucial to distinguish the
>> input records by their producer in order to merge multiple sorted
>> streams correctly.
>> """
>>
>> I don't really understand this paragraph, but thought I'd ask: why the
>> need to "distinguish the input records by their producer in order to
>> merge multiple sorted streams correctly"? Isn't that talking about
>> partitioning, where each workers *ownership* of a range matters?
>>
>
> I think so, but it seems from above text that is mainly required for
> merge iterator which probably will be used in merge join.
>
>> My
>> patch doesn't care which values belong to which workers. And, it
>> focuses quite a lot on dealing well with the memory bandwidth bound,
>> I/O bound part of the sort where we write out the index itself, just
>> by piggy-backing on tuplesort.c. I don't think that that's useful for
>> a general-purpose executor node -- tuple-at-a-time processing when
>> fetching from workers would kill performance.
>>
>
> Right, but what is written in text quoted by you seems to be do-able
> with tuple-at-a-time processing.
>

To be clear, by saying above, I don't mean that we should try that
approach instead of what you are proposing, but it is worth some
discussion to see if that has any significant merits.

-- 
With Regards,
Amit Kapila.
EnterpriseDB: http://www.enterprisedb.com

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