Table Joins

Nested loop

–

–none

–

Index nested loop

–

–index lookups

–

Hash join

–

–hashes

–

Merge join

–

–sort comparisons

–

Steps

Pseudocode

Bigger tables

Rows in students Rows in departments

Rough count: one comparison or hash ≈ 10 ns, everything in RAM. The hash join assumes about one department per bucket; sorting n rows takes ≈ n log₂ n comparisons.

Which join when?

Nested loop: Works for any join condition (<, >, ≠, LIKE …). Fine when one of the tables is tiny.
Index nested loop: The inner table has an index on the join column (often its primary key). Best when the outer side is small, e.g. after a WHERE filter: a few lookups, nothing to build or sort.
Hash join: The usual choice for equality joins (=) on big, unsorted tables. Needs RAM for a hash table on the smaller table.
Merge join: Best when both inputs already come sorted on the key (an index, or an earlier ORDER BY): then it is a single pass. Its output is sorted too.

Settings

Table sizestudents × departments

Hash bucketsh(k) = k mod B

Legend

Join key
Being compared
Match
Compared, no match
Never compared
No partner: dropped
Bucket searched
Index → row pointer
Joined row

How a database joins two tables

The ideas

A join pairs the rows of two tables that satisfy a condition, here s.dept = d.id. An inner join outputs only the pairs that match, so a student whose department doesn't exist is left out.
The database can compute the same result in different ways. The query planner picks the cheapest one from the table sizes, the indexes and the memory available.
Nested loop: for each row of the outer table, scan the whole inner table. Always n × m comparisons, but it works for any condition.
Index nested loop: the same outer loop, but each row is looked up in an index on the inner table's join column (here the B+ tree of the primary key departments.id): root → one leaf → one row. About log m comparisons per row, so n × log m in all, and the index already exists, so nothing is built per query.
Hash join: build a hash table on the smaller table, then probe it: each row of the other table looks in just one bucket. Roughly n + m work, but only for =, and the hash table needs memory.
Merge join: sort both tables on the key, then move two pointers forward together. The merge itself is at most n + m comparisons; the sorting costs about n log n, nothing if the input is already sorted.

	Work	Condition	Needs
Nested loop	n × m	any	nothing
Index nested loop	n × log m	= (and ranges)	an index on the inner table
Hash join	≈ n + m	=	RAM for the hash table
Merge join	sort + (n + m)	= (and ranges)	sorted input

Simplifications

Everything is in RAM and the scoreboard counts operations. Real databases mostly count disk page reads, e.g. a block nested loop reads the inner table once per block of outer rows.
departments.id is unique, so the merge join never moves backwards. With duplicates on both sides it outputs every pair of the two matching groups.
The index here is a two-level B+ tree with 3 keys per leaf; real ones hold hundreds of keys per page, so even huge tables need only 3–4 levels. The scoreboard counts one "index lookup" per student plus the key comparisons on the way down.
Real hash tables have thousands of buckets. When the hash table doesn't fit in RAM, a Grace hash join first splits both tables into partitions on disk.

Try this

Press Tour for a guided introduction.
Press Compare all: watch the pairs matrix, full for the nested loop, two or three cells per student for the index lookups, sparse for the hash join, a staircase for the merge join.
Set Hash buckets to 2, then to 8: more buckets, fewer comparisons per probe.
Pick 12 × 6 tables and run the nested loop.
Drag the Bigger tables sliders to a million rows, then set students to 100 and departments to 10 million: now the index nested loop wins.

Keyboard

Space	Play / pause
→ ←	Next / previous step
Home End	Start of run / skip to end
R or Enter	Run the join
1 – 4	Nested loop / index nested loop / hash / merge
C	Compare all
D	New random tables
T	Tour
?	This help

Created by