Joining Through an Index

Why this stage exists

A nested loop over 100 users and 200 orders examines 100 + 100 × 200 = 20100 rows to find 200 pairs. Almost all of that work is reading orders that belong to someone else. If orders has an index on user_id, each user's orders can be found in a few page reads, instead.

That is an index nested loop join: the same loop, with the inner scan replaced by a lookup whose key comes from the outer row. When the outer side is small, nothing beats it. It is how most OLTP queries join, and the reason almost every foreign key column gets an index.

A scan whose key changes

Until now an IndexScan's key was a literal: key=5. Here it is a column of the other table:

For each user, the join reads the user's id, runs the right-hand scan as if it were user_id = <that id>, and pairs the user with what it finds. The rest of the condition, if any, is tested on each pair, as before.

Which column can be looked up:

• the right table's key: joining orders to users on u.id = o.user_id finds each user by key, IndexScan (table=users, alias=u, key=o.user_id);
• the first column of an index on the right table. An index on (user_id, total) works; one on (total, user_id) does not, for the same reason a WHERE on user_id alone cannot use it: its entries are in total order.

When the index holds every column the statement reads of that entry, the lookup is an IndexOnlyScan, as for one table: it never visits the table, so it adds nothing to index_lookups.

Anything else, such as no index, < instead of =, or an expression, stays a nested loop, and explain shows it. This is the first time --join can name an algorithm that does not apply, and the rule is the same for every later one: fall back to the nested loop, visibly.

A NULL outer value looks nothing up: NULL = anything is unknown. Under a LEFT JOIN, an outer row whose lookup finds nothing is padded, as in the last stage.

Counting runs

rows_examined adds up what every lookup returned, and index_lookups the rows fetched through an index entry, as for a single-table index scan. A lookup by the table's own key goes through no index entry, so it adds to rows_examined only.

explain analyze gains one field. A node on the right side of a nested loop runs many times, and loops=<L> says how many: the lookup above ends with (actual rows=200 pages=<P> loops=100). Its rows and pages add up over all its runs. Every node on the right side of a nested loop prints loops, even loops=1 or loops=0; a node anywhere else prints none, so earlier output does not change.

Output contract for this stage

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

What you should see when done

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

Common bugs in this stage

• Building the lookup once. The key changes with every outer row; the scan must be re-run with the new value.
• Looking up a NULL. A NULL key would find the entries whose value is NULL, which sort first in the index. It must find nothing.
• Using an index whose first column is not the join column. Its entries are not in that order.
• Counting index_lookups for a lookup by the table key. No index entry is read.
• Printing loops on the outer side. It runs once.

Language notes

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

• C: the inner scan should be repositionable to a new key without being freed and rebuilt for each outer row; keep the key in the scan's state.
• C++: the same holds: one scan object per join, reset with each outer row's key, avoids an allocation per row.
• Rust: passing the key by reference into the inner scan's reset keeps the outer row borrowed only while the lookup starts.
• Zig: store the current key in the scan's state; the allocator then sees one scan per join, not one per row.