Letting the Cost Model Choose

Why this stage exists

You now have four ways to join, and each is the best one somewhere. An index nested loop is unbeatable for five users' orders and hopeless for all of them without an index. A hash join is the opposite. A merge join wins when both sides already come sorted. Forcing one with --join was fine for learning each; a real query needs the planner to pick.

The cost-model stage priced scans. This stage prices joins the same way: estimate how many rows each node produces, put a number on each algorithm, keep the cheapest. From here --join auto, the default, does that, as long as every table has statistics. Without them it keeps the nested loop, as the cost-model stage kept its rule plans.

How many rows does a join produce?

For users join orders on u.id = o.user_id, each order matches about one user. In general, an equality between two columns keeps about L × R / max(ndv_l, ndv_r) rows: 1000 users and 2000 orders with 1000 distinct user_id give 2000. The idea is that the column with fewer distinct values has its values all present in the other, so each row on one side meets R / ndv rows on the other. Any other condition keeps a third, as for a WHERE. A cross join keeps everything, and a LEFT JOIN at least its left rows.

An index nested loop's right child is a lookup, which estimates the rows of one value, E = floor(R / ndv) (with ndv = R for the table's key), and prints its cost for that one run. The join still uses the right table's full R, without the lookup, so the estimate is the same whatever the algorithm.

What each algorithm costs

On tiny tables the nested loop wins: reading a one-page table four times is nothing. On large ones the picture changes:

• five users' orders, with an index on user_id: five lookups beat reading 2000 wide orders, so the index nested loop wins;
• every user's orders, no index: the hash join reads each table once;
• users joined to a table keyed by user id: both sides already arrive in key order, and the merge join is one pass over each.

Ties go to the simpler algorithm, in the order nested loop, index nested loop, hash, merge, so every implementation prints the same plan. Ties are not rare: users joined to orders with no index costs the same by hash and by merge when users already arrives in key order and only orders needs a Sort, and the hash join is taken.

Output contract for this stage

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

What you should see when done

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

Common bugs in this stage

• Choosing by cost when a table has no statistics. Without them auto is the nested loop, and nothing prints an estimate.
• Integer division too early. Multiply everything, then floor once.
• Pricing an algorithm that cannot be used. A hash join on < is not a candidate.
• Breaking ties differently. The order is nested loop, index nested loop, hash, merge.
• Counting the merge join's sort twice. The Sort node prints its child's cost; the join adds rows(x).

Language notes

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

• C: keep estimates as 64-bit integers and selectivities as numerator/denominator pairs; multiply both, divide once.
• C++: a small Fraction struct with operator* keeps the arithmetic exact.
• Rust: u128 numerators and denominators avoid overflow for products of large row counts.
• Zig: u128 and @divFloor at the end; std.math.mul catches an overflow if you go wrong.