Job queues per tenant in PostgreSQL: the noisy neighbour

A job queue in PostgreSQL is a solved problem: one table, FOR UPDATE SKIP LOCKED, as many workers as you like. In a multi-tenant SaaS it has one flaw that a single-tenant test never shows. When one customer imports ten thousand invoices, every other customer’s password-reset mail waits behind them.

We measured how long, and what it costs to fix. Four workers, one tenant queuing 1,000 jobs of 20 ms, ten small tenants queuing five each a second later. With a plain first-in-first-out queue the small tenants waited a median of 4.5 seconds. With round-robin per tenant, 0.10 to 0.15 seconds. The round-robin query then turned out to have a trap of its own: with a skewed backlog and idle tenants in the rotation, the obvious way to write it took 10 seconds per job.

Why does one tenant slow down every other tenant’s jobs?

Because a FIFO queue orders by arrival, not by customer. The standard dequeue query takes the oldest job nobody else has locked:

select id, tenant_id
from jobs
where status = 'queued'
order by id
limit 1
for update skip locked;

SKIP LOCKED is what makes this work with several workers; the PostgreSQL documentation describes it as suitable “to avoid lock contention with multiple consumers accessing a queue-like table”. But the order is global. A job queued after 1,000 others starts after those 1,000, whoever they belong to.

The setup

PostgreSQL 17.10 in a throwaway container, default settings. One jobs table and a partial index for the queued jobs:

create table jobs (
  id bigint generated always as identity primary key,
  tenant_id int not null,
  status text not null default 'queued',
  enqueued_at timestamptz not null default clock_timestamp(),
  started_at timestamptz,
  finished_at timestamptz
);
create index jobs_queued_fifo on jobs (id) where status = 'queued';

Four workers, each with its own connection, use the claim pattern: in one short transaction they select a job with SKIP LOCKED and set it to running; the work — 20 ms, simulated — happens outside that transaction; a second statement marks it done. The large tenant queues 1,000 jobs at the start; one second later ten small tenants queue five jobs each. We measured the wait from enqueued_at to started_at, and ran every scenario at least twice.

FIFO against round-robin

For round-robin, a second table keeps track of when each tenant was last served, and the dequeue query asks: which tenant has waited longest, and what is that tenant’s oldest free job?

create table queue_tenants (
  tenant_id int primary key,
  last_served timestamptz not null default '-infinity'
);
create index on queue_tenants (last_served);

select j.id, qt.tenant_id
from queue_tenants qt
cross join lateral (
  select id from jobs
  where tenant_id = qt.tenant_id and status = 'queued'
  order by enqueued_at, id
  limit 1
  for update skip locked
) j
order by qt.last_served
limit 1;

In the same claim transaction the worker sets last_served for that tenant to clock_timestamp(). The lock sits in the sub-select, which PostgreSQL allows — “the rows locked are those returned to the outer query by the sub-query” — so a locked job only skips that one job, not the tenant. That matters: the obvious alternative, numbering each tenant’s jobs with row_number() over (partition by tenant_id …), cannot be locked in the same query level, because FOR UPDATE “cannot be specified with WINDOW”.

The ranges cover every run: four of FIFO, six of round-robin (with the sub-select ordered by id and by enqueued_at, which made no difference at this size). The small tenants went from waiting for the whole backlog to waiting for a few rounds. The large tenant pays for that: its last job finished 0.6 seconds later, because 50 small jobs went in between and every dequeue got more expensive.

That the large tenant is not throttled to one worker is the point of the lock in the sub-select. On its own, with no other tenants in the queue, the large tenant’s 1,000 jobs took 5.42 s with FIFO and 5.70 s with round-robin — all four workers stayed busy, at 5 % extra cost. Locking the tenant row instead of the job would have limited it to one job at a time.

Why does the round-robin query take 10 seconds with a large backlog?

Because the planner assumes an average tenant, and in a queue no tenant is average. We filled the table with 100,000 queued jobs of the large tenant and one job each for ten small tenants, with 1,000 tenants in queue_tenants, 989 of which had nothing queued. Then we timed a single dequeue with the sub-select ordered by id, the natural choice, next to a partial index on (tenant_id, id) where status = 'queued':

With order by id the planner chose to walk the queued jobs in id order and filter on tenant_id, expecting to hit the tenant within a few rows. For the large tenant that is true. For a small tenant it walked past 100,004 jobs of the large one; for a tenant with nothing queued it walked the whole backlog for nothing — 989 times per dequeue, about a million buffer reads. Dropping the FIFO index did not help: the planner then walked the primary key in the same way, again in about 10 seconds.

The fix was to order the sub-select by a column that only the per-tenant index can deliver:

create index jobs_queued_tenant
  on jobs (tenant_id, enqueued_at, id)
  where status = 'queued';

With order by enqueued_at, id in the sub-select, every probe became one short descent into that index: 1.17 ms with 989 idle tenants, 0.15 ms when the table held only tenants with work. Check the plan of your own dequeue query with a skewed backlog, not with an empty test queue. Ours walked the index on last_served under the Limit and stopped at the first tenant with a free job; a plan that sorts all tenants first could lock one job per tenant until the transaction ends. With a backlog of 1,000 jobs both versions took 1.1 ms and looked the same.

The last row shows the other cost: every idle tenant in queue_tenants is one index probe per dequeue, and at 10,000 tenants that was 10.5 ms. Keeping only tenants with queued work in that table brings it back to 0.15 ms. Adding a tenant when it queues is one insert … on conflict do nothing; removing it when its queue is empty is where a race hides — a job queued between your check and your delete — and that part we did not measure.

And row-level security?

A worker serves every tenant, so it cannot run with a fixed tenant context. The queue table itself is infrastructure and usually has no policy; the job’s work should run as that tenant. Set the tenant from the claimed row with SET LOCAL inside the transaction that does the work — not with SET, which on a pooled connection hands that tenant to the next job. What goes wrong otherwise we measured in PgBouncer and RLS: tenant context, SET LOCAL, shared plans.

What we did not measure

Priorities, a cap on concurrent jobs per tenant, weighted fairness (a paying tier getting two turns), more than four workers, jobs that hold their lock for the duration of the work, retries, and the upkeep of queue_tenants under load. The timings come from one machine with a warm cache; read them as proportions. The proportions are the finding: FIFO made small tenants wait 30 to 45 times longer, and a dequeue query that looked fine on a small backlog was four orders of magnitude slower on a skewed one.

This is decision territory we cover in multi-tenant SaaS on PostgreSQL: six decisions: the things that are cheap to get right before the first large customer and expensive after.

Sources: the PostgreSQL 17 documentation on SELECT (the locking clause, SKIP LOCKED, locking in a sub-select and the restriction on WINDOW), read on 30 September 2026. All measurements are our own, on PostgreSQL 17.10, on 30 September 2026.