Topology functions changing edge geometries (most topology editing functions) slow at updating face MBR

[strk]

When ST_ChangeEdgeGeometry is invoked, eitehr directly or due to snapping upon adding a node, the minimum bounding rectangle for the faced bound by the changed edge are being updated by computing the full geometry of the face, which is a slow operation. An opportunity exists to speed up this operation by only fetching exterior edges, so big faces with many holes won't slow down editing operations.

[strk]

It takes 2 seconds to build a polygon from a set of 9295 edges. Total vertices in the polygon: 359909

00.032867 psql:run.sql:13: DEBUG:  [../../topology/postgis_topology.c:cb_getEdgeByFace:1092] cb_getEdgeByFace: edge query returned 9295 rows
00.037544 psql:run.sql:13: DEBUG:  [../../liblwgeom/lwgeom_topo.c:lwt_GetFaceGeometry:2834] lwt_GetFaceGeometry: lwt_be_getEdgeByFace returned 9295 edges
01.959255 psql:run.sql:13: DEBUG:  [../../liblwgeom/lwgeom_topo.c:lwt_ChangeEdgeGeom:3499] lwt_ChangeEdgeGeom: lwt_GetFaceGeometry returned a polygon with 359909 vertices

[strk]

GEOSBuildArea is responsible for the slow operation, more so with GEOS main branch (while it's better with GEOS-3.9): ​https://github.com/libgeos/geos/issues/583

[strk]

The GEOS issue was a red herring, this ticket is still valid as we can avoid building the whole face geometry when all we need is the MBR of the exterior ring. See also ​https://gitlab.com/postgis/postgis/-/merge_requests/30

[strk]

The code responsible for this computation already contains a TODO comment for optimization:

  /*
  -- Update faces MBR of left and right faces
  -- TODO: think about ways to optimize this part, like see if
  --       the old edge geometry participated in the definition
  --       of the current MBR (for shrinking) or the new edge MBR
  --       would be larger than the old face MBR...
  --
  */

It's currently in liblwgeom/lwgeom_topo.c in function lwt_ChangeEdgeGeom

[strk]

Proof of concept implementation of an improved MBR computer: ​https://gitlab.com/postgis/postgis/-/merge_requests/72

[strk]

The change in ​https://gitlab.com/postgis/postgis/-/merge_requests/72 makes my testcase (which calls TopoGeo_addLineString) complete in under 0.4 seconds whereas before the change it takes over 1.6 seconds to complete:

With patch:

00.046139  topogeo_addlinestring
00.046143 -----------------------
00.046147                 978858
00.046151                 978860
00.046155                 978861
00.046158 (3 rows)
00.046161
00.046164 Time: 34.366 ms

Without patch:

01.639564  topogeo_addlinestring 
01.639567 -----------------------
01.639570                 978863
01.639572                 978865
01.639575                 978866
01.639578 (3 rows)
01.639580 
01.639583 Time: 1613.833 ms (00:01.614)

[Sandro Santilli <strk@…>]

In c273f394/git:

Speed up face MBR computation during topology editing

Closes #5111

Update test for #4706 as we won't throw an exception now,
from ST_ChangeEdgeGeom, on invalid topology