Join Algorithms
Databases join with nested loops, hash joins, or merge joins; each has distinct memory, sort, and streaming properties that decide which wins at a given data size and index state.
Definition
Join algorithms are the executor strategies for combining two inputs. Nested loop iterates one input per row of the other and exploits indexes; hash join builds an in-memory or spilled hash table on the smaller input and probes with the other; merge join merges two sorted inputs in one pass. Optimizers pick based on cardinality estimates, indexes, and memory.
Context and scope
Explains why the same query flips plans as data grows, why missing statistics cause nested-loop disasters on large tables, and why OLAP favors hash joins over index lookups.
Common misconceptions
- Nested loops are always bad — with an index on the inner side and a small outer side, they are the fastest plan
- Hash joins need indexes — they need none; that is exactly why the optimizer prefers them for unindexed analytics
- Merge joins require equality only — they require sortable inputs on the join keys and an equality predicate
Anti-patterns
- Missing optimizer statistics on a growing table and silently flipping a hash plan into a nested-loop full scan
- Adding indexes everywhere instead of fixing stale statistics and cardinality estimates
- Assuming a spilled hash join degrades linearly when it can drop an order of magnitude on cold temp space
Related concepts
Related examples
Authoritative source
https://dev.mysql.com/doc/refman/8.0/en/nested-loop-joins.html
What it is
Every join plan is one of three physical strategies. Nested loops multiply outer rows by inner lookups — excellent when the inner is indexed and the outer is small. Hash joins partition one input into a probe table — excellent for large unindexed inputs. Merge joins walk two sorted streams — excellent when inputs arrive sorted by the join key.
How it works
The optimizer estimates cardinalities and costs each strategy. Wrong row estimates produce wrong join orders and wrong algorithms: an underestimated outer size turns an index nested loop into billions of lookups. Hash joins spill to temp space when memory is short, and work_mem or join_buffer_size control that budget.
When to care
Plan flips are the top cause of sudden query regressions after data growth or major version upgrades. Keep statistics fresh, inspect EXPLAIN output for estimated versus actual rows, and pin plans only with documented cause.
Pitfalls
An index does not guarantee a nested loop is cheap: random lookups on a cold buffer pool can lose to one hash pass. Spilled hash joins and external sorts punish slow temp storage disproportionately. Batch mode and vectorization change these economics again in analytical engines.