Why might my Postgres table be growing?

I've got a table that grows under Postgres 9.1. It's a high-throughput table with lots of inserts and deletes, but it should generally remain between 1-2k in terms of number or records. Auto-vacuum is enabled, and we've run manual vacuums. We've checked for locks and there don't appear be any. Running "vacuum verbose;" says that while there are millions of dead records, but "found 0 removable".

What might I have not thought about?

Run this query:

SELECT * FROM pg_stat_activity ORDER BY xact_start NULLS LAST LIMIT 1;

If you get a row back where xact_start is not null and it's anything more than a few seconds old, that's your culprit. VACUUM cannot remove rows that have transaction_ids greater than or equal to the oldest open transaction in the system (even if it's in a completely different database). If you terminate that transaction and re-run the VACUUM, you should see more than 0 rows removable.

StackExchange Database Administrators Q#29071, answer score: 8