---
title: 'Join Optimization'
source: 'https://academia.sh/en/courses/advanced-sql/join-optimization'
course: 'Advanced SQL'
language: en
updated: '2026-08-23T07:00:38+00:00'
license: 'CC BY-SA 4.0'
---

# Join Optimization

The cost multiplier of nested loop join, how decisive the index on the inner side is, the measured effect of join order, the loop's linear scaling with outer row count, and when hash join and merge join win out.

All the measurements in the previous lessons were on a single table, and the decision was
a single one: index or scan. When more than one table is joined, the number of decisions
grows. The database decides three things separately: the order in which the tables are
read, the path by which each table is accessed, and the method by which rows are matched.

These three decisions are tied to each other, and the wrong combination costs hundreds
of times more than the right one. This lesson takes up the plan's counterpart to these
decisions and their measured effect.

## Data Set

```sh
rm -f library.db
cat > setup.sql <<'SQL'
CREATE TABLE branch (
  branch_id INTEGER PRIMARY KEY,
  name      TEXT NOT NULL,
  city      TEXT NOT NULL
);
CREATE TABLE member (
  member_id         INTEGER PRIMARY KEY,
  name              TEXT NOT NULL,
  city              TEXT NOT NULL,
  registration_date TEXT NOT NULL
);
CREATE TABLE book (
  book_id   INTEGER PRIMARY KEY,
  title     TEXT NOT NULL,
  author    TEXT NOT NULL,
  year      INTEGER NOT NULL,
  branch_id INTEGER NOT NULL
);
CREATE TABLE loan (
  loan_id     INTEGER PRIMARY KEY,
  book_id     INTEGER NOT NULL,
  member_id   INTEGER NOT NULL,
  pickup_date TEXT NOT NULL,
  return_date TEXT
);

INSERT INTO branch (branch_id, name, city) VALUES
  (1,'Central','Ankara'),(2,'Bahcelievler','Ankara'),(3,'Kadikoy','Istanbul'),
  (4,'Beyoglu','Istanbul'),(5,'Konak','Izmir'),(6,'Nilufer','Bursa'),
  (7,'Selcuklu','Konya'),(8,'Cankaya','Ankara');

INSERT INTO member (member_id, name, city, registration_date)
WITH RECURSIVE counter(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM counter WHERE n < 120000)
SELECT n, 'Member ' || n,
       CASE n % 5 WHEN 0 THEN 'Ankara' WHEN 1 THEN 'Istanbul' WHEN 2 THEN 'Izmir'
                  WHEN 3 THEN 'Bursa' ELSE 'Konya' END,
       date('2015-01-01', '+' || (n % 3200) || ' days')
FROM counter;

INSERT INTO book (book_id, title, author, year, branch_id)
WITH RECURSIVE counter(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM counter WHERE n < 200000)
SELECT n, 'Book ' || n, 'Author ' || (n % 4000), 1950 + (n % 75), 1 + (n % 8)
FROM counter;

INSERT INTO loan (loan_id, book_id, member_id, pickup_date, return_date)
WITH RECURSIVE counter(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM counter WHERE n < 2000000)
SELECT n, 1 + ((n * 7) % 200000), 1 + ((n * 13) % 120000),
       date('2018-01-01', '+' || ((n * 37) % 2437) || ' days'),
       CASE WHEN n % 9 = 0 THEN NULL
            ELSE date('2018-01-01', '+' || (((n * 37) % 2437) + 14) || ' days') END
FROM counter;
SQL
sqlite3 library.db < setup.sql
```

## Nested Loop and the Inner Index

The most basic join method is **nested loop join**: for every row read from the outer
table, matching rows are searched for in the inner table. Its cost is given by a single
product — the outer row count times the cost of one inner search. What determines the
second factor is whether there is an index on the join column on the inner side.

```sh
sqlite3 library.db <<'SQL'
CREATE INDEX book_author ON book(author);
EXPLAIN QUERY PLAN
SELECT count(*) FROM book b JOIN loan l ON l.book_id = b.book_id
WHERE b.author = 'Author 7';
.timer on
.stats vmstep
SELECT count(*) FROM book b JOIN loan l ON l.book_id = b.book_id
WHERE b.author = 'Author 7';
.timer off
.stats off
CREATE INDEX loan_book ON loan(book_id);
EXPLAIN QUERY PLAN
SELECT count(*) FROM book b JOIN loan l ON l.book_id = b.book_id
WHERE b.author = 'Author 7';
.timer on
.stats vmstep
SELECT count(*) FROM book b JOIN loan l ON l.book_id = b.book_id
WHERE b.author = 'Author 7';
SQL
```

```
QUERY PLAN
|--SCAN l
`--SEARCH b USING INTEGER PRIMARY KEY (rowid=?)
500
VM-steps: 10000512
Run Time: real 0.367 user 0.327078 sys 0.039688
QUERY PLAN
|--SEARCH b USING COVERING INDEX book_author (author=?)
`--SEARCH l USING COVERING INDEX loan_book (book_id=?)
500
VM-steps: 1712
Run Time: real 0.000 user 0.000060 sys 0.000045
```

In the first plan, `loan` is the driving table: two million loan records are read, for
each of them `book` is visited by primary key, and only at the end does the author
condition filter. The query spends ten million steps to return five hundred rows.

In the second plan, the order reversed. The difference is the presence of a single
index: as soon as an index exists on `loan.book_id`, starting from the `book` table
becomes sensible. The author condition leaves fifty books, and for each book, loan
records are searched from the index. Ten million steps dropped to 1,712.

The rule that follows from this is the shortest summary of join performance: **if there
is no index on the join columns, order cannot be chosen.** The number of options in front
of the planner is determined by the access paths that indexes open up.

## The Measured Effect of Order

To isolate the effect of order, the same query is run in reverse order while the indexes
stay in place. In this engine, the `CROSS JOIN` syntax pins the join order: the table on
the left becomes the outer loop. The syntax for pinning order varies by engine; here it
is used as a measurement tool.

```sh
sqlite3 library.db <<'SQL'
EXPLAIN QUERY PLAN
SELECT count(*) FROM loan l CROSS JOIN book b ON b.book_id = l.book_id
WHERE b.author = 'Author 7';
.timer on
.stats vmstep
SELECT count(*) FROM loan l CROSS JOIN book b ON b.book_id = l.book_id
WHERE b.author = 'Author 7';
SQL
```

```
QUERY PLAN
|--SCAN l USING COVERING INDEX loan_book
`--SEARCH b USING INTEGER PRIMARY KEY (rowid=?)
500
VM-steps: 10000512
Run Time: real 0.068 user 0.063411 sys 0.004218
```

Same data, same indexes, same result: 500. Only the order changed, and step count rose
from 1,712 to 10,000,512 — about fifty-eight hundred times. When the outer loop holds
two million rows, it barely matters how cheap the inner search is.

This output shows a second thing too. The step count is identical to the measurement
from the no-index case: 10,000,512. Time, however, is about five times shorter. This is
where it becomes visible that the two measures count different things: step count counts
the instructions the virtual machine executes, while time also accounts for the bytes
read. A scan over a covering index runs the same number of instructions as a scan over
the table, but reads much less data.

## How the Loop Scales

The cost of a nested loop is directly proportional to the outer row count. The following
measurement grows the outer side with two different filter conditions.

```sh
sqlite3 library.db <<'SQL'
CREATE INDEX book_year ON book(year);
.stats vmstep
SELECT count(*) FROM book WHERE author = 'Author 7';
SELECT count(*) FROM book b JOIN loan l ON l.book_id = b.book_id
WHERE b.author = 'Author 7';
SELECT count(*) FROM book WHERE year = 1990;
SELECT count(*) FROM book b JOIN loan l ON l.book_id = b.book_id
WHERE b.year = 1990;
SQL
```

```
50
VM-steps: 161
500
VM-steps: 1712
2667
VM-steps: 8012
26670
VM-steps: 90690
```

When the outer side grows from fifty rows to 2,667 rows (53.3 times), the join's step
count grows from 1,712 to 90,690 (53.0 times). The ratio is nearly one-to-one: the loop
behaves as $O(n)$ in outer row count, while the cost of the inner search stays constant.

This linearity is both the strength and the limit of the nested loop. When the outer
side is small, the method is unbeatable: no preparation is done, only the required rows
are touched. As the outer side grows, a separate tree descent is made for every row, and
the sum of those descents becomes more expensive than reading both tables from start to
end once.

## Two Set-Based Methods

When the outer side grows large, two set-based methods are used instead of row-by-row
search. Both are part of standard relational optimization; which engine implements which
one varies.

**Hash join** reads the smaller side once and builds a hash table from the join column,
then reads the larger side once and looks up each row's match in that table. Its cost is
the sum of the two inputs, not their product. It has a condition: the comparison must be
equality, and the hash table is expected to fit in memory; if it does not fit, the table
is split into partitions and spilled to disk. This is the structure built in the Hash
Tables lesson in the Data Structures course.

**Merge join** reads both inputs sorted by the join column and matches them in a single
pass by advancing two cursors together. If the inputs are already sorted — for instance,
if both sides have an index on that column — there is no preparation cost and memory use
is low. If they are not sorted, sorting is required first, and then the cost is
determined by sorting.

The choice looks at three measures: the size of the inputs, whether the join condition
is equality, and whether the inputs arrive already sorted. A small outer side with an
indexed inner side points to nested loop, two large tables point to hash join, and two
large, already sorted inputs point to merge join.

Every plan measured throughout this lesson is a nested loop; that is the join method
used by this engine. Which family shows up in plan output depends on the engine, but the
decision to be read is the same: which side drives, how the inner side is accessed, and
whether matching is done row by row or as a set.

## Summary

- The cost of a nested loop join is the product of the outer row count and the cost of
  one inner search; the index on the inner side determines the second factor.
- When there is no index on the join column, the planner has no order to choose from;
  once the index was added, the same query dropped from 10,000,512 steps to 1,712.
- Order alone is decisive: reversing the order while the indexes stayed in place raised
  the same query's step count by about fifty-eight hundred times.
- The same step count does not mean the same time; a scan over a covering index ran in
  about a fifth of the time of a table scan at the same instruction count.
- As the outer side grows, the nested loop grows linearly; past this point, set-based
  methods such as hash join or merge join are preferred.

## Next Step

A join is not the only way to bring tables side by side. The same question can often be
written with a subquery too, and the two forms can give the same result while producing
very different plans — especially when the subquery depends on the outer row. The next
lesson compares these forms: which subquery is evaluated once, which is evaluated per
row, and which equivalent rewrite closes the gap between them.