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

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. The planner must match the predicate. 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. 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.

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

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

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

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;

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.