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

On Sat, Aug 6, 2016 at 2:16 AM, Peter Geoghegan <pg(at)heroku(dot)com> wrote:
> On Fri, Aug 5, 2016 at 9:06 AM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
>> There are some somewhat outdated and perhaps naive ideas about this
>> that we wrote up here:
>>
>> https://wiki.postgresql.org/wiki/Parallel_Sort
>
> I'm familiar with that effort. I think that when research topics like
> sorting, it can sometimes be a mistake to not look at an approach
> specifically recommended by the database research community. A lot of
> the techniques we've benefited from within tuplesort.c have been a
> matter of addressing memory latency as a bottleneck; techniques that
> are fairly simple and not worth writing a general interest paper on.
> Also, things like abbreviated keys are beneficial in large part
> because people tend to follow the first normal form, and therefore an
> abbreviated key can contain a fair amount of entropy most of the time.
> Similarly, Radix sort seems really cool, but our requirements around
> generality seem to make it impractical.
>
>> Anyway, you're proposing an algorithm that can't be fully
>> parallelized. Maybe that's OK. But I'm a little worried about it.
>> I'd feel more confident if we knew that the merge could be done in
>> parallel and were just leaving that to a later development stage; or
>> if we picked an algorithm like the one above that doesn't leave a
>> major chunk of the work unparallelizable.
>
> I might be able to resurrect the parallel merge stuff, just to guide
> reviewer intuition on how much that can help or hurt.
>

I think here some of the factors like how many workers will be used
for merge phase might impact the performance. Having too many
workers can lead to more communication cost and having too few workers
might not yield best results for merge. One thing, I have noticed
that in general for sorting, some of the other databases uses range
partitioning [1], now that might not be what is good for us. I see
you mentioned above that why it is not good [2], but I don't
understand why you think it is a risky assumption to assume good
partition boundaries for parallelizing sort.

[1] -
https://docs.oracle.com/cd/E11882_01/server.112/e25523/parallel002.htm
Refer Producer or Consumer Operations section.

[2] -
"That approach would not suit CREATE INDEX, because the approach's
great strength is that the workers can run in parallel for the entire
duration, since there is no merge bottleneck (this assumes good
partition boundaries, which is of a bit risky assumption)"

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