Opened 19 months ago

Closed 2 months ago

Last modified 8 weeks ago

#867 closed defect (fixed)

Performance regression in union algorithm between GEOS 3.6.1 and GEOS 3.6.2

Reported by: robe Owned by: mdavis
Priority: blocker Milestone: 3.8.0
Component: Default Version: 3.6.2
Severity: Unassigned Keywords:
Cc:

Description

Reported on PostGIS mailing lists

https://lists.osgeo.org/pipermail/postgis-users/2018-April/042710.html

Example is exercised in PostGIS, but I concluded the issue is a change that happened between GEOS 3.6.1 and 3.6.2

I'll link to the related PostGIS ticket once it's put in.

Attachments (3)

pg11_POSTGIS_2_5_2_GEOS_3_7_1 (4.4 KB) - added by laopsahl 7 months ago.
pg11_POSTGIS_2_5_3_GEOS_3_8_0dev (4.4 KB) - added by laopsahl 7 months ago.
Postgres 11, geos 3.5
pg95_POSTGIS_2_2_2_GEOS_3_5_0 (3.4 KB) - added by laopsahl 7 months ago.
Postgres 9.5 , geos 3.5

Download all attachments as: .zip

Change History (28)

comment:2 Changed 19 months ago by bjornharrtell

Looking into this it seems a likely candidate for this regression is the work to fix a robustness issue as described by https://trac.osgeo.org/geos/ticket/837.

comment:3 Changed 19 months ago by robe

bjornharrtell,

Thanks for looking into this. I'm planning to test this out today so will know for sure if reverting this fixes the issue.

comment:4 Changed 19 months ago by robe

Confirmed this behemoth of a commit is the culprit.

Testing with: 3.6.2dev 459ae2f (which commit before the #837 one) takes 29.7 secs

Testing with the #837 commit (3.6.2dev-CAPI-1.10.2 3975725)

Takes 2:35 minutes.

I'll reopen that one.

comment:5 Changed 19 months ago by robe

Okay I nailed it down to this area and got it at least for this example to behavior like the old behavior. Thus probably wiping out your intent.

https://git.osgeo.org/gitea/geos/geos/pulls/28

comment:6 Changed 16 months ago by robe

Milestone: 3.6.33.6.4

comment:8 Changed 7 months ago by Martin Davis <mtnclimb@…>

Resolution: fixed
Status: newclosed

In 1b24aed/git:

Rework the logic to cope with unsafe unions by envelope
(for cases where union snapping alters the result envelope)
This fixes the performance regression in 3.6.2.

Fixes #867

comment:9 Changed 7 months ago by mdavis

Resolution: fixed
Status: closedreopened

Reopened until tested.

comment:10 Changed 7 months ago by mdavis

Further details on performance fix:

For the test data in the 2019-Apr-11 thread the GEOS performance goes from 150s to 111 s.

All unit tests pass, as does the #837 test case.

comment:11 Changed 7 months ago by mdavis

For the data in PostGIS ticket 4075 performance improves to 40 s from 205 s.

comment:12 Changed 7 months ago by mdavis

Owner: changed from geos-devel@… to mdavis
Status: reopenednew

comment:13 Changed 7 months ago by mdavis

Milestone: 3.6.43.8.0

comment:14 Changed 7 months ago by mdavis

Actually this isn't fixed correctly - still working on it.

Changed 7 months ago by laopsahl

Changed 7 months ago by laopsahl

Postgres 11, geos 3.5

Changed 7 months ago by laopsahl

Postgres 9.5 , geos 3.5

comment:15 Changed 7 months ago by laopsahl

This 3 sample files above show the out plans from the sql block below.

This show that ST_Union of polygon that does not intersects is almost 10 slower in geos 3.7.1 than in geos 3.5.0. The file geos_3_8_0dev is the master of geos from April 14.

SELECT PostGIS_full_version();

-- Use st_union on only intersecting polygins
EXPLAIN ANALYZE
select (ST_dump(st_union(geo))).geom as geo
from t1_intersects ;

-- Use st_union on only non intersecting polygins
EXPLAIN ANALYZE
select (ST_dump(st_union(geo))).geom as geo
from t1_not_intersects ;

-- Use st_union on all the data
EXPLAIN ANALYZE
select (ST_dump(st_Union(geo))).geom as geo
from ( select * from t1_intersects union select * from t1_not_intersects ) as r;

-- Test with st_collect
EXPLAIN ANALYZE
select (ST_dump(st_collect(geo))).geom as geo
from t1_not_intersects ;

The two input tables are based the file I sent this, but I have split the polygons in two sets. One that contain non intersection polygon and with intersection polygon made this way.

-- Split in two different tables one that has intersecst on that does not
create unlogged table t1_intersects as ( select distinct t1.gid, t1.geo
from sde_markslag.markslag_myrikilden_temp t1, sde_markslag.markslag_myrikilden_temp t2
where t2.gid != t1.gid and t1.gid  < 10000 and t2.gid  < 10000 and ST_intersects(t1.geo,t2.geo));

create unlogged table t1_not_intersects as ( select distinct t1.gid, t1.geo
from sde_markslag.markslag_myrikilden_temp t1
where t1.gid  < 10000 and not exists ( select 1 from t1_intersects t2_not where t1.gid = t2_not.gid and t2_not.gid < 10000));

comment:16 Changed 3 months ago by dbaston

Summary: Regression in union algorithm between GEOS 3.6.1 and GEOS 3.6.2Performance regression in union algorithm between GEOS 3.6.1 and GEOS 3.6.2

comment:17 Changed 2 months ago by pramsey

The JTS fix has found its way into GEOS master, in case you are able to test. I can pull it back to 3.7 probably, but it's full of c++11'isms so going further back would be hard.

Last edited 2 months ago by pramsey (previous) (diff)

comment:18 Changed 2 months ago by laopsahl

Thanks. I Tried to compile master, but got the error below using gcc (GCC) 4.8.5 20150623 (Red Hat 4.8.5-36)

In file included from /home/compile_source/geos/include/geos/geom/IntersectionMatrix.h:22:0,
                 from /home/compile_source/geos/include/geos/geom/Geometry.h:39,
                 from /home/compile_source/geos/src/algorithm/Centroid.cpp:22:
/home/compile_source/geos/include/geos/geom/Location.h:37:14: error: enumerator value -1 is too large for underlying type ‘char’
     UNDEF = -1, // Instead of NULL
              ^
make[2]: *** [CMakeFiles/geos.dir/src/algorithm/Centroid.cpp.o] Error 1
make[1]: *** [CMakeFiles/geos.dir/all] Error 2
make: *** [all] Error 2

To get and prepare code from https://git.osgeo.org/gitea/geos/geos.git I did mkdir build && cd build && cmake3 -DCMAKE_BUILD_TYPE=Release .. and make

I did compile geo 3.7.2 on this server a a couple a weeks ago.

comment:19 Changed 2 months ago by Paul Ramsey <pramsey@…>

In 6b6abc3/git:

Be explicit about our literals in enumerations
References #867

comment:20 Changed 2 months ago by laopsahl

Thanks it now compiled and it's about three times faster with latest master compared to geos 1.7.2. I also added an exanmple where I uses collect to show that that most of the time consumed in doing ST_Union

POSTGIS="2.5.3 r17699" [EXTENSION] PGSQL="110" GEOS="3.7.2-CAPI-1.11.2 b55d2125" SFCGAL="1.3.7" PROJ="Rel. 6.2.0, September 1st, 2019" GDAL="GDAL 3.1.0dev-7a9a0f4-dirty, released 2019/99/99" LIBXML="2.9.1" TOPOLOGY RASTER
(1 row)


EXPLAIN ANALYZE
select atil, myr, myrtype,myromdanning,myrtypetext,myromdanningtext
, st_union(geo) as geo
from sde_markslag.markslag_myrikilden_temp
group by atil, myr, myrtype,myromdanning,myrtypetext,myromdanningtext;
                                                                QUERY PLAN                                                                 
-------------------------------------------------------------------------------------------------------------------------------------------
 HashAggregate  (cost=69097.63..69100.03 rows=192 width=46) (actual time=2187.621..5473961.397 rows=166 loops=1)
   Group Key: atil, myr, myrtype, myromdanning, myrtypetext, myromdanningtext
   ->  Seq Scan on markslag_myrikilden_temp  (cost=0.00..59170.91 rows=567241 width=1616) (actual time=0.014..592.120 rows=567241 loops=1)
 Planning Time: 0.186 ms
 Execution Time: 5473964.802 ms
(5 rows)

Time: 5473965.677 ms (01:31:13.966)


POSTGIS="2.5.3 r17699" [EXTENSION] PGSQL="110" GEOS="3.8.0dev-CAPI-1.12.0 " SFCGAL="1.3.7" PROJ="Rel. 6.2.0, September 1st, 2019" GDAL="GDAL 3.1.0dev-7a9a0f4-dirty, released 2019/99/99" LIBXML="2.9.1" TOPOLOGY RASTER

EXPLAIN ANALYZE
select atil, myr, myrtype,myromdanning,myrtypetext,myromdanningtext
, st_union(geo) as geo
from sde_markslag.markslag_myrikilden_temp
group by atil, myr, myrtype,myromdanning,myrtypetext,myromdanningtext;

                                                                 QUERY PLAN                                                                 
--------------------------------------------------------------------------------------------------------------------------------------------
 HashAggregate  (cost=69097.63..69100.03 rows=192 width=46) (actual time=3153.548..1936037.866 rows=166 loops=1)
   Group Key: atil, myr, myrtype, myromdanning, myrtypetext, myromdanningtext
   ->  Seq Scan on markslag_myrikilden_temp  (cost=0.00..59170.91 rows=567241 width=1616) (actual time=0.045..1377.130 rows=567241 loops=1)
 Planning Time: 2.532 ms
 Execution Time: 1936098.442 ms
(5 rows)

Time: 1936105.931 ms (32:16.106)


 EXPLAIN ANALYZE
select atil, myr, myrtype,myromdanning,myrtypetext,myromdanningtext
, st_collect(geo) as geo
from sde_markslag.markslag_myrikilden_temp
group by atil, myr, myrtype,myromdanning,myrtypetext,myromdanningtext;
                                                                QUERY PLAN                                                                 
-------------------------------------------------------------------------------------------------------------------------------------------
 HashAggregate  (cost=69097.63..69100.03 rows=192 width=46) (actual time=2090.348..3182.008 rows=166 loops=1)
   Group Key: atil, myr, myrtype, myromdanning, myrtypetext, myromdanningtext
   ->  Seq Scan on markslag_myrikilden_temp  (cost=0.00..59170.91 rows=567241 width=1616) (actual time=0.009..564.829 rows=567241 loops=1)
 Planning Time: 0.157 ms
 Execution Time: 3186.342 ms
(5 rows)

comment:21 Changed 2 months ago by laopsahl

I did one more where I modified I aded ST_Union after the ST_collect.

Why is this so much faster ? Should not the ST_union run after all the rows are grouped in the first and second sql ?

EXPLAIN ANALYZE
select atil, myr, myrtype,myromdanning,myrtypetext,myromdanningtext, ST_Union(geo) as geo from (
select atil, myr, myrtype,myromdanning,myrtypetext,myromdanningtext
, st_collect(geo) as geo
from sde_markslag.markslag_myrikilden_temp
group by atil, myr, myrtype,myromdanning,myrtypetext,myromdanningtext
) as r
group by atil, myr, myrtype,myromdanning,myrtypetext,myromdanningtext;
                                                                                                                   QUERY PLAN                                                                        
                                           
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
-------------------------------------------
 GroupAggregate  (cost=69109.23..69115.47 rows=192 width=46) (actual time=5145.001..6581.752 rows=166 loops=1)
   Group Key: markslag_myrikilden_temp.atil, markslag_myrikilden_temp.myr, markslag_myrikilden_temp.myrtype, markslag_myrikilden_temp.myromdanning, markslag_myrikilden_temp.myrtypetext, markslag_my
rikilden_temp.myromdanningtext
   ->  Sort  (cost=69109.23..69109.71 rows=192 width=46) (actual time=5061.330..5506.245 rows=166 loops=1)
         Sort Key: markslag_myrikilden_temp.atil, markslag_myrikilden_temp.myr, markslag_myrikilden_temp.myrtype, markslag_myrikilden_temp.myromdanning, markslag_myrikilden_temp.myrtypetext, marksl
ag_myrikilden_temp.myromdanningtext
         Sort Method: external merge  Disk: 874352kB
         ->  HashAggregate  (cost=69097.63..69100.03 rows=192 width=46) (actual time=2311.471..3552.471 rows=166 loops=1)
               Group Key: markslag_myrikilden_temp.atil, markslag_myrikilden_temp.myr, markslag_myrikilden_temp.myrtype, markslag_myrikilden_temp.myromdanning, markslag_myrikilden_temp.myrtypetext,
 markslag_myrikilden_temp.myromdanningtext
               ->  Seq Scan on markslag_myrikilden_temp  (cost=0.00..59170.91 rows=567241 width=1616) (actual time=0.010..565.744 rows=567241 loops=1)
 Planning Time: 0.186 ms
 Execution Time: 6691.195 ms
(10 rows)

Time: 6707.726 ms (00:06.708)

comment:22 Changed 2 months ago by pramsey

Resolution: fixed
Status: newclosed

If you example the output from your second example, you'll probably find that the ST_Union(geo) call was a no-op, as it was handed a single input. You could replace ST_Union() with ST_UnaryUnion() and you should see the timings go back to what you expect. Basically, you call an aggregate with a single value and the aggregate goes "one entry? no processing to do, here you can have it back".

Given the great results I'm declaring victory and closing this one out.

comment:23 Changed 8 weeks ago by laopsahl

Thanks.

I did a test with ST_UnaryUnion and it's correct what you suggested.

select count(*) num_rows, Sum(ST_Area(geo)) sum_area, Sum(ST_NumGeometries(geo)) num_geos from (
select atil, myr, myrtype,myromdanning,myrtypetext,myromdanningtext, ST_Union(geo) as geo from (
select atil, myr, myrtype,myromdanning,myrtypetext,myromdanningtext
, ST_Multi(st_collect(geo)) as geo
from sde_markslag.markslag_myrikilden_temp
group by atil, myr, myrtype,myromdanning,myrtypetext,myromdanningtext
) as r
group by atil, myr, myrtype,myromdanning,myrtypetext,myromdanningtext
) as r;

 num_rows |     sum_area     | num_geos 
----------+------------------+----------
      166 | 1.35406160257966 |   567241
(1 row)

Time: 7600.350 ms (00:07.600)

select count(*) num_rows, Sum(ST_Area(geo)) sum_area, Sum(ST_NumGeometries(geo)) num_geos from (
select atil, myr, myrtype,myromdanning,myrtypetext,myromdanningtext, ST_UNaryUnion(geo) as geo from (
select atil, myr, myrtype,myromdanning,myrtypetext,myromdanningtext
, ST_Multi(st_collect(geo)) as geo
from sde_markslag.markslag_myrikilden_temp
group by atil, myr, myrtype,myromdanning,myrtypetext,myromdanningtext
) as r
group by atil, myr, myrtype,myromdanning,myrtypetext,myromdanningtext, geo
) as r;


 num_rows |     sum_area     | num_geos 
----------+------------------+----------
      166 | 1.35405434825635 |   482885
(1 row)

Time: 1914499.702 ms (31:54.500)

comment:24 Changed 8 weeks ago by laopsahl

Sorry for this, I did more testing more on an old Postgres Server. This server is about 4-5 years old and has Intel(R) Xeon(R) CPU E5-2667 v2 @ 3.30GHz and not a ARM proc, but I don't think the old server is so much faster than the new one, which I used in the tests above.

POSTGIS="2.2.2 r14797" GEOS="3.5.0-CAPI-1.9.0 r4084" PROJ="Rel. 4.8.0, 6 March 2012" GDAL="GDAL 1.9.2, released 2012/10/08" LIBXML="2.7.6" LIBJSON="0.11" TOPOLOGY RASTER

PostgreSQL 9.5.2 on x86_64-pc-linux-gnu, compiled by gcc (GCC) 4.4.7 20120313 (Red Hat 4.4.7-16), 64-bit

and the old code seems to be around 5 times faster than the new code using ST_UnaryUnion/ST_collect or plain ST_Union

select count(*) num_rows, Sum(ST_Area(geo)) sum_area, Sum(ST_NumGeometries(geo)) num_geos from (
select atil, myr, myrtype,myromdanning,myrtypetext,myromdanningtext, ST_UNaryUnion(geo) as geo from (
select atil, myr, myrtype,myromdanning,myrtypetext,myromdanningtext
, ST_Multi(st_collect(geo)) as geo
from sde_markslag.markslag_myrikilden_temp
group by atil, myr, myrtype,myromdanning,myrtypetext,myromdanningtext
) as r
group by atil, myr, myrtype,myromdanning,myrtypetext,myromdanningtext, geo
) as r;

 num_rows |     sum_area     | num_geos 
----------+------------------+----------
      166 | 1.35405434825635 |   482885
(1 row)

Time: 379259.682 ms (06:19.260)

Do you want any query plans from Postgres 9.5 tests ?

I can upload this dataset to a server that you point, if you need it ?

I will do some more testing and get back to you.

comment:25 Changed 8 weeks ago by laopsahl

I did a new test on a server which is pretty much the same as the server running Postgres 9.5 , but here we here run 'POSTGIS="2.5.0beta2 r16690" [EXTENSION] PGSQL="100" GEOS="3.6.2-CAPI-1.10.2 ' from this numbers I am pretty sure that the ST_Union function was faster in Postgres 9.5.

Later this fall we plan to upgrade the server with Postgres 9.5 to Postgres 11 and latest geos and then I will rerun this test and report the numbers.

Note: See TracTickets for help on using tickets.