Re: parallelism and sorting

On Tue, Nov 24, 2015 at 7:53 PM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
>
> On Tue, Nov 24, 2015 at 7:59 AM, Amit Kapila <amit(dot)kapila16(at)gmail(dot)com>
wrote:
> > On Tue, Nov 24, 2015 at 8:59 AM, Robert Haas <robertmhaas(at)gmail(dot)com>
wrote:
> >> One idea about parallel sort is that perhaps if multiple workers feed
> >> data into the sort, they can each just sort what they have and then
> >> merge the results.
> >
> > Sounds like a good approach for parallel sorting, however small
extension
> > to it that could avoid merging the final results is that workers
allocated
> > for sort will perform range-based sorting. A simple example to sort
integers
> > from 1-100 will be, worker-1 will be responsible for sorting any integer
> > between 1-50 and worker-2 will be responsible for sorting integers from
> > 51-100 and then master backend just needs to ensure that it first
returns
> > the tuples from worker-1 and then from worker-2. I think it has some
> > similarity to your idea-5 (use of repartition), but not exactly same.
>
> This is not so easy to accomplish for a couple of reasons. First, how
> would you know where to partition the range?

I was thinking to form range map by referring histogram from stats.

>
> That would work fine if
> you had all the data in sorted order to begin with, but of course if
> you had that you wouldn't be sorting it. Second, remember that the
> data is probably arriving in separate streams in each worker - e.g.
> the sort may be being fed by a parallel sequential scan.

True, at this moment I am not sure what is the best way to reduce that
overhead, but may be some form of min tuple can be used for the same.

>
> If you do
> what I'm proposing, those workers don't need to communicate with each
> other except for the final merge at the end; but to do what you're
> proposing, you'd need to move each tuple from the worker that got it
> originally to the correct worker. I would guess that would be at
> least as expensive as the final merge pass you are hoping to avoid,
> and maybe significantly moreso.
>

I think we can evaluate pros and cons of each approach and then proceed
with one which is more promising.

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