Opened 3 years ago

Closed 3 years ago

#4933 closed enhancement (fixed)

Slow topology population due to cost of finding face containing point.

Reported by: strk Owned by: strk
Priority: medium Milestone: PostGIS 3.2.0
Component: topology Version:
Keywords: Cc:


In a real-world case where multiple faces's MBR contain a given point, a ding unconnected linestrings has the most expensive phase being finding the face containing both of its endpoints. The following query is run twice (once per endpoint):

WITH faces AS (
 SELECT face_id
 FROM "topo_ar5ngis_sysdata_webclient".face
 WHERE mbr && $1
 ORDER BY ST_Area(mbr) ASC
SELECT face_id FROM faces 
WHERE _ST_Contains(topology.ST_GetFaceGeometry('topo_ar5ngis_sysdata_webclient', face_id), $1) LIMIT 1

In the intention of the author (me) the CTE would have been executed first, and then the filter would have been applied to those faces in the order specified in the CTE, but with PostgreSQL 12 this is not happening, and instead the CTE is being inlined.

Chances are using WITH MATERIALIZED would fix this problem:

Another approach would do the loop internally rather than delegating the strategy to the PostgreSQL planner. Doing the loop internally could also avoid building the whole face geometry but only build the exterior ring of each face, as the smallest ring containing the point would be the exterior ring of the face effectively containing it.

Attachments (1)

bigFace.png (127.4 KB ) - added by strk 3 years ago.
Big face triggering the slow query

Download all attachments as: .zip

Change History (11)

by strk, 3 years ago

Attachment: bigFace.png added

Big face triggering the slow query

comment:2 by strk, 3 years ago

The excess time of that query is really mostly due to ST_GetFaceGeometry for the Face drawn in yellow in the following image.

Big face triggering the slow query

The rendered faces are the two faces having a MBR which contain the given point (rendered as a red dot).

Calling ST_GetFaceGeometry for that yellow face takes 1.8 seconds. That yellow face has 7100 interior rings!

Checking the actual containment in proper order won't help as the smaller MBR is the face NOT containing the red dot.

comment:3 by strk, 3 years ago

For comparison: ST_GetFaceGeometry for the green face takes 6ms, for the yellow face takes 1788ms (~1.8 seconds)

comment:4 by strk, 3 years ago

Going deeper, the ~1.8 seconds are in ST_BuildArea. Simply collecting the edges take 16ms, passing the collected edges to ST_BuildArea takes the remaining time.

comment:5 by strk, 3 years ago

Interestingly enough, ST_Polygonize takes 674 seconds (half the time). Still a long time but surely to be preferred, at this point…

comment:6 by strk, 3 years ago

Reimplementing getFaceContainingPoint by finding closest edge and analizing only the two rings formed from it can determine face containing point in under 3ms rather than 1.8 seconds, I think that's the way to go.

comment:7 by strk, 3 years ago

Unfortunately the current GetFaceByPoint function is *tested* to work against the broken topology built by topology.AddEdge and topology.AddFace, which is a combination of calls leaving the topology in a state with no correct edge linking. The new improved code relies instead on a valid topology in input.

Note that ValidateTopology currently does not even report this kind of invalidity (see #3042)

comment:8 by strk, 3 years ago

Experimental implementation of the new function is in

comment:9 by strk, 3 years ago

The new GetFaceContainingPoint is now added to the main branch, bringing down the time needed to find which face contains a point (in our case 3ms instead of 1.8 seconds). Closing the ticket accordingly.

comment:10 by strk, 3 years ago

Resolution: fixed
Status: newclosed
Note: See TracTickets for help on using tickets.