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: Robert Haas <robertmhaas@gmail.com>, Pg Hackers <pgsql-hackers@postgresql.org>, Corey Huinker <corey.huinker@gmail.com>
Date: 2016-09-07T05:36:49Z
Lists: pgsql-hackers 
On Tue, Sep 6, 2016 at 10:28 PM, Heikki Linnakangas <hlinnaka@iki.fi> wrote:
>> BTW, the way that k-way merging is made more efficient by this
>> approach makes the case for replacement selection even weaker than it
>> was just before we almost killed it.
>
>
> This also makes the replacement selection cheaper, no?

Well, maybe, but the whole idea behind replacement_sort_tuples (by
which I mean the continued occasional use of replacement selection by
Postgres) was that we hope to avoid a merge step *entirely*. This new
merge shift down heap patch could make the merge step so cheap as to
be next to free anyway (in the even of presorted input), so the
argument for replacement_sort_tuples is weakened further. It might
always be cheaper once you factor in that the TSS_SORTEDONTAPE path
for returning tuples to caller happens to not be able to use batch
memory, even with something like collated text. And, as a bonus, you
get something that works just as well with an inverse correlation,
which was traditionally the worst case for replacement selection (it
makes it produce runs no larger than those produced by quicksort).

Anyway, I only mention this because it occurs to me. I have no desire
to go back to talking about replacement selection either. Maybe it's
useful to point this out, because it makes it clearer still that
severely limiting the use of replacement selection in 9.6 was totally
justified.

-- 
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