droidPart 7 · Joins and Relations

Joins and Relations · Stage 9

Join Order for Three or More Tables

For inner joins over analysed tables, try every left-deep order of the FROM's entries, skip orders that make a cross product, price each with the join estimates and costs of the previous stage, and keep the cheapest, without changing the columns or the rows.

Not run yet · 7 tests

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.

Written order: x, y, z (cost 11)

NestedLoopJoin (on: y.m = z.m)

↑ rows=6 cost=5

NestedLoopJoin (on: x.k = y.k)

↑ rows=4 cost=1

SeqScan (table=x)

↑ rows=6 cost=1

SeqScan (table=y)

↑ rows=2 cost=1

SeqScan (table=z)

Chosen: z, y, x (cost 9)

ran

NestedLoopJoin (on: x.k = y.k)

↑ rows=6 cost=3

NestedLoopJoin (on: y.m = z.m)

↑ rows=2 cost=1

SeqScan (table=z)

↑ rows=6 cost=1

SeqScan (table=y)

↑ rows=4 cost=1

SeqScan (table=x)

Starting from the 2-row table means the 6-row y is read twice, not four times.

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.

The algorithm in words

Choosing the join order

Try every left-deep order, keep the cheapest.

1.Reorder only a FROM of three entries or more, when every join is inner, every table has statistics and --join is auto. Otherwise join as written.
2.For each permutation of the entries, check that every entry after the first shares a conjunct with the entries before it. Skip the permutation if not, unless every permutation fails that test.
3.Place the conjuncts for this order: each at the scan of the one entry it reads, or at the lowest join that has all its entries.
4.Build the joins bottom up, choosing each one's algorithm and estimate as in the previous stage. The order's cost is the top join's cost.
5.Keep the cheapest order. On a tie, keep the one that comes first when orders are compared by the FROM positions of their entries.

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

shell

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

Loading starter code…

No run yet

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