Browsing jobs on lookout can be slow for high scale when ordering by submitted timestamp

[Sovietaced]

We noticed some very slow queries for jobs when sorting by the submitted timestamp.

lookoutv2=>  EXPLAIN ANALYZE SELECT selected_jobs.job_id, selected_jobs.queue, selected_jobs.owner, selected_jobs.namespace, selected_jobs.jobset, selected_jobs.cpu, selected_jobs.memory, selected_jobs.ephemeral_storage, selected_jobs.gpu, selected_jobs.priority, selected_jobs.submitted, selected_jobs.cancelled, selected_jobs.state, selected_jobs.last_transition_time, selected_jobs.duplicate, selected_jobs.priority_class, selected_jobs.latest_run_id, selected_jobs.cancel_reason, selected_jobs.annotations, selected_runs.runs FROM ( SELECT * FROM job AS j  WHERE j.queue = 'compute' ORDER BY j.submitted DESC LIMIT 500 OFFSET 11500 ) AS selected_jobs CROSS JOIN LATERAL ( SELECT COALESCE( json_agg( json_strip_nulls( json_build_object( 'runId', run_id, 'cluster', cluster, 'node', node, 'leased', leased AT TIME ZONE 'UTC', 'pending', pending AT TIME ZONE 'UTC', 'started', started AT TIME ZONE 'UTC', 'finished', finished AT TIME ZONE 'UTC', 'jobRunState', job_run_state, 'exitCode', exit_code ) ) ORDER BY COALESCE(leased, pending) ) FILTER (WHERE run_id IS NOT NULL), '[]' ) AS runs FROM job_run WHERE job_id = selected_jobs.job_id ) AS selected_runs;
                                                                    QUERY PLAN                                                                     
---------------------------------------------------------------------------------------------------------------------------------------------------
 Nested Loop  (cost=896095.16..900449.43 rows=500 width=810) (actual time=5764.707..6064.367 rows=500 loops=1)
   ->  Limit  (cost=896086.59..896144.93 rows=500 width=818) (actual time=5764.503..6057.639 rows=500 loops=1)
         ->  Gather Merge  (cost=894744.83..1052054.68 rows=1348276 width=818) (actual time=5759.561..6057.200 rows=12000 loops=1)
               Workers Planned: 2
               Workers Launched: 2
               ->  Sort  (cost=893744.80..895430.15 rows=674138 width=818) (actual time=4455.785..4456.421 rows=4083 loops=3)
                     Sort Key: j.submitted DESC
                     Sort Method: top-N heapsort  Memory: 7101kB
                     Worker 0:  Sort Method: external merge  Disk: 70792kB
                     Worker 1:  Sort Method: external merge  Disk: 76952kB
                     ->  Parallel Seq Scan on job j  (cost=0.00..339991.20 rows=674138 width=818) (actual time=0.009..940.697 rows=540771 loops=3)
                           Filter: ((queue)::text = 'compute'::text)
                           Rows Removed by Filter: 135064
   ->  Aggregate  (cost=8.57..8.58 rows=1 width=32) (actual time=0.013..0.013 rows=1 loops=500)
         ->  Index Scan using idx_job_run_job_id on job_run  (cost=0.43..8.53 rows=2 width=135) (actual time=0.005..0.005 rows=1 loops=500)
               Index Cond: ((job_id)::text = (j.job_id)::text)
 Planning Time: 1.073 ms
 Execution Time: 6065.480 ms

It appears the reason for this is a sequential scan due to having no index on the submitted column