Postgres slow exists subquery

Question

I have a queue system that has two tables, jobs and jobs_queues. jobs is where we put jobs to run and job_queues we populate with queue names so that when we pick jobs we can discard those that are already running, so queues runs sequentially.

My problem lies with the sub query to check locked jobs in que job_queues table. The query looks like this:

explain analyze
select jobs.queue_name, jobs.id
from "graphile_worker".jobs
where (jobs.locked_at is null or jobs.locked_at < (now() - '4 hours'::interval))
and (
  jobs.queue_name is null
or
  exists (
    select 1
    from "graphile_worker".job_queues
    where job_queues.queue_name = jobs.queue_name
    and (job_queues.locked_at is null or job_queues.locked_at < (now() - '4 hours'::interval))
    for update
    skip locked
  )
)
and run_at <= now()
and attempts < max_attempts
and (null is null or jobs.task_identifier = any(null))
and (null is null or (flags ?| null) is not true)
order by priority asc, run_at asc, id asc
limit 1
for update
skip locked;

The DDL for the tables can be seem here: https://github.com/graphile/worker/blob/main/sql/000001.sql (its from a library)

I have populated the tables with 100 queue names in job_queues with each having 10000 jobs in the jobs table, que query plan for the query looks like this.

Limit  (cost=0.43..17.33 rows=1 width=33) (actual time=149.335..149.336 rows=1 loops=1)
  ->  LockRows  (cost=0.43..2817155.90 rows=166667 width=33) (actual time=149.335..149.335 rows=1 loops=1)
        ->  Index Scan using jobs_priority_run_at_id_locked_at_without_failures_idx on jobs  (cost=0.43..2815489.23 rows=166667 width=33) (actual time=149.332..149.332 rows=1 loops=1)
              Index Cond: (run_at <= now())
              Filter: ((attempts < max_attempts) AND ((locked_at IS NULL) OR (locked_at < (now() - '04:00:00'::interval))) AND ((queue_name IS NULL) OR (SubPlan 1)))
              Rows Removed by Filter: 80000
              SubPlan 1
                ->  LockRows  (cost=4.28..8.31 rows=1 width=10) (actual time=0.002..0.002 rows=0 loops=79993)
                      ->  Bitmap Heap Scan on job_queues  (cost=4.28..8.30 rows=1 width=10) (actual time=0.001..0.001 rows=0 loops=79993)
                            Recheck Cond: (queue_name = jobs.queue_name)
                            Filter: ((locked_at IS NULL) OR (locked_at < (now() - '04:00:00'::interval)))
                            Rows Removed by Filter: 1
                            Heap Blocks: exact=79993
                            ->  Bitmap Index Scan on job_queues_pkey  (cost=0.00..4.28 rows=1 width=0) (actual time=0.001..0.001 rows=1 loops=79993)
                                  Index Cond: (queue_name = jobs.queue_name)
Planning time: 0.313 ms
Execution time: 149.391 ms

If I were to remove the locked_at in the where part of the sub query it gets much faster:

Limit  (cost=0.43..17.32 rows=1 width=33) (actual time=0.062..0.063 rows=1 loops=1)
  ->  LockRows  (cost=0.43..2814655.91 rows=166667 width=33) (actual time=0.061..0.062 rows=1 loops=1)
        ->  Index Scan using jobs_priority_run_at_id_locked_at_without_failures_idx on jobs  (cost=0.43..2812989.24 rows=166667 width=33) (actual time=0.056..0.057 rows=1 loops=1)
              Index Cond: (run_at <= now())
              Filter: ((attempts < max_attempts) AND ((locked_at IS NULL) OR (locked_at < (now() - '04:00:00'::interval))) AND ((queue_name IS NULL) OR (SubPlan 1)))
              Rows Removed by Filter: 1
              SubPlan 1
                ->  LockRows  (cost=4.28..8.30 rows=1 width=10) (actual time=0.032..0.032 rows=1 loops=1)
                      ->  Bitmap Heap Scan on job_queues  (cost=4.28..8.29 rows=1 width=10) (actual time=0.021..0.021 rows=1 loops=1)
                            Recheck Cond: (queue_name = jobs.queue_name)
                            Heap Blocks: exact=1
                            ->  Bitmap Index Scan on job_queues_pkey  (cost=0.00..4.28 rows=1 width=0) (actual time=0.008..0.008 rows=1 loops=1)
                                  Index Cond: (queue_name = jobs.queue_name)
Planning time: 0.232 ms
Execution time: 0.142 ms

A weird thing that I am seeing is that with each queue I lock at the job_queues table, the query gets heavier, here are some query plants with different number of locked queues (by lock I mean setting locked_at and locked_by columns in the job_queues and job tables):

0 jobs: https://explain.depesz.com/s/vM9g 1 job: https://explain.depesz.com/s/a0Lv 2 jobs: https://explain.depesz.com/s/fJ7I 3 jobs: https://explain.depesz.com/s/ouW9 8 jobs: https://explain.depesz.com/s/s9Yb

My question then is why is it so slow and why it gets slower the more rows I set locked_at and how can I optimize it.

Answer 1

Using EXISTS with OR nested in a more complex predicate is almost certainly going to force it to run that query once for every row otherwise considered. Also SomeField IS NULL OR SomeField < value will result in a scan so if other predicates are not selective enough¹ (or don't have a relevant index) to limit the rows considered you might be running the sub-select for most of those 10,000 jobs.

Things I might try with a query like this:

1. Refactor the EXISTS into a LEFT OUTER JOIN with a predicate in the WHERE to discard rows that don't match. If you were getting a list and there are cases where there could be multiple matches for a row in the outer table you might need to use GROUP BY or DISTINCT to de-duplicate results, though as you are just caring about the first result out this won't matter³.
2. Break it into two SELECTs one with WHERE locked_at IS NULL and one with WHERE locked_at < (now() - '4 hours'::interval) and combine them with UNION, either replicating the rest of the query in each new select or as a CTE that you then use to further filter². This can often improve such queries by turning a scan into two or more seeks. NOTE: this relies on there being a usable index on locked_at, otherwise you'll turn one scan into two. It also relies on neither check matching most of the rows.
3. Both of the above.

Another option if you can alter the schema might be to have a direclty indexable column that states a queue is elegable to go and search based upon that instead of deriving this property. That may add too much extra logic for maintaining that value though so you'd have to assess that against the savings made in queries like these.

---

^{[1] run_at <= now() and attempts < max_attempts are unlikely to be very selective}

^{[2] you may get quite different performance from these two options, and it'll vary further depending on your DB version, so both. I'd prefer the CTE option as it'll be clearer and easier to maintain, if it performs as well or better (or at least not significantly worse)}

^{[3] it might be duplicated, as might others, but you'll never care as you are not considering anything but the first row so you are not going to double-up a further action because of a duplicate result}

Answer 2

This is pretty easy to explain. You are looking for the first job belonging to an unlocked queue (which meet some other criteria as well, but apparently those are easy to meet, as well as not meeting some other criteria but those are apparently also pretty easy to not meet). As more and more queues are locked, jobs belonging to unlocked ones get harder and harder to find and it takes more and more work to find them.

If you don't care about whether the queues are locked, then it is pretty easy to find jobs.

As for how to optimize, well, just stop doing it. If all your queues are full, stop trying to make them fuller. Work on making them emptier instead.