[postgis-devel] More Cascade Union Adventures

[Obe, Regina]

Martin,

PostGIS just may beat JTS by cheating a little.  I think I have managed to up one on Kevin's solution by cheating.  One of the PostgreSQL developers pointed out to me that array_append is highly inefficient and testing out the st_geom_accum - that suffers from similar issues.  Watch these tests.  I tested on OpenJump too and got 55 second response.  Of course that was not a fair test since my workstation does not have PostgreSQL on it.  I'll have to wait till later when I'm at a box that has both PostgreSQL and OpenJump installed to do a fair comparison.

I also remarked out the sorting I was doing because it didn't seem to be consistently better in all cases.
---THE TESTS ---
--   231,312 ms = 3.85 mins - SELECT 231312/1000.00/60
SELECT ST_CascadeUnion(the_geom)
FROM (SELECT * FROM sample_poly) As foo;

--44,453 ms = 45 secs = wow! SELECT 44453/1000.00
SELECT st_unitecascade_garray_sort(ARRAY(SELECT the_geom FROM sample_poly));

-- 77,078 ms, 75124 ms = 1.26 min
SELECT ST_NumGeometries(ST_Union(the_geom)) AS the_geom
FROM (
   SELECT min(id) AS id, ST_Union(the_geom) AS the_geom
   FROM (
     SELECT min(id) AS id, ST_Union(the_geom) AS the_geom
     FROM (
       SELECT min(id) AS id, ST_Union(the_geom) AS the_geom
       FROM (
         SELECT min(id) AS id, ST_Union(the_geom) AS the_geom
         FROM (SELECT * FROM sample_poly) As foo
         GROUP BY round(id/10)
         ORDER BY id) AS tmp1
       GROUP BY round(id/100)
       ORDER BY id) AS tmp2
     GROUP BY round(id/1000)
     ORDER BY id) AS tmp3
   GROUP BY round(id/10000)
   ORDER BY id) AS tmp4
GROUP BY round(id/100000);


-----THE CODE ---

CREATE OR REPLACE FUNCTION st_unitecascade_garray(geometry[], iter int,
startcount int)
  RETURNS geometry AS
$$
SELECT CASE WHEN array_upper($1,1) < 5 OR  array_upper($1,1) BETWEEN 0
AND ln($3 + 1)/ln($2 + 1) THEN st_unite_garray($1) ELSE
	st_unitecascade_garray(ARRAY(SELECT st_unite_garray($1[i:least(i
+ CAST(ln($3 + 1)/ln($2 + 1) As int) - 1,array_upper($1,1))]) As geom
FROM generate_series(1, array_upper($1,1), CAST(ln($3 + 1)/ln($2 + 1) As
int)) As i), $2 + 1, $3) END

$$
  LANGUAGE 'sql' IMMUTABLE;

CREATE OR REPLACE FUNCTION st_unitecascade_garray_sort(geometry[])
  RETURNS geometry AS
$$
	SELECT CASE WHEN array_upper($1,1) < 10  THEN
st_unite_garray($1) ELSE
		st_unitecascade_garray(ARRAY(SELECT ($1)[s] FROM
generate_series(1, array_upper($1, 1)) AS s 
			--ORDER BY ST_SnapToGrid(ST_Centroid(($1)[s]),0.1)
) , 2, array_upper($1,1)) END;
$$
  LANGUAGE 'sql' IMMUTABLE;

--DROP AGGREGATE st_cascadeunion(geometry);

CREATE AGGREGATE st_cascadeunion(geometry) (
  SFUNC=st_geom_accum,
  STYPE=geometry[],
  FINALFUNC=st_unitecascade_garray_sort
);




--BEGIN TESTS --
CREATE INDEX idx_sample_poly_the_geom
  ON sample_poly
  USING gist
  (the_geom);

  
ALTER TABLE sample_poly CLUSTER ON idx_sample_poly_the_geom;
CLUSTER sample_poly;


vacuum analyze sample_poly;


Thanks,
Regina












-----------------------------------------
The substance of this message, including any attachments, may be
confidential, legally privileged and/or exempt from disclosure
pursuant to Massachusetts law. It is intended
solely for the addressee. If you received this in error, please
contact the sender and delete the material from any computer.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/postgis-devel/attachments/20080813/6dbcdfe7/attachment.html>