Postgres: `DeleteRelationships` with limit using inefficient query

While trying to bulk delete relationships in preparation for a schema migration, we ran into an issue where batches of 1000 were taking significant amounts of time to delete. My colleague noted that the query could probably make use of ctid to improve performance and after digging into it with Claude that does seem to be the case.

While the below is Claude's summary, I have validated its assertions manually to the best of my ability and it doesn't seem to have hallucinated anything

Problem

deleteRelationshipsWithLimit in internal/datastore/postgres/readwrite.go (v1.56.1) soft-deletes in two steps: a CTE selects up to limit rows by their seven key columns, then the UPDATE re-finds each row by that key.

WITH found_tuples AS (SELECT namespace, object_id, relation, userset_namespace, userset_object_id, userset_relation, created_xid
                      FROM relation_tuple WHERE <filter> AND deleted_xid = <live> LIMIT 1000)
UPDATE relation_tuple SET deleted_xid = $1
WHERE (namespace, object_id, relation, userset_namespace, userset_object_id, userset_relation, created_xid) IN (SELECT * FROM found_tuples)

The select half uses the alive covering index and is fast. For the re-find, Postgres picks ix_relation_tuple_by_subject, matches on the five subject-leading columns, and applies object_id and created_xid as a post-filter:

Update on relation_tuple  (cost=117.53..411.59 rows=0 width=0)
  ->  Nested Loop  (cost=117.53..411.59 rows=103 width=209)
        ->  HashAggregate  (cost=116.84..117.84 rows=100 width=366)
              Group Key: (found_tuples.namespace)::text, (found_tuples.object_id)::text, (found_tuples.relation)::text, (found_tuples.userset_namespace)::text, (found_tuples.userset_object_id)::text, (found_tuples.userset_relation)::text, found_tuples.created_xid
              ->  Subquery Scan on found_tuples  (cost=0.70..115.09 rows=100 width=366)
                    ->  Limit  (cost=0.70..114.09 rows=100 width=171)
                          ->  Index Scan using ix_relation_tuple_alive_by_resource_rel_subject_covering on relation_tuple relation_tuple_1  (cost=0.70..56180.78 rows=49544 width=171)
                                Index Cond: (((namespace)::text = '<redacted>'::text) AND ((relation)::text = '<redacted>'::text) AND ((userset_namespace)::text = '<redacted>'::text))
        ->  Index Scan using ix_relation_tuple_by_subject on relation_tuple  (cost=0.70..2.93 rows=1 width=177)
              Index Cond: (((userset_object_id)::text = (found_tuples.userset_object_id)::text) AND ((userset_namespace)::text = (found_tuples.userset_namespace)::text) AND ((userset_relation)::text = (found_tuples.userset_relation)::text) AND ((namespace)::text = (found_tuples.namespace)::text) AND ((relation)::text = (found_tuples.relation)::text))
              Filter: (((found_tuples.object_id)::text = (object_id)::text) AND (found_tuples.created_xid = created_xid))

The planner estimates that inner lookup at one row. The real cost is the number of relationships sharing that subject on that relation, because object_id is only checked after the walk. Observed on a 157M-row table:

Batch size makes no difference, since the cost is per row. OptionalLimit exists to bound the cost of a delete, but today that bound only holds when subjects are not shared.

Proposed Solution

Keying the UPDATE on the physical row address avoids the re-lookup entirely:

WITH found_tuples AS (SELECT tableoid, ctid FROM relation_tuple WHERE <filter> AND deleted_xid = <live> LIMIT 1000)
UPDATE relation_tuple SET deleted_xid = $1
WHERE (tableoid, ctid) IN (SELECT tableoid, ctid FROM found_tuples)

Update on relation_tuple  (cost=115.59..229.09 rows=0 width=0)
  ->  Nested Loop  (cost=115.59..229.09 rows=100 width=48)
        ->  HashAggregate  (cost=115.59..116.59 rows=100 width=44)
              Group Key: found_tuples.tableoid, found_tuples.ctid
              ->  Subquery Scan on found_tuples  (cost=0.70..115.09 rows=100 width=44)
                    ->  Limit  (cost=0.70..114.09 rows=100 width=10)
                          ->  Index Scan using ix_relation_tuple_alive_by_resource_rel_subject_covering on relation_tuple relation_tuple_1  (cost=0.70..56180.78 rows=49544 width=10)
                                Index Cond: (((namespace)::text = '<redacted>'::text) AND ((relation)::text = '<redacted>'::text) AND ((userset_namespace)::text = '<redacted>'::text))
        ->  Tid Scan on relation_tuple  (cost=0.00..1.11 rows=1 width=10)
              TID Cond: (found_tuples.ctid = ctid)
              Filter: (found_tuples.tableoid = tableoid)

The inner side becomes a Tid Scan: one heap fetch per row, independent of fan-in. Verified on Aurora PostgreSQL and on vanilla PostgreSQL 16.4. Semantics are unchanged: the CTE and the UPDATE share one statement snapshot, and a row version replaced by a concurrent writer surfaces as the same serialization failure the current created_xid match produces, which the datastore already retries.

This is the pattern the GC already uses. batchDelete in internal/datastore/postgres/gc.go selects gcPKCols = {tableoid, ctid} and deletes with WHERE (tableoid, ctid) IN (SELECT tableoid, ctid FROM rows), including tableoid for partitioned tables. The change to deleteRelationshipsWithLimit is the selectForDelete column list and the IN list in the CTE format string.

Considerations

• Isolation level. The ctid join matches only the row version the CTE saw. Under SERIALIZABLE (the default) and REPEATABLE READ, a concurrent modification of that row raises a serialization failure in both the current and proposed forms, so behaviour is identical. Under READ COMMITTED they would differ: the seven-column key follows the update chain and still soft-deletes the new version, while the ctid form skips it for that round. SpiceDB does not run write transactions at READ COMMITTED, so this is theoretical, but it is the one semantic difference. Address reuse is not a concern: vacuum cannot remove a tuple visible to a live snapshot, so a ctid returned by the CTE cannot be recycled within the same statement.
• Partitioned tables. ctid is only unique per physical table, hence the tableoid pairing, which mirrors gcPKCols. The datastore tests should be run against the partitioned configuration.
• Plan stability. The fast plan is a nested loop with a Tid Scan inner side. If the planner ever chose a hash semi-join instead, the inner side would become a sequential scan, which is worse than today. At the default --max-delete-relationships-limit of 1000 the nested loop wins by a wide margin. For the non-partitioned case, WHERE ctid = ANY (ARRAY(SELECT ctid FROM …)) plans as a Tid Scan with TID Cond: (ctid = ANY ($0)) and has no join at all, at the cost of dropping tableoid.