---
title: 'Subquery Reduction'
source: 'https://academia.sh/en/courses/advanced-sql/subquery-reduction'
course: 'Advanced SQL'
language: en
updated: '2026-08-23T07:00:38+00:00'
license: 'CC BY-SA 4.0'
---

# Subquery Reduction

The per-row evaluation of a correlated subquery and its reduction to a single pass with a window function, the measured plans of the same question written with IN, EXISTS, and a join, the interaction between NOT IN and NULL, and the equivalence conditions for a rewrite.

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

```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
```

## 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.

```sh
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.

```sh
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.

```sh
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.