Nested loop join
Simplest join algorithm: for every row in the outer relation, scan the inner relation and output matches. O(N×M) in general; O(N) if the inner has an index on the join key. Default for OLTP small-data joins.
Powerful with an indexed inner — every outer row generates an index lookup (logarithmic). Catastrophic without an index on large relations: 10k×10k = 100M operations. Classic performance regression: stats skew → the planner picks nested loop thinking the outer has 10 rows, actually 10k → query hangs. Hash join is a safer default on unknown cardinality. PostgreSQL: a Materialize node on top of the inner caches the result if the outer iterates the same values multiple times. OLTP single-row lookups almost always end up as nested loop with a PK index — that's optimal.