ValidateTopology, failes with ERROR: XX000: GetRingEdges: edge id cannot be null

[Lars Aksel Opsahl]

We are running on

POSTGIS="3.4.0 0874ea3" [EXTENSION] PGSQL="120" GEOS="3.10.1-CAPI-1.16.0" SFCGAL="1.3.7" PROJ="8.2.0 NETWORK_ENABLED=OFF URL_ENDPOINT=https://cdn.proj.org USER_WRITABLE_DIRECTORY=/tmp/proj DATABASE_PATH=/usr/share/proj/proj.db" LIBXML="2.9.10" LIBJSON="0.13.1" LIBPROTOBUF="1.3.3" WAGYU="0.5.0 (Internal)" TOPOLOGY

PostgreSQL 12.6 (Ubuntu 12.6-0ubuntu0.20.04.1) on x86_64-pc-linux-gnu, compiled by gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0, 64-bit

This is the failing call

SELECT * FROM topology.ValidateTopology(   
'tmp_resultat_1804_t4',
'0103000020A210000001000000050000001886F01924952D40A49DCA0D0ECC50401886F01924952D4046B267EF9CCD5040E6511F5B5BBF2D4046B267EF9CCD5040E6511F5B5BBF2D40A49DCA0D0ECC50401886F01924952D40A49DCA0D0ECC5040'
);    

Here is the output with DEBUG

NOTICE:  00000: Limiting topology checking to bbox SRID=4258;POLYGON((14.79129105626184 67.18835778032968,14.79129105626184 67.21270356299019,14.873743865559799 67.21270356299019,14.873743865559799 67.18835778032968,14.79129105626184 67.18835778032968))
LOCATION:  exec_stmt_raise, pl_exec.c:3862
NOTICE:  00000: Checking for coincident nodes
LOCATION:  exec_stmt_raise, pl_exec.c:3862
NOTICE:  00000: Checking for edges crossing nodes
LOCATION:  exec_stmt_raise, pl_exec.c:3862
NOTICE:  00000: Checking for invalid or not-simple edges
LOCATION:  exec_stmt_raise, pl_exec.c:3862
NOTICE:  00000: Checking for crossing edges
LOCATION:  exec_stmt_raise, pl_exec.c:3862
NOTICE:  00000: Checking for edges start_node mismatch
LOCATION:  exec_stmt_raise, pl_exec.c:3862
NOTICE:  00000: Checking for edges end_node mismatch
LOCATION:  exec_stmt_raise, pl_exec.c:3862
NOTICE:  00000: Checking for faces without edges
LOCATION:  exec_stmt_raise, pl_exec.c:3862
NOTICE:  00000: Checking edge linking
LOCATION:  exec_stmt_raise, pl_exec.c:3862
DEBUG:  00000: building index "pg_toast_1750651423_index" on table "pg_toast_1750651423" serially
LOCATION:  index_build, index.c:2870
DEBUG:  00000: CREATE TABLE / PRIMARY KEY will create implicit index "shell_check_pkey" for table "shell_check"
LOCATION:  DefineIndex, indexcmds.c:1006
DEBUG:  00000: building index "shell_check_pkey" on table "shell_check" serially
LOCATION:  index_build, index.c:2870
DEBUG:  00000: building index "pg_toast_1750651431_index" on table "pg_toast_1750651431" serially
LOCATION:  index_build, index.c:2870
NOTICE:  00000: Building edge rings
LOCATION:  exec_stmt_raise, pl_exec.c:3862
NOTICE:  00000: Found 476 rings, 445 valid shells, 31 valid holes
LOCATION:  exec_stmt_raise, pl_exec.c:3862
NOTICE:  00000: Constructing geometry of all faces
LOCATION:  exec_stmt_raise, pl_exec.c:3862
DEBUG:  00000: building index "pg_toast_1750651451_index" on table "pg_toast_1750651451" serially
LOCATION:  index_build, index.c:2870
DEBUG:  00000: drop auto-cascades to type shell_check
LOCATION:  reportDependentObjects, dependency.c:1127
DEBUG:  00000: drop auto-cascades to type shell_check[]
LOCATION:  reportDependentObjects, dependency.c:1127
DEBUG:  00000: drop auto-cascades to toast table pg_toast_temp_6.pg_toast_1750651423
LOCATION:  reportDependentObjects, dependency.c:1127
DEBUG:  00000: drop auto-cascades to type pg_toast_temp_6.pg_toast_1750651423
LOCATION:  reportDependentObjects, dependency.c:1127
DEBUG:  00000: drop auto-cascades to index pg_toast_temp_6.pg_toast_1750651423_index
LOCATION:  reportDependentObjects, dependency.c:1127
          THEN
            edge_id
          ELSE
            -edge_id
          END ring_id
        FROM tmp_resultat_1804_t4.edge
        WHERE left_face = $1 or right_face = $1
        ORDER BY
          geom <-> $2
        LIMIT 1
      ),
      edgering AS (
        SELECT *
        FROM
          topology.GetRingEdges(
            'tmp_resultat_1804_t4',
            (SELECT ring_id FROM leftmost_edge)
          )
      )
      SELECT
        ST_MakeLine(
          CASE WHEN r.edge > 0 THEN
            e.geom
          ELSE
            ST_Reverse(e.geom)
          END
          ORDER BY r.sequence
        ) outerRing
      FROM edgering r, tmp_resultat_1804_t4.edge e
      WHERE e.edge_id = abs(r.edge)
    "
PL/pgSQL function _validatetopologygetfaceshellmaximaledgering(character varying,integer) line 74 at EXECUTE
SQL statement "INSERT INTO pg_temp.face_check
    SELECT face_id,
      topology._ValidateTopologyGetFaceShellMaximalEdgeRing(toponame, face_id),
      mbr
    FROM face
    WHERE mbr && bbox
    AND (
      CASE WHEN invalid_faces IS NOT NULL THEN
        NOT face_id = ANY(invalid_faces)
      ELSE
        TRUE
      END
    )
    AND face_id NOT IN (
      SELECT face_id FROM pg_temp.face_check
    )"
PL/pgSQL function validatetopology(character varying,geometry) line 336 at SQL statement
LOCATION:  pg_error, lwgeom_pg.c:332

[Lars Aksel Opsahl]

Here is out with debug5

[strk]

As usual, we need a dataset to be able to reproduce this. A topology dump, in this case.

[strk]

I got access to the database exposing the problem. The offending query is from the step in which shells of all faces are constructed

NOTICE: Constructing geometry of all faces

In particular, this is the dynamic SQL being executed:

      WITH
      outside_point AS (
        SELECT ST_Translate(
          ST_StartPoint( ST_BoundingDiagonal(mbr) ),
          -1,
          -1
        )
        FROM topo.face
        WHERE face_id = $1
      ),
      leftmost_edge AS (
        SELECT
          CASE WHEN left_face = $1
          THEN
            edge_id
          ELSE
            -edge_id
          END ring_id
        FROM topo.edge
        WHERE left_face = $1 or right_face = $1
        ORDER BY
          geom <-> $2
        LIMIT 1
      ),
      edgering AS (
        SELECT *
        FROM
          GetRingEdges(
            'topo',
            (SELECT ring_id FROM leftmost_edge)
          )
      )
      SELECT
        ST_MakeLine(
          CASE WHEN r.edge > 0 THEN
            e.geom
          ELSE
            ST_Reverse(e.geom)
          END
          ORDER BY r.sequence
        ) outerRing
      FROM edgering r, topo.edge e
      WHERE e.edge_id = abs(r.edge)

The GetRingEdges function evidently receives a NULL, so SELECT ring_id FROM leftmost_edge returns NULL. The leftmost_edge CTE is:

        SELECT
          CASE WHEN left_face = $1
          THEN
            edge_id
          ELSE
            -edge_id
          END ring_id
        FROM topo.edge
        WHERE left_face = $1 or right_face = $1
        ORDER BY
          geom <-> $2
        LIMIT 1

Getting a NULL from that query suggests that the face with id=$1 has no edges. I'm digging further.

[strk]

I confirm the offending database has 9 faces with no edges:

postgis-ticket-5548=# select face_id from topo.face except ( select left_face from topo.edge union select right_face from topo.edge );
 face_id 
---------
  101455
   91383
  169721
  168377
  105440
  163138
  173666
  104389
   38457
(9 rows)

[strk]

It's to be noted that this bug is only present when a bounding box is provided. Regress test showing the problem now available in ​https://gitlab.com/postgis/postgis/-/merge_requests/95, fix is coming next.

[Sandro Santilli <strk@…>]

In 9288c54/git:

Fix box-filtered validity check of topologies with edge-less faces

Includes regress test.
References #5548 in master branch (3.5.0dev)

[strk]

The bbox parameter was added in PostGIS-3.2, 3.2.6 is also affected

[Sandro Santilli <strk@…>]

In 05ea0b35/git:

Fix box-filtered validity check of topologies with edge-less faces

Includes regress test.
References #5548 in stable-3.4 branch (3.4.1dev)

[Sandro Santilli <strk@…>]

In 343e2d4/git:

Fix box-filtered validity check of topologies with edge-less faces

Includes regress test.
References #5548 in stable-3.3 branch (3.3.5dev)

[Sandro Santilli <strk@…>]

In 6e4b1c4/git:

Fix box-filtered validity check of topologies with edge-less faces

Includes regress test.
Closes #5548 in stable-3.2 branch (3.2.6dev)

[strk]

I'm reopening because the issue is still not fixed on the reporter database. I must have missed another condition in the test I added.

[strk]

Taking it back, the fix is actually effective. I just conducted the wrong upgrade. With the fix I can confirm the problem was faces without edges:

       error        |  id1   | id2 
--------------------+--------+-----
 face without edges |  91383 |    
 face without edges | 101455 |    
 face without edges | 105440 |    
(3 rows)