Partial Indexes for Job Queue Polling #

Twenty workers poll a jobs table every 200 ms with SELECT … FOR UPDATE SKIP LOCKED LIMIT 10. The table holds 40 million rows, of which a few hundred are pending at any moment. On Monday the poll took 0.3 ms; by Thursday it takes 45 ms and the database’s CPU is dominated by it, even though the pending count has not changed.

A partial index is the right structure for this shape — the principles are in partial index implementation — but a queue exposes a failure mode that most partial indexes never meet: extremely high churn through a tiny live set.

The Planner Condition #

The poll:

SELECT id, payload FROM jobs
WHERE status = 'queued' AND run_at <= now()
ORDER BY run_at
LIMIT 10
FOR UPDATE SKIP LOCKED;

The index:

CREATE INDEX CONCURRENTLY jobs_queued_run_at_idx
  ON jobs (run_at) WHERE status = 'queued';

The planner uses it because the query’s status = 'queued' implies the index predicate — the matching rules are in partial index predicate matching rules. Because the index is ordered on run_at, the scan returns jobs in ORDER BY order and the Limit can stop after ten locked rows. No sort, no scan of finished jobs.

The complication is how rows leave the index. A worker finishes a job with UPDATE jobs SET status = 'done'. The new row version does not satisfy the index predicate, so no new index entry is made — but the old entry remains, pointing to the now-dead version, until vacuum removes it. Every poll that walks the index from the oldest run_at passes through those dead entries first, fetching each heap tuple to check visibility. Index entries can be marked dead during scans (“killed” once the scanner sees that the tuple is dead to everyone), which helps, but only after all older transactions have finished, and long-running transactions anywhere on the server prevent it.

Dead entries sit in front of the live queue A partial index ordered by run_at. The oldest portion on the left is filled with dead entries left by jobs that were completed but not yet vacuumed. The live queued jobs are a short segment on the right. A poll scan starts at the left and must pass every dead entry, fetching heap tuples to check visibility, before reaching the ten live jobs it will lock. jobs_queued_run_at_idx (ordered by run_at) dead entries from completed jobs (≈ 380,000) live queued (≈ 300) each poll scans from the oldest run_at dead entry → heap fetch → invisible cost grows with churn since last vacuum live entry → LockRows → skip if locked stop at LIMIT 10

Annotated EXPLAIN Evidence #

Healthy, right after vacuum:

Limit  (actual time=0.05..0.28 rows=10 loops=1)
  ->  LockRows  (actual time=0.05..0.27 rows=10 loops=1)
        ->  Index Scan using jobs_queued_run_at_idx on jobs
              (actual time=0.03..0.16 rows=14 loops=1)
              Index Cond: (run_at <= now())
              Buffers: shared hit=22
-- rows=14 under LockRows → 4 rows were skipped because other workers had them locked
-- 22 buffers for 14 rows: no dead entries in the way
Execution Time: 0.31 ms

Degraded, three days of churn:

Limit  (actual time=44.9..45.2 rows=10 loops=1)
  ->  LockRows  (actual time=44.9..45.2 rows=10 loops=1)
        ->  Index Scan using jobs_queued_run_at_idx on jobs
              (actual time=44.8..45.0 rows=13 loops=1)
              Index Cond: (run_at <= now())
              Buffers: shared hit=61204
-- still only 13 rows produced, but 61,204 buffers touched
-- that gap is dead index entries and their heap tuples
Execution Time: 45.3 ms

Metric to watch: buffers divided by rows produced under LockRows. It should stay in single digits.

The ratio that reveals dead entries Three lines of the degraded poll plan are annotated. LockRows over an index scan confirms the intended shape. Thirteen rows produced shows the queue is short. Sixty-one thousand buffers for thirteen rows shows dead entries in the scan path. LockRows → Index Scan using jobs_queued… intended shape, no Sort Index Scan … rows=13 queue itself is short Buffers: shared hit=61204 ≈ 4,700 buffers per row: dead entries

Step-by-Step Resolution #

  1. Index the ordering column inside the partial predicate as shown above. Include priority first if polls order by priority, run_at.

  2. Confirm the plan shape: Limit → LockRows → Index Scan on the partial index, with no Sort node.

  3. Measure dead entries:

    SELECT n_live_tup, n_dead_tup, last_autovacuum, autovacuum_count
FROM pg_stat_user_tables WHERE relname = 'jobs';

  4. Vacuum the queue table far more often than the global defaults allow:

    ALTER TABLE jobs SET (
  autovacuum_vacuum_scale_factor = 0,
  autovacuum_vacuum_threshold    = 5000,
  autovacuum_vacuum_cost_limit   = 2000
);

    A zero scale factor makes the trigger a fixed number of dead tuples regardless of table size. The mechanics are in autovacuum thresholds and dead-tuple drift.

  5. Find transactions holding back cleanup. Vacuum cannot remove tuples still visible to an old snapshot:

    SELECT pid, now() - xact_start AS age, state, left(query, 60)
FROM pg_stat_activity
WHERE xact_start IS NOT NULL ORDER BY xact_start LIMIT 5;

  6. Move finished jobs out when churn is too high for vacuum to keep up: delete completed rows in the same transaction that finishes them and archive elsewhere, or partition the table by time and drop old partitions.

Poll cost follows the vacuum cycle A sawtooth line of buffers per poll over time. With default autovacuum settings, the teeth are tall and far apart, rising to tens of thousands of buffers. With a fixed low threshold, the teeth are short and frequent, staying under a few hundred buffers. high low time → (each drop is an autovacuum pass on jobs) dashed: default thresholds · solid: fixed threshold of 5,000 dead tuples

Before and After #

-- BEFORE: default autovacuum, 3 days of churn
Index Scan using jobs_queued_run_at_idx  rows=13  Buffers: shared hit=61204      Execution Time: 45.3 ms

-- AFTER: autovacuum_vacuum_scale_factor = 0, threshold = 5000
Index Scan using jobs_queued_run_at_idx  rows=14  Buffers: shared hit=31         Execution Time: 0.34 ms

Why delete-on-completion behaves better than update-on-completion #

Both approaches leave a dead index entry behind, so the difference is not in the partial index itself. It is in the heap and in vacuum’s workload. Updating the row to done creates a new live version that stays in the table forever, so the table grows with every job and each autovacuum pass has more pages to consider. Deleting the row leaves only a dead version, which vacuum removes, and the table stays roughly the size of the live queue plus recent churn. Smaller tables are vacuumed faster, so dead index entries are cleared sooner and polls stay cheap.

Where completed jobs must be kept, write them to a separate history table in the same transaction that deletes them from the queue. The queue table then holds only work in progress, and the history table can be append-only, partitioned by time and indexed for reporting without affecting polling.

Priority queues and multiple partial indexes #

Queues that serve several job kinds or priorities often poll with different predicates: WHERE status = 'queued' AND queue = 'email', WHERE status = 'queued' AND priority >= 5. A single partial index on run_at still helps, but each poll filters out jobs of other kinds as it walks the index, and a busy kind can bury a quiet one. Two better shapes exist. Put the discriminating column first — (queue, run_at) WHERE status = 'queued' — so each poll starts at its own section of the index. Or create one partial index per hot queue, WHERE status = 'queued' AND queue = 'email', which keeps each index tiny. Either way, check that polls for the quietest queue do not show a large Rows Removed by Filter, which would mean they are paying for another queue’s backlog.

Common Pitfalls #

Indexing status instead of the ordering column. An index on (status) finds queued jobs but returns them unordered, adding a sort of every pending row per poll. Diagnostic signal: a Sort above the index scan. Fix: index run_at with WHERE status = 'queued'.

Omitting the predicate from the query. A poll that says status IN ('queued', 'retry') does not match WHERE status = 'queued'. Diagnostic signal: a sequential scan or a different index. Fix: align the index predicate with the query, or create one index per state.

A long transaction on a replica with hot_standby_feedback. It holds back vacuum on the primary. Diagnostic signal: n_dead_tup climbing despite frequent autovacuum runs. Fix: find and bound long transactions on replicas too.

Using LIMIT 1 with many workers. Workers contend for the same first row and skip past each other’s locks. Diagnostic signal: LockRows child producing many more rows than LIMIT. Fix: fetch a small batch per poll, or randomise among the oldest jobs.

Frequently Asked Questions #

Why does my queue poll get slower even though the queue is short? Completed jobs leave dead entries in the partial index until vacuum removes them, and each poll walks past them and checks their heap tuples. Polling cost tracks churn since the last vacuum, not queue length.

What does LockRows mean in the plan? It applies FOR UPDATE to each row from its child. With SKIP LOCKED, rows locked by another worker are discarded, so the child may produce more rows than the LIMIT.

Should the partial index include the ORDER BY column? Yes. Indexing run_at inside the partial index lets the scan return jobs in order and stop at the limit instead of sorting every pending job.

Up: Partial Index Implementation