Opened 13 months ago

Last modified 6 weeks ago

#867 new defect

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 6 weeks ago.
pg11_POSTGIS_2_5_3_GEOS_3_8_0dev (4.4 KB) - added by laopsahl 6 weeks ago.
Postgres 11, geos 3.5
pg95_POSTGIS_2_2_2_GEOS_3_5_0 (3.4 KB) - added by laopsahl 6 weeks ago.
Postgres 9.5 , geos 3.5

Download all attachments as: .zip

Change History (18)

comment:2 Changed 13 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 13 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 13 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 13 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 10 months ago by robe

Milestone: 3.6.33.6.4

comment:8 Changed 6 weeks 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 6 weeks ago by mdavis

Resolution: fixed
Status: closedreopened

Reopened until tested.

comment:10 Changed 6 weeks 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 6 weeks ago by mdavis

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

comment:12 Changed 6 weeks ago by mdavis

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

comment:13 Changed 6 weeks ago by mdavis

Milestone: 3.6.43.8.0

comment:14 Changed 6 weeks ago by mdavis

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

Changed 6 weeks ago by laopsahl

Changed 6 weeks ago by laopsahl

Postgres 11, geos 3.5

Changed 6 weeks ago by laopsahl

Postgres 9.5 , geos 3.5

comment:15 Changed 6 weeks 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));

Note: See TracTickets for help on using tickets.