Wait, What?
A SQL join is not one algorithm. It is a decision about which algorithm should combine two relations, in which order, under which memory and data-shape assumptions.
Beginners often learn joins as syntax: write JOIN, state the matching columns, receive rows. Database engines have a harder problem. They must decide whether to scan repeatedly, build a hash table, sort and merge, use an index, spill to storage, parallelise, and—when many tables are involved—choose a join order from a rapidly growing plan space.
That makes join processing a beautiful algorithm-learning topic. It connects loops, hashing, sorting, memory hierarchy, cost models, estimation and optimisation without requiring the learner to memorise one universal winner.
Quick Answer
Learn database join algorithms through the route relational matching → nested loops → indexed nested loops → hash joins → build/probe roles → merge joins → sorting cost → memory pressure and spilling → join selectivity → cardinality estimation → join trees → dynamic-programming search → heuristic search → parallel joins → adaptive execution → professional plan diagnosis. A beginner should be able to hand-trace a two-table join. A professional should be able to explain why the optimizer selected a particular physical join, what assumptions made that plan attractive, and how wrong estimates or memory limits can change the outcome.
1. Separate the Logical Join From the Physical Algorithm
A logical join says which rows belong together. A physical join algorithm says how the engine will actually find those pairs. The same SQL query may therefore have several correct physical implementations.
This distinction is the first invariant to learn: same relational result, different execution strategy.
2. Start With the Smallest Possible Join
Take two tiny tables. One contains students; the other contains class enrolments. Write the matching key on each row and manually produce the result. Before optimising anything, the learner needs a precise model of what counts as a match, what duplicates do and what happens when one side has no partner.
3. Nested-Loop Join Is the Direct Algorithm
The simplest physical strategy is: for every row on the outer side, scan the inner side and test the join condition. If the outer relation has m rows and the inner relation has n rows, the naïve comparison count is on the order of mn.
PostgreSQL documents nested-loop, merge and hash joins as core physical strategies. See PostgreSQL Planner/Optimizer.
4. Indexed Nested Loops Change the Inner Search
A nested loop does not have to scan the entire inner table. If the join key is indexed, each outer row can perform an index lookup into the inner relation. That can make nested loops excellent when the outer side is small or highly selective.
This is why “nested loops are slow” is a poor rule. The relevant question is what the inner access path costs for the actual number of outer rows.
5. Hash Join Turns Equality Matching Into Lookup
For an equality join, a hash join typically builds a hash table from one input, keyed by the join attribute, then probes it with rows from the other input. The algorithm trades extra memory for fast expected lookup.
The existing How to Learn Hash Tables article owns generic hashing. Join processing adds a systems decision: which side to build, how large the table becomes, how duplicates are represented, and what to do when the build no longer fits memory.
6. Build Side and Probe Side Matter
Building the hash table on the smaller input usually reduces memory and build work. But “smaller” means smaller after filters and projections, not merely smaller on disk. Optimizers therefore depend on cardinality estimates.
7. Hash Collisions Do Not Make the Join Incorrect
A collision means two keys map to the same bucket. Correct implementations still compare the actual join keys before emitting a match. Collisions affect performance, not relational correctness.
8. Memory Pressure Changes the Hash-Join Algorithm
If the build side does not fit memory, the engine may partition data and process partitions in stages, or spill temporary data to storage. The performance profile can change sharply once an in-memory assumption stops being true.
Recent DuckDB work revisits this exact larger-than-memory problem with adaptive external hash-join techniques: Saving Private Hash Join.
9. Merge Join Exploits Order
If both inputs are ordered on the join key, a merge join can advance through them together, much like merging two sorted lists. The key idea is monotonic progress: once one side has moved beyond a key, earlier keys do not need to be reconsidered.
10. Sorting May Be the Hidden Price of Merge Join
Merge join is attractive when inputs already arrive in suitable order from indexes or previous operators. If both sides must first be sorted, the sort cost can dominate. The existing How to Learn Sorting Algorithms article owns sorting fundamentals; database joins add external-memory, tuple-width and pipeline considerations.
11. Join Type Constrains the Algorithm
Inner, left outer, right outer, full outer, semi and anti joins require different output behaviour. An implementation must preserve unmatched rows where the logical semantics require them. Physical speed never overrides relational correctness.
12. Selectivity Is the Fraction of Data That Survives
A predicate that keeps 1% of rows can radically change the best join plan compared with one that keeps 90%. Join algorithms therefore cannot be chosen sensibly without considering filters and expected result sizes.
13. Cardinality Estimation Is the Optimizer’s Forecast
The optimizer estimates how many rows each intermediate operator will produce. Those estimates influence build-side choice, memory expectations, join ordering and access paths.
A professional learns to ask not only “what plan ran?” but also “what row counts did the optimizer expect?”
14. Wrong Estimates Can Make a Good Algorithm Look Bad
Hash join may be excellent for a small build input but painful if that input is unexpectedly huge. Indexed nested loops may be excellent for ten outer rows and disastrous for ten million. The algorithm can be correct and well implemented while the plan choice is still poor.
15. With Three Tables, Join Order Becomes an Algorithmic Problem
For tables A, B and C, joining A with B first can produce a very different intermediate size from joining B with C first. As the number of relations grows, the number of possible join trees grows rapidly.
16. Join Trees Describe the Order of Combination
A left-deep tree repeatedly joins the current result with one new relation. Bushy trees allow subjoins to be computed independently and then combined. Different shapes expose different opportunities for parallelism, pipelining and intermediate-result reduction.
17. Dynamic Programming Can Search the Join-Order Space
Classic optimizers reuse the best known plan for subsets of relations rather than recomputing every possibility independently. This is a dynamic-programming idea applied to query planning.
But the state space still grows rapidly, which motivates pruning and heuristics for large queries.
18. PostgreSQL Uses Heuristic Search for Very Large Join Problems
PostgreSQL includes a Genetic Query Optimizer for sufficiently large join queries because near-exhaustive planning can become too expensive. See PostgreSQL Genetic Query Optimizer.
This teaches an important professional lesson: even the optimizer needs an optimizer. Planning time is part of the total system cost.
19. Cost Models Convert Hardware and Data Into Comparable Plans
Optimizers assign estimated costs to scans, random I/O, sequential I/O, CPU comparisons, hashing, sorting and other operations. The model is an approximation, but it creates a common scale for comparing otherwise different algorithms.
20. Parallel Joins Change the Bottleneck
Partitioning input across workers can accelerate build, probe or merge work, but introduces coordination, memory-bandwidth and skew concerns. Adding workers does not guarantee linear speedup.
The existing How to Learn Parallel Algorithms article owns work/span reasoning. Database joins supply a concrete production workload where shared memory, partitioning and skew make the ideal model messy.
21. Data Skew Can Defeat Evenly Partitioned Plans
If one join key appears far more often than others, one hash bucket or one worker can receive disproportionate work. Average distribution can therefore hide a severe tail bottleneck.
22. Adaptive Execution Uses Runtime Evidence
Static plans are chosen before full execution. Adaptive systems can use observed cardinalities, memory pressure or runtime statistics to change strategy. Current research continues to explore robust and adaptive join ordering, including recent DuckDB work on alternative join orders and runtime routing: POLAR.
23. Modern Analytical Engines Push Beyond the Textbook Three
Vectorised execution, radix partitioning, factorisation, worst-case-optimal joins, SIMD-aware hash tables and adaptive spilling all extend the familiar nested-loop/hash/merge foundation. The fundamentals remain valuable because these systems still manipulate the same core constraints: data size, order, equality structure, memory and intermediate-result growth.
For a current systems-level bridge, see DuckDB’s work on adaptive factorization and worst-case-optimal joins.
24. Common Learning Failure States
- Thinking SQL syntax determines one fixed physical join algorithm.
- Calling nested loops “bad” without considering indexes and outer-side size.
- Calling hash join “linear” without considering build size, collisions, spilling and output size.
- Ignoring the cost of sorting before a merge join.
- Choosing algorithms from base-table size while ignoring filters.
- Ignoring duplicate join keys and output multiplicity.
- Assuming the optimizer knows exact cardinalities.
- Changing join methods without examining row-count estimates.
- Comparing execution time without accounting for cache warmth and memory limits.
- Optimising a two-table join while missing the larger join-order problem.
25. A Beginner-to-Professional Learning Ladder
- Level 1: manually join two tiny tables and explain every output row.
- Level 2: trace a naïve nested-loop join.
- Level 3: replace the inner scan with an index lookup and compare work.
- Level 4: build and probe a small hash join by hand.
- Level 5: merge two pre-sorted relations and identify monotonic progress.
- Level 6: compare the three strategies under different table sizes and selectivities.
- Level 7: explain a query plan using estimated and actual row counts.
- Level 8: design join orders for three to six relations.
- Level 9: reason about spilling, parallelism and skew.
- Level 10: diagnose a production plan using cardinality estimates, memory, I/O, CPU and end-to-end latency evidence.
26. Teach the Physical Algorithm Before the Optimizer
Give learners two printed relations and ask them to execute the join in three ways: repeated scan, hash lookup and sorted merge. Only after they can trace each procedure should they be asked to predict which one an optimizer might choose.
This prediction-first sequence aligns well with PRIMM’s Predict–Run–Investigate–Modify–Make approach: Using PRIMM to teach programming.
27. Fade Worked Plans Into Independent Diagnosis
Start with an annotated plan showing build side, estimated rows, actual rows, sort keys and memory use. On the next example, remove some annotations. Eventually ask the learner to reconstruct the reasoning from the plan alone.
Faded worked examples with metacognitive scaffolding have shown benefits in novice programming problem solving: Shin et al. (2023).
28. Immediate, Delayed and Transfer Checks
- Immediate: trace one nested-loop, hash and merge join on small data.
- Counterexample: construct a case where a nested loop beats a hash join.
- Estimate: predict intermediate row counts before viewing the plan.
- Delayed: explain why build-side size and selectivity matter without notes.
- Transfer: choose a join strategy for an indexed point lookup, a large equi-join and a pre-sorted reporting query.
- Professional: explain a plan regression using estimates, memory pressure, join order and runtime evidence together.
Use spaced and interleaved retrieval so learners repeatedly distinguish join strategies under changing data shapes rather than memorising one example. See A Spaced, Interleaved Retrieval Practice Tool.
29. AI Assistance Boundary
AI can generate toy relations, explain query plans, propose counterexamples and compare candidate join strategies. The learner should still be able to trace the physical algorithm, state the relevant assumptions, identify a suspicious cardinality estimate and verify claims against an actual execution plan.
Professional Direction
Advanced study includes Grace and hybrid hash joins, radix joins, cache-conscious hash tables, vectorised execution, bloom-filter pushdown, semi-join reduction, worst-case-optimal joins, factorised execution, distributed shuffles, broadcast joins, skew handling, adaptive query processing, learned cardinality estimation, robust join ordering and memory-aware spilling. Carnegie Mellon’s Database Systems course provides a strong systems map spanning storage, indexes, joins, optimisation and parallel execution: CMU 15-445 Database Systems.
Algorithm-learning rule: when a join is slow, do not ask only which join method ran. Ask how many rows entered it, how many were expected, which side was built or sorted, what memory was available, what intermediate result was created and why the optimizer believed this plan was cheaper than its alternatives.
eduKate Sengkang 