Postgres - ReadRelationships with optional_resource_id_prefix filter cannot use index
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 msI 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 msClaude'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
Source: authzed/spicedb