LEFT JOIN and NULL Padding

Add LEFT [OUTER] JOIN, which keeps every left row and pads it with NULLs when no right row pairs with it, and place conditions so that none of them removes a row the join must keep.

Not run yet · 10 tests

Why this stage exists

"Every user with their orders" sounds like the join of the last stage, until you notice that it silently drops every user who has no orders. Often those are exactly the rows you want: customers who never bought, products never sold, tasks with no assignee. An inner join cannot show what is missing.

A LEFT JOIN can. It keeps every row of its left side. When nothing on the right pairs with a left row, the row still comes out once, with NULL in every right-side column. Those are padded rows.

It comes this early because every join algorithm in the rest of this part must support it, and because it is the first place where where you test a condition changes the answer.

Padding

droid session

>select u.name, o.id from users u left join orders o on u.id = o.user_id order by u.id, o.id;
name | id
ada | 10
ada | 12
bob | 11
cy | NULL
(4 rows)
[EXEC] rows_examined=15

cy has no order, so the join pads her: one row, NULL in every orders column.

As a nested loop, padding is one flag per left row: did any pair come out? When the right side ends and none did, hand up the padded row. It comes in left order, where that row's pairs would have been.

ON and WHERE part ways

For an inner join, a test in ON and the same test in WHERE gave the same rows. Not any more. ON decides which right rows pair; WHERE filters the joined rows, and it sees padded rows like any other.

Query over `users u left join orders o`	cy, who has no order
`on u.id = o.user_id and o.total > 5`	kept, padded: the test only chose which orders pair
`on u.id = o.user_id where o.total > 5`	dropped: her padded `o.total` is NULL, so the WHERE is unknown
`on u.id = o.user_id and u.id > 1`	kept, padded, and so is ada: no order may pair with user 1
`on u.id = o.user_id where o.id is null`	the only row left: the users with no order

The last line is a classic, the anti-join: "rows of A with no match in B".

The third line is the subtle one. u.id > 1 reads only users, and the last stage sent such tests down to the users scan. Here that would be wrong: ada would vanish instead of being padded. So a left-side test inside a LEFT JOIN's ON stays in the join's condition. A right-side test in ON can still go down to the right scan, because it only decides which orders are candidates. A WHERE test on the right side must stay above the join, where it sees the padding.

... on u.id = o.user_id and u.id > 1 and o.total > 5 where o.id is null

Filter (o.id IS NULL)

NestedLoopJoin (left, on: (u.id = o.user_id) AND (u.id > 1))

SeqScan (table=users, alias=u)

Filter (o.total > 5)

SeqScan (table=orders, alias=o)

The right-side ON test goes down; the left-side ON test stays in the join; the WHERE stays above it.

Counting over padding

count(*) counts rows, and a padded row is a row. count(o.id) counts values that are not NULL, and a padded o.id is NULL. So per user, cy gets count(o.id) = 0 and count(*) = 1. To count orders per user including the users with none, count a right-side column.

The algorithm in words

Placing conditions around a LEFT JOIN

Nothing may remove a left row the join must keep.

1.An ON conjunct that reads only the right entry goes down to the right scan: it only decides which right rows can pair.
2.Every other ON conjunct stays in the join's condition, including one that reads only the left side.
3.A WHERE conjunct that reads the right entry stays above the LEFT JOIN: at the lowest join above it that has all its entries, or in a Filter right above the LEFT JOIN.
4.A WHERE conjunct that reads only entries on its left goes down as before.

Running a left nested loop

The inner join, plus one padded row per unmatched left row.

1.For each left row, run the right child as a nested loop does, and remember whether any pair was handed up.
2.When the right child ends and nothing was handed up for this left row, hand up the left row with NULL in every column of the right side.

Output contract for this stage

These are the exact lines the tests check. The full definition is on the output contract page, section 68.

Input	Output
`select u.name, o.id from users u left join orders o on u.id = o.user_id order by u.id, o.id;`	`ada \| 10`, `ada \| 12`, `bob \| 11`, `cy \| NULL`
`select * ... left join ... where u.id = 3;`	`3 \| cy \| NULL \| NULL \| NULL`
`explain` of a LEFT JOIN	`NestedLoopJoin (left, on: ...)`
`explain logical` of a LEFT JOIN	`Join (left, on: ...)`

What you should see when done

shell

$droid --db left.db
Welcome to droid!
>create table users (id int primary key, name varchar(20));
Create table statement executed successfully
>create table orders (id int primary key, user_id int);
Create table statement executed successfully
>insert into users (id, name) values (1, 'ada');
Insert statement executed successfully (1 rows)
>insert into users (id, name) values (2, 'cy');
Insert statement executed successfully (1 rows)
>insert into orders (id, user_id) values (10, 1);
Insert statement executed successfully (1 rows)
>select u.name, o.id from users u left join orders o on u.id = o.user_id;
name | id
ada | 10
cy | NULL
(2 rows)
[EXEC] rows_examined=4
>.exit
exiting.. good bye!

Common bugs in this stage

Padding a left row that did pair. Only a row with no pair at all is padded, once.
Pushing a left-side ON test below the join. The rows it rejects must still come out, padded.
Pushing a right-side WHERE test below the join. It must see the padded NULLs.
Padding only the columns you select. Every column of the right side is NULL, including those a later join or the WHERE reads.
Forgetting the flag when the inner side has no rows at all. An empty right side pads every left row.

Language notes

The page above is the same for every language. These are the only language-specific hints.

C: a bool matched in the join's state, reset when a new left row starts.
C++: the same flag as a member of the join operator; a padded row can share the left row's storage with a row of NULLs.
Rust: Option<Row> for the right side of the output row makes padding explicit.
Zig: keep a row of NULL values for the right side, built once when the join opens.

Loading starter code…

No run yet

10 tests wait for your first run

Run tests builds your code, drives the binary through every case for this stage, and shows expected and received output side by side here. Failing cases come first.