[postgis-devel] ST_Union Parallel Experiment

[Paul Ramsey]

Hey all,
I just wanted to record for posterity the results of my experiment in
making a parallel version of ST_Union().

The basic theory was:

* add serialfn/deserialfn/combinefn to the aggregate
* in the serialfn, do an initial cascaded union of everything
collected by the worker
* in the combinefn, do pairwise union of each set of partials

The obvious drawback is, particularly for inputs that are a "coverage"
(many polygons, covering an area, with no overlap) the workers won't
be fed a neat contiguous area, so the main promise of cascaded union,
that it eliminates the maximum number of vertices possible at each
step, is broken.

In fact, that is more-or-less what I observed. The union was quite a
bit slower, even when it was using up twice as much CPU (two core
laptop)

(The debug messages are the parallel-only functions
(serialfn/deserialfn/combinefn) being called in the parallel
execution.)

postgis25=# select st_area(st_union(geom)) from va_ply_17;
DEBUG:  pgis_geometry_union_serialfn called
DEBUG:  pgis_geometry_union_serialfn called
DEBUG:  pgis_geometry_union_serialfn called
DEBUG:  pgis_geometry_union_deserialfn called
DEBUG:  pgis_geometry_union_deserialfn wkb size = 8526407
DEBUG:  pgis_accum_combinefn called
DEBUG:  pgis_geometry_union_deserialfn called
DEBUG:  pgis_geometry_union_deserialfn wkb size = 4236637
DEBUG:  pgis_accum_combinefn called
DEBUG:  pgis_geometry_union_deserialfn called
DEBUG:  pgis_geometry_union_deserialfn wkb size = 6526511
DEBUG:  pgis_accum_combinefn called
     st_area
-----------------
 1070123068374.1
(1 row)

Time: 106545.200 ms (01:46.545)

Force the plan to be single-threaded, and run again.

postgis25=# set max_parallel_workers_per_gather = 0;
postgis25=# select st_area(st_union(geom)) from va_ply_17;
     st_area
------------------
 1070123068374.11
(1 row)

Time: 66527.914 ms (01:06.528)

Damn, it's faster.

It’s possible that if the partials were fed inputs in a spatially
correlated order the final merge might be no worse than the usual
top-level merge in a cascaded union. However, forcing an ordering in
the aggregate strips out the parallel plans.

postgis25=# set max_parallel_workers_per_gather = 2;
postgis25=# explain select st_area(st_union(geom order by geom)) from va_ply_17;
                               QUERY PLAN
------------------------------------------------------------------------
 Aggregate  (cost=15860.58..15860.62 rows=1 width=8)
   ->  Seq Scan on va_ply_17  (cost=0.00..1715.58 rows=5658 width=6181)

If the order by trick worked, I'd hope that the parallel execution
might win, but since it doesn't it's best to just leave it "as is".

The branch is available here for anyone interested in perusing it.

https://github.com/pramsey/postgis/tree/svn-trunk-parallel-union

ATB,

P