Outbox Your Indexes, Index Your Outbox

This memo provides information for the curious and the on-call. It does not specify an Internet standard of any kind. Distribution of this memo is unlimited, and comments are welcome by email (saksh.am [at] outlook [dot] in). I don’t trust comment boxes online.

A transactional outbox is polled by a background job that asks the database, every few hundred milliseconds, whether anything is pending. Most of the time the answer is no. This memo describes how that poll query can get slower as the table grows, until it reads most of an index to return nothing; why no alert fires; how to find a query like that without a fancy tool; and why a polling outbox needs a partial index on its pending state.

No war story this time. Just a trap that outbox tables love to walk into, and the way back out.

The short version: a query that answers “nothing to do” should be the cheapest query you have. With an outbox it can get more expensive every day, because the table it looks at only ever grows and the index it uses may not be able to narrow the search. Nothing breaks. It just quietly burns CPU.

The examples below use PostgreSQL, with a simplified table and queries.

Say a service saves an order and also has to tell the rest of the world about it, by publishing an event to a message broker. Two writes, two systems. If the database commit succeeds and the publish fails, there is no event to drive your “event-driven” system.

Fine, Saksham. Then publish first and write after?

Somehow even worse :/ Now the event is homeless. If the write fails after the publish, the rest of the world hears about an order that was never stored in the database, and consistency is far, far away.

Either way the two systems disagree, and we’ve hit the proverbial brick wall.

The transactional outbox is a simple way around that. You write the event to a table, in the same transaction as your data. Either both are saved or neither is. A background job then reads the table and publishes whatever is waiting.

BEGIN;
INSERT INTO orders (...) VALUES (...);
INSERT INTO outbox (topic, payload) VALUES ('orders', '{...}');
COMMIT;

A simple outbox table:

CREATE TABLE outbox (
  id              bigserial PRIMARY KEY,
  topic           text        NOT NULL,
  payload         jsonb       NOT NULL,
  status          text        NOT NULL DEFAULT 'pending',  -- pending, failed, published
  created_at      timestamptz NOT NULL DEFAULT now(),
  next_attempt_at timestamptz NOT NULL DEFAULT now()
);

The background job is usually a poller. Every few hundred milliseconds it asks the database: is anything pending?

Most of the time the answer is no.

The table only grows. Rows go from pending to published, and unless someone deletes them, they stay. So after a while the table is almost all history, and the rows that need attention are a tiny sliver of it.

The poll query is fine at a thousand rows. At hundreds of thousands, it can end up reading most of an index to return nothing. Two things make it worse.

3.1 The index led with a column the query didn’t use

Picture the index and the poll query as something like this:

CREATE INDEX outbox_topic_status ON outbox (topic, status);

SELECT id, topic, payload
FROM outbox
WHERE status = 'pending'
   OR (status = 'failed' AND next_attempt_at <= now())
ORDER BY id
LIMIT 100;

A B-tree index on (topic, status) is sorted by topic first, and by status only within each topic. Think of a phone book sorted by surname, then first name. Finding every “Smith” is quick: you jump to the S pages. Finding every “Priya”, with no surname, means reading the whole book, because the Priyas are scattered across every page.

That is what the poller does here. The query never says which topic, so the database cannot jump to a section of the index. It has to check every entry for a matching status. The index is still “used”, in the sense that it shows up in the plan, but only as a smaller copy of the table to read end to end. (Figure 1 in Section 6 draws this.)

Then why didn’t the planner just ignore the index?

Because reading the whole index can still be cheaper than reading the whole table. The index is smaller. So the planner picks it, honestly, as the least bad option. The real problem is that no good option exists.

3.2 An OR in the filter

The OR doubled the work. PostgreSQL can combine indexes for an OR: it scans the index once for each branch, builds a bitmap of matching rows from each, and merges them (a BitmapOr in the plan). That is usually a good trick. Here, each branch is its own full read of an index that cannot be narrowed, so the whole index is read twice per poll.

3.3 How bad

At that size, a poll like this can take hundreds of milliseconds. With the missing leading column added to the query, the same lookup takes under a millisecond.

Now remember how often it runs. A query that takes hundreds of milliseconds and fires every few hundred milliseconds keeps roughly one CPU core busy all the time, asking a question whose answer is almost always no.

• No errors. The query returns the right answer every time. It is just slow to say nothing.
• No slow requests. The poller is a background job. No user is waiting on it, so no request latency alert can see it.
• No disk activity. The index fits in memory, so every read is a cache hit. Nothing showed up as I/O.

It only shows up as a flat CPU line that never went down. A flat line does not look like an incident. It looks like the baseline.

So how do you find something that looks normal?

You stop asking “what is slow?” and start asking “what is the database actually busy with?” That is the next section.

None of this needs a paid database monitoring product. There are four steps, and each one checks the one before.

5.1 Traces, to rank queries by total time

If your services emit traces (RFC 0001 promised a memo on those), each database call is a span with a duration. Sum the durations per query and sort. A query that is cheap per call but runs constantly can easily top the list, above the “slow” queries everyone already knows about.

Treat this as a ranking, not a CPU measurement. A span’s duration includes network time, waiting for a connection and waiting on locks, so it tells you where to look, not exactly how much CPU went where.

5.2 The database’s own counters, to cross-check

PostgreSQL keeps running totals of what it reads. The two that matter here are rows scanned and pages read, per index:

SELECT s.indexrelname, s.idx_scan, s.idx_tup_read, io.idx_blks_hit, io.idx_blks_read
FROM pg_stat_user_indexes s
JOIN pg_statio_user_indexes io USING (indexrelid)
WHERE s.relname = 'outbox';

These are counters since the last reset, not rates. Run the query twice, a minute apart, and divide the difference by 60 to get per-second numbers. A huge idx_blks_hit with a near-zero idx_blks_read is the signature from Section 4: lots of reading, all of it from memory.

If the pg_stat_statements extension is installed, it gives the same thing per query: calls, total_exec_time and shared_blks_hit.

5.3 EXPLAIN (ANALYZE, BUFFERS) on the suspect

EXPLAIN (ANALYZE, BUFFERS)
SELECT id, topic, payload FROM outbox
WHERE status = 'pending'
   OR (status = 'failed' AND next_attempt_at <= now())
ORDER BY id LIMIT 100;

ANALYZE actually runs the query and reports real times and row counts. BUFFERS adds lines like Buffers: shared hit=... under each step: how many 8 kB pages it touched.

The number to look at is buffers, not just time. Time depends on how busy the machine is at that moment. Buffers count how much work the query did, and they do not lie. A query that returns 0 rows and touches thousands of pages is the bug, however fast it happened to run when you tried it.

5.4 Make the numbers agree

This check tells you that you have found the right query, not just a suspicious one:

pages per poll  ×  polls per second  ≈  pages per second from the counters

Pages per poll comes from BUFFERS in 5.3. Polls per second comes from the poller’s interval (or calls in pg_stat_statements). Pages per second comes from 5.2. If the product roughly matches the counter, this one query explains the reads, and you can stop looking. If it explains only a tenth of them, something else is reading too, so keep going.

A polling outbox needs a partial index on the pending state, and the poll query has to match it exactly.

A partial index has a WHERE clause. Only rows that match it get an entry. So instead of indexing every row the outbox has ever held, you index only the rows that still need attention:

CREATE INDEX CONCURRENTLY outbox_pending
  ON outbox (topic, next_attempt_at)
  WHERE status <> 'published';

When a row is published, it leaves the index. The index holds only what is waiting, so it stays tiny however big the table gets. “Is anything pending?” becomes a look at a handful of entries, or an empty index.

 BEFORE: index on (topic, status)                  one entry for every row, ever

 ┌─ billing ─────────────┬─ orders ──────────────┬─ users ───────────────┐
 │ F P pub pub ... pub   │ P pub pub pub ... pub │ pub pub pub ... pub   │
 └───────────────────────┴───────────────────────┴───────────────────────┘
 ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━►
 WHERE status = 'pending' ...   no topic, so no place to jump in.
                                Read every entry. Then again for the OR.

 AFTER: partial index on (topic, next_attempt_at)
        WHERE status <> 'published'               only rows still waiting

 ┌─ billing ─┬─ orders ──┬─ users ───┐
 │ F P       │ P         │ (empty)   │      pub rows are not in here at all
 └───────────┴───────────┴───────────┘
              ▲
              WHERE topic = 'orders' AND status <> 'published' ...
              jump straight to orders, read 1 entry, done.

 A million more published rows later:
   BEFORE  +1,000,000 entries to read on every poll
   AFTER   +0 (rows leave the index the moment they are published)

 F = failed, waiting to retry    P = pending    pub = published

The poll query then has to line up with it:

SELECT id, topic, payload
FROM outbox
WHERE topic = 'orders'
  AND status <> 'published'
  AND next_attempt_at <= now()
ORDER BY next_attempt_at
LIMIT 100
FOR UPDATE SKIP LOCKED;

• One pending condition. The OR is gone. Instead of two kinds of “needs attention” (new, and failed but due for a retry), there is one: not yet published. A failed row stays unpublished and gets its next_attempt_at pushed later, and the next_attempt_at <= now() filter handles the waiting.
• The leading column is present. The query names the topic, so the index search jumps straight to it (the surname, in the phone book).
• The condition matches the index’s, word for word. PostgreSQL only uses a partial index if it can prove, at planning time, that the query’s WHERE implies the index’s WHERE. It is not clever about this, so write the same condition. In particular, keep it a literal: a parameter like status <> $1 cannot be proven, and the planner will quietly skip the index.
• FOR UPDATE SKIP LOCKED is not part of the fix, but it is how you let more than one poller run without two of them grabbing the same row.

Is the partial index enough on its own?

It fixes the expensive part. Three more habits keep it fixed:

• Purge or archive published rows. The index no longer cares about them, but the table, its other indexes, vacuum and backups still do. Delete them in batches, or partition the table by time and drop old partitions.
• Back off the poll when there is nothing to do. If a poll comes back empty, wait longer before the next one (up to a ceiling), and go back to the short interval once something shows up. The cheapest query is the one you don’t run.
• Run EXPLAIN at realistic row counts, not on the dev database. This bug was invisible at a thousand rows. Fill a test table with production-like volume (generate_series makes this easy) and look at the buffers there.

• CREATE INDEX CONCURRENTLY builds the index without blocking writes, but it is slower, cannot run inside a transaction block, and if it fails it leaves an invalid index behind that you have to drop by hand.
• A partial index stays small only if vacuum keeps up. A published row leaves a dead index entry behind until vacuum cleans it, and a busy outbox makes a lot of those. Keep an eye on autovacuum for this table.
• PostgreSQL 18 added skip scan, which can sometimes search a multicolumn index whose leading column the query doesn’t constrain, if that column has few distinct values. It is a nice safety net, not a design. Don’t count on it.
• The table and queries in this memo are simplified to show the shape of the problem. Run EXPLAIN on your own.

“Nothing to do” should cost almost nothing. If it doesn’t, the index is answering a different question from the one the query asks.

• A B-tree can only narrow a search using its leading column. A query that skips it reads the whole index.
• An OR can mean one index scan per branch.
• A polling outbox needs a partial index on the pending state, with the poll query matching it exactly.
• Measure with buffers, not just time, and make the numbers agree before you call it found.

It also loops back to RFC 0001: no error, no slow request, no disk, only a flat CPU line that is easy to read as normal. Nothing says so. The data to find it is there all along, in counters nobody thinks to check.

[OUTBOX] Chris Richardson, “Pattern: Transactional outbox”, microservices.io.

[PG-PARTIAL] PostgreSQL documentation, “Partial Indexes”, postgresql.org/docs/current/indexes-partial.html.

[PG-MULTICOL] PostgreSQL documentation, “Multicolumn Indexes”, postgresql.org/docs/current/indexes-multicolumn.html.

[PG-BITMAP] PostgreSQL documentation, “Combining Multiple Indexes”, postgresql.org/docs/current/indexes-bitmap-scans.html.

[PG-EXPLAIN] PostgreSQL documentation, “Using EXPLAIN”, postgresql.org/docs/current/using-explain.html.

[PG-STATS] PostgreSQL documentation, “The Cumulative Statistics System”, postgresql.org/docs/current/monitoring-stats.html.

[PG-STATEMENTS] PostgreSQL documentation, “pg_stat_statements”, postgresql.org/docs/current/pgstatstatements.html.

[PG-CREATEINDEX] PostgreSQL documentation, “CREATE INDEX”, postgresql.org/docs/current/sql-createindex.html.

[RFC0001] Saksham, “Observability, My Dear Watson”, blogs.saksh.fyi.