SQL JOINs - What They Are and What Actually Happens

What is an INNER JOIN

An INNER JOIN returns only rows that have a matching value in both tables. If no match is found, the row is excluded.

-- Modern explicit inner join
SELECT p.name AS pet_name, o.full_name AS owner_name
FROM pets AS p
JOIN owners AS o
  ON p.owner_id = o.owner_id;

Old style that is functionally the same as INNER JOIN:

SELECT p.name, o.full_name
FROM pets AS p, owners AS o
WHERE p.owner_id = o.owner_id;

⬆ Back to top

What is a LEFT JOIN

A LEFT JOIN keeps all rows from the left table and matches from the right table. If no match is found on the right side, the right table columns are returned as NULL.

SELECT o.full_name, p.name AS pet_name
FROM owners AS o
LEFT JOIN pets AS p
  ON o.owner_id = p.owner_id;

Read it left to right - keep every owner, and if they have pets show them, otherwise pet columns are NULL.

⬆ Back to top

What actually happens with an INNER JOIN

The optimizer chooses a join algorithm based on table sizes, indexes, and statistics. The three common strategies are below.

1) Nested Loop Join

Concept - for each row in table A, look up matches in table B.
Fast when the inner side has an index on the join key or when A is small.
Naive version is O(n × m). Indexed lookups make it much faster in practice.

for each row a in A
  probe B using a.join_key  -- ideally via index
  output matches

2) Hash Join

Build a hash table in memory from the smaller table on the join key.
Scan the larger table and probe the hash table for matches.
Roughly O(n + m). Good when indexes are missing and data fits memory.

build hash from B on join_key
for each row a in A
  lookup a.join_key in hash
  output matches

3) Merge Join

Both inputs are sorted on the join key - either pre-sorted via index or sorted on the fly.
Walk both lists in order and merge matches.
Linear once sorted. Sorting cost can dominate if no indexes exist.

while i < A and j < B
  if A[i].key == B[j].key  -> output and advance
  else if A[i].key < B[j].key -> i++
  else j++

You can see what your engine chose using EXPLAIN:

EXPLAIN
SELECT p.name, o.full_name
FROM pets AS p
JOIN owners AS o
  ON p.owner_id = o.owner_id;

⬆ Back to top

Mini examples

Tables

pets	owners
`pet_id \| name \| owner_id` 1 \| Luna \| 1 2 \| Rex \| 2 3 \| StrayCat \| NULL	`owner_id \| full_name` 1 \| Kara 2 \| James

INNER JOIN

SELECT p.name, o.full_name
FROM pets p
JOIN owners o ON p.owner_id = o.owner_id;

Result - only matches:

Luna | Kara
Rex  | James

LEFT JOIN

SELECT o.full_name, p.name
FROM owners o
LEFT JOIN pets p ON o.owner_id = p.owner_id;

Result - all owners, pets may be NULL:

Kara  | Luna
James | Rex

If there was an owner with no pets, they would still appear with NULL for the pet name.

⬆ Back to top