Repository navigation
Postgres - ReadRelationships with optional_resource_id_prefix filter cannot use index #3274
Description
Description
ReadRelationships with a prefix filter causes a query like this to be generated (captured from the datastore's query builder, with pg_current_snapshot() standing in for a specific revision):
SELECT object_id, relation, userset_namespace, userset_object_id, userset_relation, caveat_name, caveat_context, expiration
FROM relation_tuple
WHERE pg_visible_in_snapshot(created_xid, pg_current_snapshot()) = true
AND pg_visible_in_snapshot(deleted_xid, pg_current_snapshot()) = false
AND namespace = '<namespace>'
AND object_id LIKE '<prefix>\_%'
AND (expiration IS NULL OR expiration > NOW());Which with en_US.UTF-8 collation (default in RDS) does a seq scan:
Gather (cost=1000.00..410914.91 rows=21 width=154) (actual time=82.851..1220.622 rows=11 loops=1)
Workers Planned: 2
Workers Launched: 2
Buffers: shared hit=327354 read=32287
I/O Timings: shared read=2045.173
-> Parallel Seq Scan on relation_tuple (cost=0.00..409912.81 rows=9 width=154) (actual time=446.095..1202.032 rows=4 loops=3)
" Filter: (((object_id)::text ~~ '<prefix>\_%'::text) AND ((namespace)::text = '<namespace>'::text) AND pg_visible_in_snapshot(created_xid, pg_current_snapshot()) AND (NOT pg_visible_in_snapshot(deleted_xid, pg_current_snapshot())) AND ((expiration IS NULL) OR (expiration > now())))"
Rows Removed by Filter: 1367386
Buffers: shared hit=327354 read=32287
I/O Timings: shared read=2045.173
Planning:
Buffers: shared hit=1
Planning Time: 0.161 ms
Execution Time: 1220.659 ms
I was hoping using the prefix filter would be an optimization for something which is currently making a lot of DB calls/load but without it being able to use the index I suspect it will make it worse.
That a filter may not be able to use indexes is called out in the filter docs
NOTE: The performance of the API will be affected by the selection of fields on which to filter. If a field is not indexed, the performance of the API can be significantly slower.
But this seems like a reasonable case for an index.
Possible Solution
Adding this index allowed it to do an index scan instead:
CREATE INDEX CONCURRENTLY ix_relation_tuple_by_resource_id_prefix ON relation_tuple (namespace, object_id varchar_pattern_ops);Index Scan using ix_relation_tuple_by_resource_id_prefix on relation_tuple (cost=0.56..2.79 rows=22 width=154) (actual time=0.035..0.052 rows=11 loops=1)
Index Cond: (((namespace)::text = '<namespace>'::text) AND ((object_id)::text ~>=~ '<prefix>_'::text) AND ((object_id)::text ~<~ '<prefix>`'::text))
" Filter: (((object_id)::text ~~ '<prefix>\_%'::text) AND pg_visible_in_snapshot(created_xid, pg_current_snapshot()) AND (NOT pg_visible_in_snapshot(deleted_xid, pg_current_snapshot())) AND ((expiration IS NULL) OR (expiration > now())))"
Buffers: shared hit=15
Planning:
Buffers: shared hit=49 read=1
I/O Timings: shared read=0.613
Planning Time: 0.988 ms
Execution Time: 0.635 ms
Claude's summary
ReadRelationships with optional_resource_id_prefix compiles to object_id LIKE 'prefix%' (BuildLikePrefixClause, internal/datastore/common/sql.go). Postgres can only serve a LIKE 'prefix%' range scan from a btree under C collation or a pattern opclass[0][1], but relation_tuple.object_id is plain VARCHAR in the database's default collation and none of the shipped indexes use varchar_pattern_ops — so on typical deployments (docker/RDS default locales) every prefix-filtered read degrades to a full table scan. Adding CREATE INDEX ... ON relation_tuple (namespace, object_id varchar_pattern_ops) restores an index range scan (~2000× fewer buffers in our 4M-row test). Suggestion: ship such an index in a migration, or document that prefix filters require C collation or a manual pattern-ops index.
Sources
[0] https://www.postgresql.org/docs/current/indexes-types.html#INDEXES-TYPES-BTREE
[1] https://www.postgresql.org/docs/current/indexes-opclass.html
Activity
tstirrat15 commentedon Aug 21, 2026
We are generally wary of adding new indices, as they both reduce write throughput and can entail a large amount of temporary load on large deployments as the index is built. Prefixes especially were intended as an escape hatch, not something to be relied upon in a latency-sensitive context.
What's the use case here? What are you trying to do that's prevented by the lack of this index?
Vojtasii commentedon Sep 9, 2026
Hi, I found this issue while encountering a similar problem on our performance testing environment.
In our case, we have two query shapes that would benefit from an index.
DeleteRelationshipswithoptional_resource_id_prefix;removing a whole subtree across every resource type in one call, when a tenant is deleted.
ReadRelationshipswithresource_type+optional_resource_id_prefix; a reconcilerthat diffs what SpiceDB holds against our own store. This is mostly "structural" tuples (resource inheritance and similar).
The delete is on a fairly standard path (though more common in tests than production).
The read is outside normal APIs, so latency is not as critical there, and the reconciliation runs at a time with the least other traffic. It's a bit of a latent trap though, if anyone reuses the reconciliation code for other purposes (for example, declarative-style APIs).
On ~3M relationships both plan as
Parallel Seq Scan. The delete was causing more damage, ittook seconds per call, and because writes run at SERIALIZABLE, a prefix scan that reads the whole table conflicts with concurrent writes to it regardless of what they touch. In our case
WriteRelationshipsaveraged 14x the baseline while there was no pool queuing.I checked out #3278 to see if that helps us: the proposed
(namespace, object_id varchar_pattern_ops)serves the typedReadRelationshipsonly. Delete without type has nonamespace, switching the order of the columns would serve both our cases, since the prefix is the selective predicate in each.Can't answer whether it should be indexed or not, I did see the NOTE about possible performance issues, though in our case just by "clever" id construction we can have a lot simpler cleanup of tenants than we otherwise would. We can either keep the index ourselves, rework the cleanup, or make it delayed and offload it, similarly to the "reconciler" so that it does not conflict with normal traffic.
epbensimpson commentedon Sep 10, 2026
Sorry I hadn't seen the original question, but the above comment outlines basically the same use cases we have. The original case that was causing us a problem was the reconcile scenario.
More recently I was bulk deleting relationships in preparation to remove some relations from the schema and was struggling with cluttered namespaces making the deletes with a limit untenably slow due to the query it uses and unbounded deletes would fail due to serializable conflicts.
We have the index proposed in my initial comment in place already, and as we knew the IDs were all GUIDs we were able to speed it up massively using
optional_resource_id_prefixto shard the requests with a prefix of 2 hex digits (256 shards00 - ff) and an unbounded delete to significantly increase the speed.This was a workaround made possible by the prefix index, I actually have a proposal for a fix to improve the speed of the limited delete without prefixes involved which I'll open a separate issue for.
armin-perplexity commentedon Sep 15, 2026
This is also an issue for us when trying to fetch roles assigned to a group sharing a common prefix.