Join tables with a comma, CROSS JOIN or JOIN ... ON, as a NestedLoopJoin that restarts its right child for every left row, pushes each condition down to the lowest place that can test it, and reports two-child plans and the rows every scan examined.
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.
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 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.
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:
A condition like u.id = 2 or o.total = 5 reads both tables and cannot go down: every pair is formed and tested.
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.
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.
Place every conjunct as low as it can go.
Pairs, in left order then right order.
These are the exact lines the tests check. The full definition is on the output contract page, section 67.
| Input | Output |
|---|---|
select count(*) from users cross join orders; (3 and 4 rows) | 12, then [EXEC] rows_examined=15 |
select id from users u join orders o on u.id = o.user_id; | [ERROR:01702] ... |
select * from users join users on users.id = users.id; | [ERROR:01703] ... |
select * from users u join orders o on ... | header id | name | id | user_id | total |
droid --join bogus | [ERROR:00108] ..., exit status 1 |
droid --join | [ERROR:00102] ..., exit status 1 |
explain logical select * from users u join orders o on u.id = o.user_id where u.id > 1; | Filter (u.id > 1) over Join (on: u.id = o.user_id) over the two Gets; , and CROSS JOIN print Join |
explain select * from users, orders, items; | the tree below |
[PLAN] select * from users, orders, items
[PLAN] └── NestedLoopJoin
[PLAN] ├── NestedLoopJoin
[PLAN] │ ├── SeqScan (table=users)
[PLAN] │ └── SeqScan (table=orders)
[PLAN] └── SeqScan (table=items)
$droid --db join.dbWelcome 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 | totalada | 5ada | 30(2 rows)[EXEC] rows_examined=6>.exitexiting.. good bye!
2 + 2 × 2 = 6.NULL = NULL is unknown, so the pair is dropped.rows_examined is not.The page above is the same for every language. These are the only language-specific hints.
rewind (or reopen) function next to next; the join calls it on its right child for each left row.rewind() in the operator base class, overridden by each scan.next and rewind; the join holds its two children as Box<dyn Operator>.next and rewind function pointers, or a tagged union of operators with a switch.