Join Optimization

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

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.

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.

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.

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.