what version of spicedb are you using? there should be an index on the timestamp field

ix_relation_tuple_transaction_by_timestamp

but from the explain output it doesn't look like that's being used