Subquery Reduction

A join is not the only way to bring tables side by side. The same question can often be written with a subquery too; the two forms give the same result but do not produce the same plan.

The source of the distinction is a single question: is the subquery evaluated once, or once for every row of the outer query? A subquery that does not depend on the outer query runs once, and its result is used. A correlated subquery, one that takes a value from the outer row, runs again for every row — in other words, it is a hidden loop, and its cost follows the nested loop formula from the previous lesson.

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

A Correlated Subquery Is a Loop

The question is: which is each member’s most recent loan? The direct way to write it is to compute that member’s maximum date for every loan record and compare against it.

sqlite3 library.db <<'SQL'
CREATE INDEX loan_member ON loan(member_id);
CREATE INDEX loan_book   ON loan(book_id);
CREATE INDEX loan_pickup ON loan(pickup_date);
EXPLAIN QUERY PLAN
SELECT count(*) FROM loan l
WHERE l.pickup_date = (SELECT max(l2.pickup_date) FROM loan l2 WHERE l2.member_id = l.member_id);
.timer on
.stats vmstep
SELECT count(*) FROM loan l
WHERE l.pickup_date = (SELECT max(l2.pickup_date) FROM loan l2 WHERE l2.member_id = l.member_id);
.timer off
.stats off
EXPLAIN QUERY PLAN
SELECT count(*) FROM
  (SELECT pickup_date, max(pickup_date) OVER (PARTITION BY member_id) AS last_pickup FROM loan)
WHERE pickup_date = last_pickup;
.timer on
.stats vmstep
SELECT count(*) FROM
  (SELECT pickup_date, max(pickup_date) OVER (PARTITION BY member_id) AS last_pickup FROM loan)
WHERE pickup_date = last_pickup;
SQL

QUERY PLAN
|--SCAN l
`--CORRELATED SCALAR SUBQUERY 1
   `--SEARCH l2 USING INDEX loan_member (member_id=?)
120000
VM-steps: 232279993
Run Time: real 7.486 user 6.674963 sys 0.810437
QUERY PLAN
|--CO-ROUTINE (subquery-1)
|  |--CO-ROUTINE (subquery-3)
|  |  `--SCAN loan USING INDEX loan_member
|  `--SCAN (subquery-3)
`--SCAN (subquery-1)
120000
VM-steps: 75200032
Run Time: real 1.009 user 0.987930 sys 0.020616

In the first plan, the CORRELATED SCALAR SUBQUERY node says that the subquery depends on the outer row. There are two million rows on the outer side; for each of them, all of that member’s records are looked at to find the maximum date. The presence of the index lowers the inner cost but does not remove the loop: two hundred and thirty-two million steps.

The second form does the same computation with a window function. This construct, introduced in the Compound Queries topic, attaches its partition’s aggregate value to every row. The nodes in the plan describe a single pass: the index is read in member_id order, and because the same member’s rows are already adjacent, the partition’s maximum is determined in one pass. Step count dropped to about a third, and time dropped to roughly a seventh in this environment.

The result is the same in both forms: 120,000. The source of the gain is not a better index but not repeating the same work.

Three Forms of the Same Question

The question “how many books were borrowed at least once in 2024?” can be written in three separate forms. All three give the same number.

sqlite3 library.db <<'SQL'
EXPLAIN QUERY PLAN
SELECT count(*) FROM book b WHERE b.book_id IN
  (SELECT l.book_id FROM loan l WHERE l.pickup_date >= '2024-01-01');
EXPLAIN QUERY PLAN
SELECT count(*) FROM book b WHERE EXISTS
  (SELECT 1 FROM loan l WHERE l.book_id = b.book_id AND l.pickup_date >= '2024-01-01');
EXPLAIN QUERY PLAN
SELECT count(DISTINCT b.book_id) FROM book b JOIN loan l ON l.book_id = b.book_id
WHERE l.pickup_date >= '2024-01-01';
.timer on
.stats vmstep
SELECT count(*) FROM book b WHERE b.book_id IN
  (SELECT l.book_id FROM loan l WHERE l.pickup_date >= '2024-01-01');
SELECT count(*) FROM book b WHERE EXISTS
  (SELECT 1 FROM loan l WHERE l.book_id = b.book_id AND l.pickup_date >= '2024-01-01');
SELECT count(DISTINCT b.book_id) FROM book b JOIN loan l ON l.book_id = b.book_id
WHERE l.pickup_date >= '2024-01-01';
SQL

QUERY PLAN
|--SEARCH b USING INTEGER PRIMARY KEY (rowid=?)
`--LIST SUBQUERY 1
   |--SEARCH l USING INDEX loan_pickup (pickup_date>?)
   `--CREATE BLOOM FILTER
QUERY PLAN
|--SCAN b
`--CORRELATED SCALAR SUBQUERY 1
   `--SEARCH l USING INDEX loan_book (book_id=?)
QUERY PLAN
|--USE TEMP B-TREE FOR count(DISTINCT)
|--SEARCH l USING INDEX loan_pickup (pickup_date>?)
`--SEARCH b USING INTEGER PRIMARY KEY (rowid=?)
105374
VM-steps: 1738206
Run Time: real 0.261 user 0.148644 sys 0.112857
105374
VM-steps: 9251955
Run Time: real 0.375 user 0.358855 sys 0.016175
105374
VM-steps: 1527452
Run Time: real 0.445 user 0.241398 sys 0.202772

Three forms, three separate plans. The IN form produces the subquery as a list and builds a filter on the outer side. The EXISTS form is correlated: it searches inside loan for each of two hundred thousand books, and its step count is about five times higher. The join form spends the fewest steps, but because it builds a temporary structure for DISTINCT, it takes the longest time in this environment.

The conclusion to draw is not that one form is superior to another. The three measurements give three separate rankings, and step count and time do not point to the same winner. The EXISTS form pulls ahead when the searched condition is highly selective and it can stop at the first match; the IN form when the subquery’s result is small; the join form when both sides are large and duplication is not a problem. The decision is made by measurement.

The join form also has a side effect: if a book had more than one loan in 2024, the join produces that book as more than one row. The count(DISTINCT ...) form is therefore mandatory — equivalence breaks not in the count of the result, but in row multiplicity.

NOT IN and NULL

Whether a rewrite is equivalent is not always as clear as it looks. The difference between NOT IN and NOT EXISTS is the sharpest example of this.

sqlite3 library.db <<'SQL'
SELECT count(*) FROM book WHERE book_id NOT IN (SELECT 1 UNION ALL SELECT 2);
SELECT count(*) FROM book WHERE book_id NOT IN (SELECT 1 UNION ALL SELECT NULL);
SELECT count(*) FROM book b WHERE NOT EXISTS
  (SELECT 1 FROM (SELECT 1 AS v UNION ALL SELECT NULL) t WHERE t.v = b.book_id);
SELECT count(*) FROM loan WHERE return_date IS NULL;
SQL

199998
0
199999
222222

The second query returns zero. The reason is three-valued logic: the expression book_id NOT IN (1, NULL) means book_id <> 1 AND book_id <> NULL; the second comparison is never true, it stays unknown. A row whose condition is unknown cannot pass the filter, so the result set becomes empty.

NOT EXISTS does not fall into the same trap: it searches for a match, and if it does not find one, it lets the row through. The third query returns 199,999 — the expected number.

This is not an academic detail. The fourth query shows that more than two hundred and twenty-two thousand records in the loan table have a return_date field that is empty. A NOT IN subquery built over this column silently produces an empty result; the query does not fail, it only gives the wrong answer. The NOT EXISTS form is both independent of this behavior and better optimized by most planners.

The Rule for Rewriting

This lesson compared four pairs of forms. The shared method has three steps.

The first step is to see whether the subquery depends on the outer row. If it does, a marker saying so appears in the plan node, and the cost is multiplied by the outer row count. The second step is to look for a structure that reduces per-row work to a single pass: a window function, grouping, a common table expression, or a join. The third step is to check that the rewrite is truly equivalent — NULL behavior, row multiplicity, and empty-result cases are the three separate items of this check.

The most reliable form of an equivalence check is to run both forms and compare the results. In this lesson, every comparison showed both forms returning the same number; this is not a confirmation, it is a precondition for the rewrite.

Summary

• A subquery that depends on the outer row is re-evaluated for every row; its cost follows the nested loop formula and it appears in the plan with a node that marks it as correlated.
• A per-row aggregation, once reduced to a single pass with a window function, dropped from 232,279,993 steps to 75,200,032 in this data set.
• When the same question was written with IN, EXISTS, and a join, three separate plans came out; step count and time did not point to the same form, so the decision is made by measurement.
• A subquery converted into a join can change row multiplicity; equivalence requires DISTINCT or grouping.
• If the subquery’s result contains a single NULL, NOT IN returns an empty set; NOT EXISTS is unaffected by this behavior.

Next Step

Up to this point, every decision the planner made turned out to be the right one: it drove the correct table, it chose the correct index. What it based those decisions on has not been asked yet. The planner does not read the data at query time; it looks at statistics collected beforehand about tables and indexes, and it estimates how many rows each step will return. The next lesson takes up the source of that estimate, how its accuracy is measured, and how the plan changes when the estimate goes wrong.