Indexes & Query Performance

Join, Sort, and Aggregation Algorithms

Physical operators trade startup, ordering, memory, repeated lookup, and spill behavior. Nested loop, hash, and merge joins—and hash versus sort/stream aggregation—are alternatives selected from input size, predicates, order, indexes, memory, and estimates.

Nested loop repeats inner work.
Hash join targets equijoins.
Merge join consumes compatible order.
Sort is blocking but reusable.
Hash aggregation stores groups.
Memory is per active operator/worker.

Algorithm comparison
Operator	Input requirement	Strength	Failure mode
Nested loop	Any join; efficient inner access helps	Low startup for tiny outer input	Repeated inner work
Hash join	Hashable equality	Linear-style build/probe when fit	Skew, batches, disk spill
Merge join	Merge-compatible equality/order	Streaming through sorted inputs	Sort cost and duplicate groups
Hash aggregate	Hashable group keys	No pre-sort	Too many/wide groups spill
Sort/stream aggregate	Grouped order	Small streaming state after order	Sort startup/spill if order absent

Same join, three physical shapes

Inspect memory and spill evidence

EXPLAIN (ANALYZE, BUFFERS)
SELECT o.customer_id, pc.category_id, sum(i.quantity * i.unit_price) AS revenue
FROM orders o
JOIN order_items i USING (order_id)
JOIN product_categories pc USING (product_id)
WHERE o.placed_at >= :from_time
GROUP BY o.customer_id, pc.category_id;
-- Look for loops, Sort Method/Disk, hash Buckets/Batches/Memory Usage, and temp I/O.

“Small build side” means the side’s actual filtered width and rows, not its base-table size. Projection and early filters matter. A cardinality miss can reverse the intended build/probe economics and cause an unexpected multi-batch hash.