Nested Loop, Hash Join, Merge Join, Memoize, Sort, Hash Aggregate, and Incremental Sort

Learning outcomes

Once rows are found, executor nodes must join, sort, aggregate, and sometimes cache intermediate results. ServiceHub sees a hash join spill to batches during one report, a nested loop become disastrous after a cardinality underestimate, and a Memoize node that looks like an undocumented cache. The cure is to connect each node to its input row counts, ordering, parameterization, and memory budget.

1. Build join and executor datasets

DROP TABLE IF EXISTS app.ch11_events;DROP TABLE IF EXISTS app.ch11_technicians;DROP TABLE IF EXISTS app.ch11_regions;CREATE TABLE app.ch11_regions (    region_id integer PRIMARY KEY,    region_name text NOT NULL);INSERT INTO app.ch11_regionsVALUES (1,'north'),(2,'south'),(3,'east'),(4,'west');CREATE TABLE app.ch11_technicians (    technician_id integer PRIMARY KEY,    region_id integer NOT NULL REFERENCES app.ch11_regions,    skill text NOT NULL);INSERT INTO app.ch11_techniciansSELECT g, 1 + (g % 4), 'skill-' || (g % 20)FROM generate_series(1,2000) AS g;CREATE TABLE app.ch11_events (    event_id bigint PRIMARY KEY,    technician_id integer NOT NULL REFERENCES app.ch11_technicians,    tenant_id integer NOT NULL,    event_type text NOT NULL,    occurred_at timestamptz NOT NULL,    duration_ms integer NOT NULL,    payload text NOT NULL);INSERT INTO app.ch11_eventsSELECT g,       1 + (g % 2000),       1 + (g % 80),       CASE g % 4 WHEN 0 THEN 'open' WHEN 1 THEN 'assign' WHEN 2 THEN 'complete' ELSE 'note' END,       timestamptz '2026-01-01 00:00+00' + g * interval '2 seconds',       5 + (g % 5000),       repeat(md5(g::text), 3)FROM generate_series(1,420000) AS g;CREATE INDEX ch11_events_tech_time_idxON app.ch11_events (technician_id, occurred_at DESC);CREATE INDEX ch11_events_tenant_type_idxON app.ch11_events (tenant_id, event_type);CREATE INDEX ch11_technicians_region_skill_idxON app.ch11_technicians (region_id, skill);ANALYZE app.ch11_regions;ANALYZE app.ch11_technicians;ANALYZE app.ch11_events;

2. Nested loop: repeated inner work can be excellent or terrible

Nested loop takes each row from an outer input and evaluates an inner plan. It is powerful when the outer side is small and the inner side has a cheap parameterized lookup. The same structure can explode when the outer cardinality is much larger than estimated.

EXPLAIN (ANALYZE, BUFFERS, TIMING OFF)SELECT t.technician_id, e.event_id, e.occurred_atFROM app.ch11_technicians tJOIN app.ch11_events e  ON e.technician_id = t.technician_idWHERE t.region_id = 2  AND t.skill = 'skill-7'  AND e.occurred_at >= timestamptz '2026-01-08 00:00+00'ORDER BY t.technician_id, e.occurred_at DESC;

If nested loop appears, inspect loops on the inner node. An index scan repeated 25 times may be ideal. The same scan repeated 100,000 times after a bad outer estimate may dominate runtime.

3. Memoize: cache repeated parameter values inside nested loops

Memoize caches results of parameterized inner scans. It is useful when the outer side repeats the same parameter values. PostgreSQL can then skip rescanning the underlying inner plan for cache hits. Entries can be evicted when the cache needs space.

EXPLAIN (ANALYZE, BUFFERS, SETTINGS, TIMING OFF)SELECT e.event_id, t.skillFROM app.ch11_events eJOIN app.ch11_technicians t  ON t.technician_id = e.technician_idWHERE e.tenant_id BETWEEN 10 AND 14  AND e.event_type = 'complete';

If a Memoize node is selected, read Cache Key, hits, misses, evictions, overflows, and memory usage. If it is not selected, do not force it just to match the lesson—the cost model may prefer a hash join for your local cardinality.

BEGIN;SET LOCAL enable_memoize = off;EXPLAIN (ANALYZE, BUFFERS, SETTINGS, TIMING OFF)SELECT e.event_id, t.skillFROM app.ch11_events eJOIN app.ch11_technicians t  ON t.technician_id = e.technician_idWHERE e.tenant_id BETWEEN 10 AND 14  AND e.event_type = 'complete';ROLLBACK;

4. Hash join: build a hash table, then probe it

A hash join usually hashes the smaller eligible input on equality join keys, then probes it with rows from the other input. It does not require pre-sorted inputs. Memory pressure can split the hash into multiple batches; more than one batch is a signal that the operation exceeded the in-memory budget and used additional work.

EXPLAIN (ANALYZE, BUFFERS, SETTINGS, TIMING OFF)SELECT r.region_name, count(*), sum(e.duration_ms)FROM app.ch11_events eJOIN app.ch11_technicians t ON t.technician_id = e.technician_idJOIN app.ch11_regions r ON r.region_id = t.region_idGROUP BY r.region_nameORDER BY r.region_name;

BEGIN;SET LOCAL work_mem = '128kB';SET LOCAL hash_mem_multiplier = 1.0;EXPLAIN (ANALYZE, BUFFERS, SETTINGS, TIMING OFF)SELECT count(*)FROM app.ch11_events e1JOIN app.ch11_events e2  ON e2.technician_id = e1.technician_idWHERE e1.event_id BETWEEN 1 AND 50000  AND e2.event_id BETWEEN 200000 AND 300000;ROLLBACK;

Inspect Batches on the Hash node. A value greater than one indicates batching. Do not respond by globally raising work_mem; Chapter 02 already established that many simultaneous sort/hash operations across many sessions can multiply memory demand.

5. Merge join: exploit sorted inputs

A merge join walks two inputs ordered by compatible join keys. Ordering may come from indexes or explicit Sort nodes. It can be attractive for large ordered inputs, but sorting itself has startup cost and memory/disk implications.

BEGIN;SET LOCAL enable_hashjoin = off;SET LOCAL enable_nestloop = off;EXPLAIN (ANALYZE, BUFFERS, SETTINGS, TIMING OFF)SELECT count(*)FROM app.ch11_events eJOIN app.ch11_technicians t  ON t.technician_id = e.technician_idWHERE e.event_id BETWEEN 1 AND 200000;ROLLBACK;

The enable flags mostly discourage node types; they are not a plan-hinting API and some node types cannot be completely suppressed. This forced comparison is useful to understand alternative cost, not to “fix” production by banning hash or nested-loop joins.

6. Sort and incremental sort

A full Sort must order its complete input before returning rows, unless another optimization changes the requirement. Incremental Sort can exploit a prefix that is already ordered and sort only within groups for the remaining keys. This can reduce startup cost and memory for some workloads, especially with LIMIT, but incurs group-management overhead.

CREATE INDEX ch11_events_tenant_only_idxON app.ch11_events (tenant_id);ANALYZE app.ch11_events;EXPLAIN (ANALYZE, BUFFERS, TIMING OFF)SELECT tenant_id, event_type, occurred_at, event_idFROM app.ch11_eventsORDER BY tenant_id, event_type, occurred_at DESCLIMIT 5000;

If the planner uses the index for the tenant_id prefix, Incremental Sort becomes plausible, showing a presorted key. PostgreSQL 18 can also report richer memory/disk details for executor nodes. If a full Sort is cheaper locally, accept that evidence.

BEGIN;SET LOCAL work_mem = '128kB';EXPLAIN (ANALYZE, BUFFERS, SETTINGS, TIMING OFF)SELECT event_type, occurred_at, payloadFROM app.ch11_eventsORDER BY payload, occurred_at;ROLLBACK;

Inspect Sort Method. An external merge or nonzero disk usage means the sort spilled. That may be acceptable for an occasional report; tuning depends on concurrency and workload value.

7. Hash aggregate versus sorted aggregation

EXPLAIN (ANALYZE, BUFFERS, TIMING OFF)SELECT tenant_id, event_type,       count(*) AS events,       avg(duration_ms) AS avg_durationFROM app.ch11_eventsGROUP BY tenant_id, event_type;

HashAggregate stores groups in a hash table and can spill/batch under memory pressure. A sorted/group aggregate can consume ordered groups instead. The best strategy depends on estimated groups, input ordering, tuple width, memory, and parallel opportunities.

BEGIN;SET LOCAL enable_hashagg = off;EXPLAIN (ANALYZE, BUFFERS, SETTINGS, TIMING OFF)SELECT tenant_id, event_type,       count(*) AS events,       avg(duration_ms) AS avg_durationFROM app.ch11_eventsGROUP BY tenant_id, event_type;ROLLBACK;

8. Production judgment and cleanup

When an executor node appears expensive, ask whether its input row count is correct before blaming the node. Then inspect loops, ordering, memory/spill evidence, hash batches, Memoize hit ratio, and buffer activity. A wrong cardinality estimate can select the wrong join algorithm and then amplify work everywhere above it.

DROP TABLE IF EXISTS app.ch11_events;DROP TABLE IF EXISTS app.ch11_technicians;DROP TABLE IF EXISTS app.ch11_regions;

Authoritative references

Planner and executor behavior is version-sensitive and workload-sensitive. Verify the exact PostgreSQL major, statistics state, server settings, indexes, and data distribution before generalizing any plan shown in this lesson.

• PostgreSQL 18 — Using EXPLAIN
• PostgreSQL 18 — Query Planning Configuration
• PostgreSQL 18 — Resource Consumption
• PostgreSQL 18 — Parallel Plans
• PostgreSQL 18 — Release 18 Notes