Explain the three join algorithms PostgreSQL can choose: nested loop, hash join and merge join. When is each a good fit?

Nested loop: a good fit when the outer side is small. It takes each row of the outer input and looks up matching rows in the inner input, ideally through an index. It works with any join condition. But its cost multiplies with the number of outer rows.

Hash join: a good fit for large, unsorted inputs joined on equality (=). It builds a hash table from the smaller input. Then it checks each row of the other input against that table. The hash table must fit in work_mem. If it does not, PostgreSQL splits it into batches that spill to disk.

Merge join: a good fit for large inputs that are already sorted. It needs both inputs sorted on the join key, either from an index or from an explicit sort. Then it walks through both inputs together, like merging two sorted lists.

The planner chooses based on row estimates. So a bad estimate often produces a slow nested loop. For example, the planner expects 1 row, but there are really 100,000.