What's the difference between a nested loop join and a hash join?

A nested loop join takes one row from the outer table, hunts through the inner table for matches, emits them, and moves to the next row. A hash join reads one table to the end, arranges it in memory so any value can be found immediately, then reads the other table once, probing that structure as it goes. Both return the same rows. The difference is entirely in how the cost grows, and it is not a small difference: on one pair of tables the first method can be three hundred times slower than the second, and on another pair it is forty times faster.

Here $n$ is the number of rows on the outer side, the one being walked, $d$ is the cost of one descent into the inner side's index, $m$ is the matches found per outer row, and $g$ is the cost of fetching each match. Put numbers in it. Twelve outer rows at four page reads per descent, with two matches each at one page read per fetch, is $12 \times (4 + 2) = 72$ page reads. Nothing about that is slow. Raise the outer side to two million rows and keep everything else identical: $2{,}000{,}000 \times 6 = 12{,}000{,}000$ page reads, each one a scattered seek rather than a sequential run. If the inner side has no usable index, $d$ stops being four pages and becomes a full scan of the whole inner table, which is the single worst thing you can ask a database to do.

Now the same join done the other way, at a scale where it matters: one million rows joined to two hundred thousand, with an index on the inner side and a hundred rows to a page. The nested loop costs $1{,}000{,}000 \times 4 = 4{,}000{,}000$ page reads, scattered. The hash join reads $200{,}000 \div 100 = 2{,}000$ pages to build its structure and $1{,}000{,}000 \div 100 = 10{,}000$ pages to probe it, so $12{,}000$ page reads, sequential. The ratio is $4{,}000{,}000 \div 12{,}000 = 333$. Same query, same answer, and no amount of tuning closes a gap of that shape.

A hash join needs an equality on the joining column, because it works by turning a value into an address. A predicate like a range or a not-equal cannot be probed, so for those the nested loop is the only one of the two available, and it is excellent if an index can answer the predicate. The nested loop's limit is on the other axis: it is proportional to the outer side, so it stops being viable the moment the outer side reaches the thousands, which is why it is so often the wrong choice in a plan produced by a bad estimate of how small the small side really is. And if both sides happen to arrive already sorted on the joining column, from an index or from an earlier step, walking them together in one pass beats both of these, since it needs no memory and no per-row lookup at all.