Three algorithms, one result, wildly different bills
When you write a JOIN, you do not choose the algorithm — the planner does. And the Nested Loop, Hash Join and Merge Join lines you see in an EXPLAIN plan are usually the whole explanation for why a query took four milliseconds or forty seconds.
Nested loop — n × m
For every row on the left it scans the entire right table. Simple, needs no memory, and on small tables it genuinely is the fastest. The problem is growth: double both sides and the work quadruples.
Now tick R has an index in the simulator and watch the curve change completely. It no longer scans the table per row; it descends the tree. This is why a planner that sees a small left input and an indexed right input picks nested loop — and is right to.
Hash join — n + m, paid for in memory
It builds a hash table from the smaller side in memory, then probes it once per row of the larger side. Comparisons drop from a product to a sum. In the simulator you can watch the two phases run as distinct stages — build fills the memory counter, probe drains the left table.
The cost is sitting in that memory counter. If the hash table does not fit in memory the join spills to disk, and most of the advantage goes with it. That is why work_mem has such an outsized effect on which plan you get.
Sort-merge — who pays for the sort?
It sorts both sides, then walks them together with two pointers. The simulator charges the sort as a single step so the trace stays readable, but the full n·log n lands in the comparison counter — because that is the actual question with merge join: who pays for the sort?
Tick inputs already sorted and it becomes the cheapest of the three. In real queries that free ordering comes from an index scan or from the output of a previous step, and it is usually the reason the planner reaches for merge join at all.
At eight rows, none of this matters
On a toy data set all three finish instantly, and something counter-intuitive shows up: sort-merge is often the most expensive of the three, because the sort dominates when there is almost nothing to sort. That is real, and it is why the planner does not reach for merge join on small inputs.
It is also why the simulator projects to 100,000 × 100,000. Same choices, real table sizes: nested loop does ten billion comparisons, hash join does two hundred thousand — a factor of 50,000. That gap is the entire reason reading a query plan is worth your time.
What to do in practice
The planner usually chooses well. When it does not, the cause is almost always bad statistics — it mis-estimated how many rows a step would produce. So when a query is unexpectedly slow, run EXPLAIN ANALYZE and compare the estimated row count against the actual one. That gap tells you why the wrong algorithm was chosen, and fixing the estimate beats forcing the algorithm by hand almost every time.
