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

[strk]

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: ​https://www.postgresql.org/docs/current/sql-select.html#SQL-WITH

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.

[strk]

Real world case is discussed here: ​https://gitlab.com/nibioopensource/pgtopo_update_sql/-/issues/147#note_612817496

[strk]

Big face triggering the slow query

[strk]

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

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.

[strk]

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

[strk]

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.

[strk]

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

[strk]

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.

[strk]

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)

[strk]

Experimental implementation of the new function is in ​https://gitlab.com/postgis/postgis/-/merge_requests/28

[strk]

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.