Postgres slow exists subquery

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 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 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 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   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.