Join Algorithms

The same JOIN can be computed three ways. Run each on the same two tables and count the comparisons it spends.

Nested loop: O(n·m)

Hash: O(n + m)

Sort-merge: O(n log n + m log m)

Algorithm

Animation Speed: 700ms

Step 1 of 0

Click Play to begin.

When Each One Wins

Nested loop

Tiny inputs, join conditions that are not equalities, or an index on the inner table — an index nested-loop join turns each inner scan into one lookup.

Hash join

Equality joins on large, unsorted inputs, when the smaller side fits in memory. The usual winner for analytics.

Sort-merge

Inputs already sorted on the key (from an index or an earlier sort), inputs too big for memory, or when sorted output is wanted next.

The query optimizer picks among these using table statistics — the same cost-based choice shown in How a Database Query Executes.

Knowledge Check

Question 1 of 3

Two tables of 10,000 rows each are joined on an equality condition, with no indexes and plenty of memory. Which join is usually fastest?

DSAverse

Join Algorithms

When Each One Wins

Knowledge Check

See also

Join Algorithms

When Each One Wins

Knowledge Check

See also