Join Algorithms

In Module 5 you learned what a join means. You never learned how the database actually performs one.

There are three ways, and knowing which is running explains most join-related slowness.

Why & what

"Match rows in A against rows in B" is a description, not a method. Compare every row against every row and a join of two 10,000-row tables is 100 million comparisons.

So databases have three strategies, and the optimiser picks one.

Nested loop scans B for every row of A. Hash join builds a lookup table from A and probes it with B. Merge join sorts both sides and walks them together.

How it works

Joining Student to Enrollment on roll_no.

1. Nested loop. Take Aisha, scan all of Enrollment for roll 101. Take Ben, scan again. Simple, and the cost is roughly A × B — brutal on big tables. But if Enrollment.roll_no is indexed, each "scan" becomes an index lookup and it's suddenly excellent.
2. Hash join. Read Student once and build an in-memory lookup keyed on roll_no. Then read Enrollment once, and for each row look up its match instantly. Cost is roughly A + B dramatically better. Only works for equality joins, because hashing gives no ordering.
3. Merge join. Sort both sides by roll_no, then walk the two sorted lists together like merging two decks of cards. Cost is sort + A + B — and if both sides are already sorted (say, both have indexes on the join column), the sort is free and this wins.
4. Who chooses? The optimiser, based on table sizes, available indexes and memory. You don't pick this — which is itself the point of the topic.
5. What you can influence. Add an index on the join column, and nested loop stops being catastrophic while merge join becomes cheap. Almost all join tuning is really index tuning.

Notice: the optimiser picks one for you — it is not a setting you choose.

Common confusion

Candidates assume nested loop is always the bad one. It isn't. With an index on the inner table, nested loop is often the fastest choice — especially when the outer table is small. It's only terrible when both sides are big and unindexed.

Second: hash join needs memory to hold the lookup table. If it doesn't fit, the database spills to disk and performance drops sharply — one reason the same query can be fast on one server and slow on another.

Interview angle

1. "Name the join algorithms and when each is used." — Nested loop for small or indexed inners, hash join for big equality joins, merge join for already-sorted inputs.
2. "Why can't a hash join do a range join?" — Hashing destroys ordering, so < and BETWEEN can't be answered from a hash table.
3. "How do you make a join faster?" — Index the join columns, reduce rows before joining with a WHERE, and check EXPLAIN to see which algorithm was picked.

Recap

Nested loop rescans the inner side per row (great when indexed), hash join builds a lookup for equality joins, merge join walks two sorted inputs — and the optimiser chooses, not you.