Query processing

Join methods

PostgreSQL joins two inputs in one of three ways: look up matches for each outer row (nested loop), build a hash table from one side (hash join), or walk two sorted inputs side by side (merge join).

In plain words

A join matches rows of two tables, say orders and customers. PostgreSQL has three ways to do it, and the planner picks by estimated cost:

Nested loop: for every order, look up its customer. Perfect when there are only a few orders and an index on customers; terrible when both sides are big and there is no index.
Hash join: first put all customers into an in-memory lookup table (a hash table), then stream the orders through it. Great for large, unsorted inputs, as long as the hash table fits in memory.
Merge join: sort both sides by the join key (or read them in order from an index), then walk down both lists together like a zipper.

Pick a method below and watch how many rows each one touches.

For DBAs and operators

Nested loop

Cost ≈ outer rows × cost of one inner lookup. With an inner index scan (parameterized by the outer row, Index Cond: (id = o.cust)) it is the fastest plan for small outer sides and returns its first row almost immediately (no build or sort phase). Without an index the inner side is rescanned per outer row, usually from a Materialize node, with a Join Filter. Memoize (PostgreSQL 14+) caches inner results for repeated keys. It is also the only method for non-equality joins (a.x < b.y). A classic support case: a row-count misestimate (rows=1 estimated, 50,000 actual) on the outer side turns a nested loop into millions of index probes.

Nested Loop  (cost=0.72..83.38 rows=9 width=22)
  ->  Index Scan using o_pkey on o  (cost=0.43..8.58 rows=9 width=12)
        Index Cond: (id < 10)
  ->  Index Scan using c_pkey on c  (cost=0.29..8.31 rows=1 width=10)
        Index Cond: (id = o.cust)

Hash join

Builds a hash table from the (estimated) smaller input, the Hash node, then probes it with each outer row. Equality joins only. The table may use up to work_mem × hash_mem_multiplier (4MB × 2 by default). If it does not fit, the inner and outer rows are split by hash into batches; all but the first are written to temp files and joined one batch at a time. Batches double at run time if the estimate was wrong. Parallel hash join (Parallel Hash) builds one shared table across workers.

SET work_mem = '1MB';  -- real PostgreSQL 18 output, excerpt
Hash Join (actual rows=2000000.00 loops=1)
  Hash Cond: (o.cust = c.id)
  Buffers: … temp read=6328 written=6328
  ->  Seq Scan on o (actual rows=2000000.00 loops=1)
  ->  Hash (actual rows=100000.00 loops=1)
        Buckets: 65536  Batches: 4  Memory Usage: 1560kB

With the default 4MB the same join shows Buckets: 131072 Batches: 1 Memory Usage: 5213kB. Watch for Batches greater than 1 and for temp files in pg_stat_database.temp_bytes or log_temp_files.

Merge join

Needs both inputs sorted on the key: from an index scan, an explicit Sort, or a lower merge join. It walks both inputs once; duplicates on the outer side are handled by "mark and restore" on the inner side. It shines when both inputs are already ordered and large, and its output is sorted, which can save a later Sort.

Merge Join  (cost=2.72..7743.86 rows=100000 width=22)
  Merge Cond: (c.id = o.id)
  ->  Index Scan using c_pkey on c  (cost=0.29..3148.29 rows=100000 width=10)
  ->  Index Scan using o_pkey on o  (cost=0.43..62758.43 rows=2000000 width=12)

Join order

The planner also chooses the order. It searches exhaustively up to join_collapse_limit / from_collapse_limit (8) items, and switches to the genetic optimizer (GEQO) at geqo_threshold (12) FROM items. The enable_* switches do not forbid a method: since PostgreSQL 18 the planner prefers plans with fewer disabled nodes and falls back to a disabled one only when nothing else works (Disabled: true in EXPLAIN). Use them to test alternatives, not as a fix.

For developers: inside the source

Planning: where join paths come from

joinrels.c: join_search_one_level() and make_join_rel() build join relations level by level for standard_join_search() (allpaths.c), or geqo() (geqo_main.c) at geqo_threshold.
joinpath.c: add_paths_to_joinrel() calls sort_inner_and_outer() (merge join with explicit sorts), match_unsorted_outer() (nested loops, including Memoize via get_memoize_path(), and merge joins on presorted outer input) and hash_inner_and_outer().
Costing in costsize.c is two-phase: initial_cost_nestloop() / _mergejoin() / _hashjoin() give a cheap lower bound that add_path_precheck() uses to drop hopeless paths, then final_cost_*() does the full job. final_cost_hashjoin() still adds disable_cost when the bucket of the inner side's most common value would not fit in hash memory, because equal keys cannot be split into batches.

Execution

nodeNestloop.c: ExecNestLoop() copies the outer values listed in nestParams into executor parameters and calls ExecReScan() on the inner plan for every outer row; that is how the inner index scan becomes parameterized.
nodeHashjoin.c: ExecHashJoinImpl() is a state machine (HJ_BUILD_HASHTABLE → HJ_NEED_NEW_OUTER → HJ_SCAN_BUCKET … HJ_NEED_NEW_BATCH), specialised into ExecHashJoin() and ExecParallelHashJoin(). Batch tuples go to temp BufFiles through ExecHashJoinSaveTuple().
nodeHash.c: MultiExecHash() builds the table; ExecChooseHashTableSize() picks buckets and batches from the estimate; ExecHashTableInsert() calls ExecHashIncreaseNumBatches(), which doubles nbatch when memory runs out. HashJoinTableData is in hashjoin.h, which also documents the Parallel Hash barrier phases (PHJ_BUILD_ELECT … PHJ_BUILD_FREE).
nodeMergejoin.c: ExecMergeJoin() is a state machine from EXEC_MJ_INITIALIZE_OUTER to EXEC_MJ_ENDINNER; duplicate outer keys use ExecMarkPos() / ExecRestrPos() on the inner plan, which therefore must support mark/restore (or get a Material node).
nodeMemoize.c (ExecMemoize()) and nodeMaterial.c (ExecMaterial()) serve repeated inner scans.

Hooks and tests

set_join_pathlist_hook lets an extension add its own join paths (for example a CustomScan), and join_search_hook replaces the join-order search. FDWs push joins down with GetForeignJoinPaths. Regression suites: src/test/regress/sql/join.sql, join_hash.sql (batch growth, parallel hash), memoize.sql, partition_join.sql. While a parallel hash join is running, pg_stat_activity shows IPC waits such as HashBuildHashInner.

Parameters that shape this

enable_nestloop enable_hashjoin enable_mergejoin enable_memoize enable_material work_mem hash_mem_multiplier join_collapse_limit from_collapse_limit geqo_threshold