LEFT JOIN and NULL Padding

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

>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.

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.

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.

Output contract for this stage

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

What you should see when done

$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.