Nested-loop, hash, and merge joins

A naïve nested loop considers each outer row against every inner row, evaluating the join condition on every pair. It supports broad predicate forms but can perform a product of input sizes. An indexed nested loop is a different physical strategy: an outer key drives a lookup into the inner relation, so only candidate matching rows need inspection. This can be excellent for a small outer input and a selective usable index. Index traversal, random access, repeated keys, visibility checks, and the number of returned matches all affect its actual cost.

A row-count underestimate is especially dangerous when it turns a supposedly tiny outer input into thousands of repeated expensive lookups. Conversely, replacing every nested loop with hashing can force a large build and delay useful output for a query needing only a few rows. Establish what the loop rescans and whether it has a parameterized access path. The phrase nested loop alone does not tell you whether the inner operation is a full table scan, a cached small relation, an index probe, or another complex subplan.

For a supported equality condition, a hash join builds a table from one input and probes it with the other. Good hash behavior and an in-memory build can make expected input processing roughly linear, plus output work. Build size is a byte-and-overhead question, not merely a row-count comparison. A narrower larger relation can sometimes be cheaper to build than a smaller wide one. A hash collision requires an equality check, and nonmatching extra join conditions still need evaluation; hashing does not establish SQL equality by itself.

Skew creates two distinct risks. Many rows in one bucket can hurt lookup or partition balance, while a key repeated on both sides genuinely requires a product of matching rows. The second cost is unavoidable output, not just a bad hash function. If the build does not fit its available memory, partitioning and temporary storage can add substantial work. Null handling and outer-join bookkeeping also depend on the requested semantics. Use a complete plan to identify the actual build side and inspect observed batches or spill evidence before calling a hash join cheap.

A merge join advances through inputs ordered compatibly with the join comparison, matching equal key groups. If the order is already available, it can avoid building a hash table or sorting those inputs again. If order must be created, sorting belongs in the comparison. Duplicates can require revisiting or retaining an equal-key group and still emit many pairs. Do not confuse linear movement through sorted keys with a promise of linear total output when a large matching group exists. Collation, comparison semantics, and supported merge conditions determine whether the order is usable.

Use the cache lab to inspect a narrow reuse effect relevant to repeated probes. Reset, set both capacity C=4 and stride s=4, predict twelve hits in the initial sixteen requests, then Play or Step. Separately Reset, set both C=4 and s=1, predict zero initial hits, then Play or Step. The first fixed modulo-sixteen trace cycles over four addresses; the second cycles over sixteen. This is an exact toy LRU trace, not a join, an index, or a processor benchmark. It illustrates why probe locality belongs in a cost argument without selecting the winning SQL algorithm.