Why does searching a PostgreSQL index for recently-deleted value take so long?

Question

Trying to test that a delete query worked as expected, I want to run a simple select query, but the query just hangs and never completes. Looking at pg_stat_activity it looks like the query is running with the wait_event changing between DataFileRead and other states (including NULL, and surprisingly, WalWrite).

The explained query:

explain select *
from public.some_table
where foreign_id = 99
limit 1

Shows the expected query plan:

Limit  (cost=0.58..4.51 rows=1 width=45)
  ->  Index Scan using idx_unique_cols on "some_table"  (cost=0.58..32.04 rows=8 width=45)
        Index Cond: (foreign_id = 99)

idx_unique_cols has this DDL:

CREATE UNIQUE INDEX idx_unique_cols ON public."some_table" USING btree (foreign_id DESC, col1, col2 DESC, foreign_id_2);

The table is fairly large - around 380GB, and I expect around 50 million rows per foreign_id. I was expecting a fairly quick index scan to determine that there are no rows with a foreign_id of 99. But that is clearly not happening and I don't know why the query would take so long.

Questions:

1. Why would this query ever need to wait on a WalWrite event (I'm assuming that this means the select query, for some reason, requires writing to the Write-Ahead Log)
2. Looking at the index, why would it take so long to determine that a value in the index doesn't exist?
3. Running the same query on a foreign_key value that I know is much higher than exists in some_table returns instantly. Why would running the query on a value that is lower than existing values in the table take so long to return?

Answer 1

The only scenario that comes to my mind is that there were lots of rows with foreign_id = 99 deleted recently. In PostgreSQL, DELETE doesn't remove rows from the table (and the index!) immediately, but marks them as invisible. Later, autovacuum will actually remove the deleted entries. If autovacuum hasn't processed the table yet, the following will happen:

• all the deleted entries are still in the index, and PostgreSQL has to fetch the table rows to determine that they are deleted, which can take a long time

• if the table rows are truly dead (nobody can see them any more), PostgreSQL will "kill the index entries" (free the space in the table and mark the entries in table and index as dead), so that subsequent queries can save themselves the effort

There is some more information in this article.

If my theory is correct, running the same query a second time should be much faster, and VACUUM would speed it up even more.