Re: CLUSTER, reform_and_rewrite_tuple(), and parallelism

On Wed, Aug 17, 2016 at 4:12 PM, Peter Geoghegan <pg@heroku.com> wrote:
> During preliminary analysis of what it would take to produce a
> parallel CLUSTER patch that is analogous of what I came up with for
> CREATE INDEX, which in general seems quite possible, I identified
> reform_and_rewrite_tuple() as a major bottleneck for the current
> CLUSTER implementation.

I now think my original analysis here was more or less wrong.

With today's git tip, which has numerous optimizations to merging in
particular [1], CLUSTER seems like an unappealing target for
parallelism. As noted recently [1], it seems like there has been a
significant decrease in the time spent merging by serial external
CREATE INDEX operations; as a proportion of total time, it's now often
as low as 15%. Things are generally moderately CPU bound. The
situation with CLUSTER is quite different; CLUSTER can spend up to 50%
of the time or more merging, because it's distinctly I/O bound,
presumably due to typically processing relatively wide tuples, with a
tuple header, etc. Furthermore, even if it is possible to push some of
the cycles into worker processes, that seems hard.

I think that Heikki's preload tuplesort work will help serial CLUSTER
cases quite a bit, by allowing tuplesort to buffer more tuples in
memory, but the overall picture is the same, which is that merging for
CLUSTER is very I/O bound (this is when we write out the new version
of the heap relation, of course). I'm not excited about the prospect
of using parallelism to speed up scanning and sorting to generate
input runs in the style of my parallel CREATE INDEX patch, because
Amdahl's law is going to bite hard when only 50% of the work can be
parallelized [2]. Besides, parallel CREATE INDEX alone will probably
be quite effective at speeding up CLUSTER in practice, simply because
that's often where most wall clock time is spent during a CLUSTER
operation.

The only thing that generalizing my parallel CREATE INDEX approach to
CLUSTER really has to recommend it is that it isn't that hard to get
working, and will still help somewhat. But, once you factor in the
need for us to alter the CLUSTER cost model (we'll need to make
significant updates to plan_cluster_use_sort()), then even that isn't
true. I don't think I'm going to work on parallel CLUSTER after all.

[1] https://www.postgresql.org/message-id/CAM3SWZSsvig8eZtxCG1L9bZZw+-uWdJ48yxSM41QmNLtJeQSyA@mail.gmail.com
[2] https://en.wikipedia.org/wiki/File:AmdahlsLaw.svg
-- 
Peter Geoghegan