Two Tables, One Loop

Why this stage exists

Every query so far has read one table. Real data is spread over several: users in one table, their orders in another, each order's items in a third, tied together by keys. A join puts them back together, and it is the operation that makes a relational database relational.

This stage builds the simplest join there is. Every later join algorithm in this part is a faster way to produce exactly the same rows.

What a join means

Joining users and orders pairs every user with every order: 3 users and 4 orders make 12 pairs, each one row with the user's columns followed by the order's. That is a cross product, which is what from users, orders and cross join mean. A condition keeps only some pairs: join orders o on u.id = o.user_id keeps the pairs where the order belongs to the user.

For these joins, ON and WHERE say the same thing. from a join b on X where Y keeps the pairs for which both X and Y are true, and so does from a, b where X and Y. The next stage, LEFT JOIN, is where the two stop being interchangeable.

A pair for which the condition is unknown is dropped, as a WHERE drops a row. So a NULL key joins nothing: an order whose user_id is NULL pairs with no user, and two NULLs do not pair with each other either.

The nested loop

The algorithm is two loops, one inside the other:

The left child is the outer side, read once. The right child is the inner side, restarted from its beginning for every outer row. So a nested loop's rows come out in a fixed order: outer order, and for each outer row, inner order. That is the order you see when a join has no ORDER BY.

It is also why the counter changes meaning a little. rows_examined now adds up the rows every scan handed up, every time it ran. With one scan run once, nothing changes; with a join, the inner scan's rows count once per outer row.

Put each condition where it can be tested first

Testing u.id = 2 after forming every pair wastes work: 15 rows read to keep one user's orders. The condition reads only users, so it can be tested at the users scan, where it is a key bound like any other. Then only one user comes out, the orders are read once, and the query examines 1 + 4 = 5 rows.

The rule is the same for every conjunct of the WHERE and of every ON:

• one that reads one table goes down to that table's scan, and is planned as it would be for that table alone;
• one that reads several tables goes to the lowest join that has them all below it, and becomes its condition.

A condition like u.id = 2 or o.total = 5 reads both tables and cannot go down: every pair is formed and tested.

Names with two tables

With two tables, a bare name can be ambiguous: users and orders both have id, so select id is 01702. Qualify it, u.id, and it is not. A name only one table has, like total, needs no qualifier.

An ON may name its own entry and the entries before it: from orders o join users u on o.user_id = x.id join users x ... is 01701, since x comes later.

Two entries cannot share a name, 01703. That is why a self join needs aliases: users a join users b is two entries reading the same table.

select * lists every entry's columns, entry by entry in FROM order. The header can repeat a name, id | name | id | user_id | total, and that is fine.

Choosing an algorithm

A command line option, --join nl|inl|hash|merge|auto, will let each later stage force its own algorithm so that its tests can see it. In this stage every value means a nested loop; an unknown one is 00108, and --join with nothing after it is 00102. Both end the program with status 1.

Output contract for this stage

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

[PLAN] select * from users, orders, items
[PLAN]   └── NestedLoopJoin
[PLAN]       ├── NestedLoopJoin
[PLAN]       │   ├── SeqScan (table=users)
[PLAN]       │   └── SeqScan (table=orders)
[PLAN]       └── SeqScan (table=items)

What you should see when done

$droid --db join.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, total 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, 'bob');
Insert statement executed successfully (1 rows)
>insert into orders (id, user_id, total) values (10, 1, 5);
Insert statement executed successfully (1 rows)
>insert into orders (id, user_id, total) values (11, 1, 30);
Insert statement executed successfully (1 rows)
>select u.name, o.total from users u join orders o on u.id = o.user_id;
name | total
ada | 5
ada | 30
(2 rows)
[EXEC] rows_examined=6
>.exit
exiting.. good bye!

Common bugs in this stage

• Not restarting the inner side. After the first outer row the inner scan is exhausted; it must start again from its first row.
• Counting the inner scan once. Every run counts: 2 users and 2 orders examine 2 + 2 × 2 = 6.
• Joining NULL to NULL. NULL = NULL is unknown, so the pair is dropped.
• Leaving single-table conditions above the join. The rows are right but rows_examined is not.
• Pushing down a condition that reads both tables. It can only be tested on a pair.
• Skipping the Sort for ORDER BY on a key. With a join, the rows do not arrive in one table's key order, so the Sort stays.

Language notes

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

• C: give every operator a rewind (or reopen) function next to next; the join calls it on its right child for each left row.
• C++: a virtual rewind() in the operator base class, overridden by each scan.
• Rust: an operator trait with next and rewind; the join holds its two children as Box<dyn Operator>.
• Zig: a vtable struct with next and rewind function pointers, or a tagged union of operators with a switch.