Why is a hash join preferred when it does not fit in work_mem

Hello list,

I have a very simple NATURAL JOIN that does not fit in the work_mem.  Why
does the query planner prefer a hash join that needs 361s, while with a
sort operation and a merge join it takes only 13s?

The server is an old Mac Mini with hard disk drive and only 4GB RAM.
Postgres version info:

  PostgreSQL 15.0 on x86_64-apple-darwin20.6.0, compiled by Apple clang
version 12.0.0 (clang-1200.0.32.29), 64-bit

The low work_mem and the disabled memoization are set on purpose, in order
to simplify a complex query, while reproducing the same problem that I
experienced there. This result is the simplest query I could get, where
the optimizer does not go for a faster merge join.

From my point of view a merge join is clearly faster, because the hash
table does not fit in memory and I expect a hash join to do a lot of
random I/O. But the query planner does not see that, and increasing
random_page_cost does not help either. In fact the opposite happens: the
merge join gets a higher cost difference to the hash join, as I increase
the random page cost!



# EXPLAIN (ANALYZE,VERBOSE,BUFFERS,SETTINGS) SELECT * FROM
tasks_mm_workitems NATURAL JOIN workitem_ids;

QUERY PLAN

------------------------------------------------------------------------------------------------------------------------------------------------------
  Hash Join  (cost=121222.68..257633.01 rows=3702994 width=241) (actual
time=184498.464..360606.257 rows=3702994 loops=1)
    Output: tasks_mm_workitems.workitem_n, tasks_mm_workitems.task_n,
workitem_ids.workitem_id
    Inner Unique: true
    Hash Cond: (tasks_mm_workitems.workitem_n = workitem_ids.workitem_n)
    Buffers: shared hit=15068 read=47434, temp read=56309 written=56309
    ->  Seq Scan on public.tasks_mm_workitems  (cost=0.00..53488.94
rows=3702994 width=8) (actual time=0.040..1376.084 rows=3702994 loops=1)
          Output: tasks_mm_workitems.workitem_n, tasks_mm_workitems.task_n
          Buffers: shared read=16459
    ->  Hash  (cost=59780.19..59780.19 rows=1373719 width=237) (actual
time=184361.874..184361.875 rows=1373737 loops=1)
          Output: workitem_ids.workitem_id, workitem_ids.workitem_n
          Buckets: 4096  Batches: 512  Memory Usage: 759kB
          Buffers: shared hit=15068 read=30975, temp written=43092
          ->  Seq Scan on public.workitem_ids  (cost=0.00..59780.19
rows=1373719 width=237) (actual time=0.026..1912.312 rows=1373737 loops=1)
                Output: workitem_ids.workitem_id, workitem_ids.workitem_n
                Buffers: shared hit=15068 read=30975
  Settings: effective_cache_size = '500MB', enable_memoize = 'off',
hash_mem_multiplier = '1', max_parallel_workers_per_gather = '1', work_mem
= '1MB'
  Planning:
    Buffers: shared hit=2 read=6
  Planning Time: 0.568 ms
  Execution Time: 361106.876 ms
(20 rows)


# EXPLAIN (ANALYZE,VERBOSE,BUFFERS,SETTINGS) SELECT * FROM
tasks_mm_workitems NATURAL JOIN workitem_ids;

QUERY PLAN

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
  Merge Join  (cost=609453.49..759407.78 rows=3702994 width=241) (actual time=5062.513..10866.313 rows=3702994 loops=1)
    Output: tasks_mm_workitems.workitem_n, tasks_mm_workitems.task_n, workitem_ids.workitem_id
    Merge Cond: (workitem_ids.workitem_n = tasks_mm_workitems.workitem_n)
    Buffers: shared hit=5343 read=66053, temp read=32621 written=32894
    ->  Index Scan using workitem_ids_pkey on public.workitem_ids
(cost=0.43..81815.86 rows=1373719 width=237) (actual time=0.111..1218.363 rows=1373737 loops=1)
          Output: workitem_ids.workitem_n, workitem_ids.workitem_id
          Buffers: shared hit=5310 read=49627
    ->  Materialize  (cost=609372.91..627887.88 rows=3702994 width=8) (actual time=5062.389..7392.640 rows=3702994
loops=1)
          Output: tasks_mm_workitems.workitem_n, tasks_mm_workitems.task_n
          Buffers: shared hit=33 read=16426, temp read=32621 written=32894
          ->  Sort  (cost=609372.91..618630.40 rows=3702994 width=8) (actual time=5062.378..6068.703 rows=3702994
loops=1)
                Output: tasks_mm_workitems.workitem_n, tasks_mm_workitems.task_n
                Sort Key: tasks_mm_workitems.workitem_n
                Sort Method: external merge  Disk: 65256kB
                Buffers: shared hit=33 read=16426, temp read=32621 written=32894
                ->  Seq Scan on public.tasks_mm_workitems
(cost=0.00..53488.94 rows=3702994 width=8) (actual time=0.045..1177.202 rows=3702994 loops=1)
                      Output: tasks_mm_workitems.workitem_n, tasks_mm_workitems.task_n
                      Buffers: shared hit=33 read=16426
  Settings: effective_cache_size = '500MB', enable_hashjoin = 'off', enable_memoize = 'off', hash_mem_multiplier = '1',
max_parallel_workers_per_gather= '1', work_mem = '1MB' 
  Planning:
    Buffers: shared hit=8
  Planning Time: 0.677 ms
  Execution Time: 13364.545 ms
(23 rows)


Thank you in advance,
Dimitris