Opened 3 years ago

Closed 3 years ago

#5111 closed enhancement (fixed)

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

Reported by: strk Owned by: strk
Priority: medium Milestone: PostGIS 3.3.0
Component: topology Version: 3.2.x
Keywords: performance Cc:

Description

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.

Change History (8)

comment:1 by strk, 3 years ago

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

comment:2 by strk, 3 years ago

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

comment:3 by strk, 3 years ago

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

comment:4 by strk, 3 years ago

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

comment:5 by strk, 3 years ago

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

comment:6 by strk, 3 years ago

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)

comment:7 by strk, 3 years ago

Summary: Topology ChangeEdgeGeometry slow at updating face MBRTopology functions changing edge geometries (most topology editing functions) slow at updating face MBR

comment:8 by Sandro Santilli <strk@…>, 3 years ago

Resolution: fixed
Status: newclosed

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

Note: See TracTickets for help on using tickets.