Join Order for Three or More Tables

Why this stage exists

Sales of category t3: 2000 sales, 200 products, 20 categories. Written as sale join prod join cat where c.tag = 't3', the obvious plan joins every sale to its product, making 2000 rows, then throws away nineteen twentieths of them when it reaches the categories. Started from the other end, the filter leaves one category, which has 10 products, which have 100 sales. The rows are the same and the work is a tiny fraction.

The previous stage chose each join's algorithm. This one chooses which tables to join first.

Left-deep orders

A left-deep plan adds one table at each join: the first two tables, then that result with the third, and so on. Every right child is a single table, which is what an index nested loop needs. With three tables there are six orders, and with four there are 24.

For each order, place the conditions again (with inner joins, ON and WHERE mean the same), choose each join's algorithm from the bottom up as before, and take the cost of the top join. The cheapest order wins.

No cross products

In x join y on x.k = y.k join z on y.m = z.m, nothing links x and z. An order that joins them first makes every pair of their rows, a cross product, only to filter most of them away at the next join. Orders like that are skipped, as long as some order avoids them. With only a few small tables a cross product can occasionally be cheaper, but real planners avoid them for the same reason this one does: the estimates are least reliable exactly there.

What does not move

Columns belong to their entries, not to positions, so select * still lists x's columns, then y's, then z's, whatever order the plan joins in. The rows are the same; only their order without an ORDER BY can change.

A LEFT JOIN is not reordered: a left join b keeps every row of a, and swapping the sides would keep every row of b instead. A FROM of two tables is joined as written, and so is a FROM with any LEFT JOIN, as is any statement with a table that has no statistics, or a forced --join.

Output contract for this stage

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

[PLAN] select * from x join y on x.k = y.k join z on y.m = z.m
[PLAN]   └── NestedLoopJoin (on: x.k = y.k) (rows=6 cost=9)
[PLAN]       ├── NestedLoopJoin (on: y.m = z.m) (rows=6 cost=3)
[PLAN]       │   ├── SeqScan (table=z) (rows=2 cost=1)
[PLAN]       │   └── SeqScan (table=y) (rows=6 cost=1)
[PLAN]       └── SeqScan (table=x) (rows=4 cost=1)

What you should see when done

$droid --db order.db
Welcome to droid!
>create table x (id int primary key, k int);
Create table statement executed successfully
>create table y (id int primary key, k int, m int);
Create table statement executed successfully
>create table z (id int primary key, m int);
Create table statement executed successfully
>insert into x (id, k) values (1, 1);
Insert statement executed successfully (1 rows)
>insert into x (id, k) values (2, 1);
Insert statement executed successfully (1 rows)
>insert into y (id, k, m) values (1, 1, 1);
Insert statement executed successfully (1 rows)
>insert into z (id, m) values (1, 1);
Insert statement executed successfully (1 rows)
>analyze x;
Analyze statement executed successfully
>analyze y;
Analyze statement executed successfully
>analyze z;
Analyze statement executed successfully
>explain select * from x join y on x.k = y.k join z on y.m = z.m;
[PLAN] select * from x join y on x.k = y.k join z on y.m = z.m
[PLAN]   └── NestedLoopJoin (on: x.k = y.k) (rows=2 cost=3)
[PLAN]       ├── NestedLoopJoin (on: y.m = z.m) (rows=1 cost=2)
[PLAN]       │   ├── SeqScan (table=y) (rows=1 cost=1)
[PLAN]       │   └── SeqScan (table=z) (rows=1 cost=1)
[PLAN]       └── SeqScan (table=x) (rows=2 cost=1)
>.exit
exiting.. good bye!

As written, x then y then z costs 5. Starting from y, as y, z, x, costs 3, and so does z, y, x; on that tie, y, z, x wins, because its FROM positions (y second, z third, x first) come before z, y, x.

Common bugs in this stage

• Reordering a LEFT JOIN. It changes the rows.
• Placing conditions once, for the written order. Each order needs its own placement.
• Reordering the columns of select *. Columns stay with their entries.
• Picking a cross product when a linked order exists.
• Breaking ties by something other than FROM positions. The written order wins a tie.

Language notes

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

• C: generate permutations in lexicographic order with the classic next-permutation step on an array of entry indexes; the first one is the written order.
• C++: std::next_permutation on a sorted vector of indexes visits them in exactly the tie-break order.
• Rust: a small recursive generator over a Vec<usize>, or the next-permutation algorithm on a slice.
• Zig: the next-permutation algorithm on a []usize slice, starting from the identity.