Why does the sort method used by Postgres change from "top-N" to "external merge" when FOR UPDATE is added?

Question

I have a table in Postgres (14) that is used like a queue with FOR UPDATE SKIP LOCKED queries. It was missing an index, but since any rows are usually processed quickly that never became a problem. Until it suddenly did, after a surge of new work, which slowed the entire database down. I now added the index and all is good, but I'd like to understand what really happened.

A simplified version of the table looks like this:

CREATE TABLE outgoing(
    id int PRIMARY KEY,
    created_at timestamptz NOT NULL,
    some_data text NOT NULL
);

It is periodically queried like this:

SELECT * 
FROM outgoing
ORDER BY created_at
LIMIT 100
FOR UPDATE SKIP LOCKED;

When I suddenly got around 500,000 rows in the table, the above query started to take about 30 seconds to execute. After some debugging, I've found that it was the sorting that was the culprit. With the FOR UPDATE clause, it would choose Sort Method: external merge. However, if I removed FOR UPDATE from the query, it changed to the much faster and less resource hungry (and also expected) Sort Method: top-N heapsort. Why does the presence of FOR UPDATE change the sort method?

The behaviour can be reproduced with the above table definition and query, plus the following block to add some rows:

do $$
begin
    for i in 1..500000 loop
        insert into outgoing values (i, now() - make_interval(0, 0, 0, 0, 0, i), i::text);
    end loop;
end; $$;

Plan without FOR UPDATE:

EXPLAIN (ANALYZE, BUFFERS) SELECT * 
FROM outgoing
ORDER BY created_at
LIMIT 100;

Limit  (cost=14230.69..14242.36 rows=100 width=18) (actual time=80.188..85.939 rows=100 loops=1)
  Buffers: shared hit=3305 dirtied=1
  ->  Gather Merge  (cost=14230.69..62845.12 rows=416666 width=18) (actual time=80.186..85.929 rows=100 loops=1)
        Workers Planned: 2
        Workers Launched: 2
        Buffers: shared hit=3305 dirtied=1
        ->  Sort  (cost=13230.67..13751.50 rows=208333 width=18) (actual time=25.455..25.459 rows=67 loops=3)
              Sort Key: created_at
              Sort Method: top-N heapsort  Memory: 40kB
              Buffers: shared hit=3305 dirtied=1
              Worker 0:  Sort Method: top-N heapsort  Memory: 40kB
              Worker 1:  Sort Method: quicksort  Memory: 25kB
              ->  Parallel Seq Scan on outgoing  (cost=0.00..5268.33 rows=208333 width=18) (actual time=0.007..7.269 rows=166667 loops=3)
                    Buffers: shared hit=3185 dirtied=1
Planning Time: 0.097 ms
Execution Time: 85.972 ms

Plan with FOR UPDATE:

EXPLAIN (ANALYZE, BUFFERS) SELECT * 
FROM outgoing
ORDER BY created_at
LIMIT 100
FOR UPDATE SKIP LOCKED;

Limit  (cost=27294.64..27295.89 rows=100 width=24) (actual time=163.076..163.107 rows=100 loops=1)
  Buffers: shared hit=3285, temp read=494 written=2441
  ->  LockRows  (cost=27294.64..33544.64 rows=500000 width=24) (actual time=163.075..163.101 rows=100 loops=1)
        Buffers: shared hit=3285, temp read=494 written=2441
        ->  Sort  (cost=27294.64..28544.64 rows=500000 width=24) (actual time=163.053..163.058 rows=100 loops=1)
              Sort Key: created_at
              Sort Method: external merge  Disk: 19432kB
              Buffers: shared hit=3185, temp read=494 written=2441
              ->  Seq Scan on outgoing  (cost=0.00..8185.00 rows=500000 width=24) (actual time=0.010..29.042 rows=500000 loops=1)
                    Buffers: shared hit=3185
Planning Time: 0.073 ms
Execution Time: 166.365 ms

Answer 1

The reason for the difference is that data modifying queries cannot use parallel query (locking rows modifies the data). With two parallel workers, each process only has to sort a third of the rows, which can be done using the available memory, as configured with work_mem. Without parallel query, work_mem is not sufficient, and the sort has to spill to disk.

The solution is to increase work_mem.