Should I use a partial index on a queue table where I only ever scan 'pending' rows?

Short answer: yes, a partial index is the textbook case for exactly this scenario.

Short answer

An index with a WHERE status = 'pending' predicate holds only a few thousand rows; it’s small, fits in memory, is fast to scan and cheap to update — and it steps right past the millions of dead rows without touching them. Which columns an index should carry and in what order is something I covered separately in the composite index order record; the question here is how to narrow that index further.

Why

1. A partial index only indexes matching rows. With CREATE INDEX ... WHERE status='pending' the index holds a few thousand entries, not millions. That keeps it almost entirely in cache and shrinks the tree that has to be updated on every insert/update.

2. It’s strictly better than a plain index on status. A plain index on the low-cardinality status column is mostly useless done values; the planner will often skip it and do a seq scan. For this access pattern the partial index is a clear win.

3. The same logic applies to any skewed predicate. The lesson isn’t queue-specific: any query targeting a small minority of the table — WHERE deleted_at IS NULL (soft delete), WHERE processed = false — gets the same win from a partial index. Anytime you pull “a few rows out of a sea of dead ones”, reach for it.

What to do

1. Put the ORDER BY column in the index. Workers typically do WHERE status='pending' ORDER BY created_at FOR UPDATE SKIP LOCKED. Include the sort key in the index: (created_at) WHERE status='pending'. That gets you an index-ordered scan and lets SKIP LOCKED step over locked rows and grab the next job instantly. The SQL looks like this:

   CREATE INDEX idx_jobs_pending
       ON jobs (created_at)
       WHERE status = 'pending';
   
   -- the worker's pull query:
   SELECT id, payload
   FROM jobs
   WHERE status = 'pending'
   ORDER BY created_at
   FOR UPDATE SKIP LOCKED
   LIMIT 1;

2. Pass the predicate as a literal in the query. Your query’s WHERE must be a condition the index predicate (status='pending') provably implies. If you query with a parameter like status = $1, the planner may not pick the index; write the condition as the literal 'pending' so the match can be proven.

3. Watch out for churn and bloat. When a row flips from pending to done it drops out of the partial index — that’s good. But heavy update traffic can produce bloat, so a healthy autovacuum matters. The good news: because the index is small, vacuuming it is cheap too.

Bottom line: personally I’d create a partial index on the pull predicate, including the ORDER BY column, and pair it with FOR UPDATE SKIP LOCKED. The one thing to watch: make sure your queries pass 'pending' as a literal so the planner actually picks the index. Verify once with EXPLAIN (ANALYZE, BUFFERS) that you’re getting an index scan; after that you can happily let millions of completed rows pile up.