The query running in O(queue size) is very likely avoidable if you add an index on the tenant_id.
Ideally the query planner figures this out (see the sibling comment), but if not, the query can likely be written to "encourage" the planner, for example by first selecting the top few values of md5(tenant_id, current_timestamp) within a subquery before lateral joining into the SKIP LOCKED table.
If the concern is only that the queue falls over once it gets large enough, you can also LIMIT to a fixed number of rows before doing the outer SELECT. This gives a weaker fairness bound (tenants that have fewer than O(queue size / selected items) rows are at risk of being ignored) but you get a better guarantee of progress under contention.
Ideally the query planner figures this out (see the sibling comment), but if not, the query can likely be written to "encourage" the planner, for example by first selecting the top few values of md5(tenant_id, current_timestamp) within a subquery before lateral joining into the SKIP LOCKED table.
If the concern is only that the queue falls over once it gets large enough, you can also LIMIT to a fixed number of rows before doing the outer SELECT. This gives a weaker fairness bound (tenants that have fewer than O(queue size / selected items) rows are at risk of being ignored) but you get a better guarantee of progress under contention.