Correlated Subqueries

The last example in the previous lesson placed two subqueries side by side. One looked at the whole table and produced a single value; the other referenced the outer query’s m.id column. In the phrasing, the difference was a single column name, but this reference changes when the subquery gets evaluated.

A subquery that references a column of the outer query is called a correlated subquery. This lesson takes up what the correlation means, how it grows the amount of work, and how a phrasing that asks the same question with less work is built.

What the Link Means

An independent subquery can be run by itself; its result does not depend on the outer query. Because of this, the engine can evaluate it once and treat it as a constant.

A correlated subquery cannot be run by itself: it contains a name that cannot be resolved. Its meaning is defined as “each time the outer query produces a row, the subquery is re-evaluated with that row’s values.” The conceptual order of evaluation is:

1. The outer query produces a candidate row.
2. The outer column references inside the subquery are replaced with that row’s values.
3. The subquery runs.
4. The result is used in filtering the outer row, or in one of its columns.

This definition is semantic: it determines what the query produces. Whether the engine actually runs it row by row is a separate question, taken up at the end of the lesson.

The typical job of a correlated subquery is a question that requires a per-group comparison, such as “the extreme value inside each group.” The question “each member’s most recent loan” is one of these:

sqlite3 -box -header <<'SQL'
CREATE TABLE member(id INTEGER PRIMARY KEY, name TEXT, branch_id INT);
CREATE TABLE loan(id INTEGER PRIMARY KEY, book_id INT, member_id INT, pickup TEXT, returned TEXT);
INSERT INTO member VALUES (1,'Alice',4),(2,'Ben',4),(3,'Clara',5),(4,'Derek',5);
INSERT INTO loan VALUES
  (1,1,1,'2024-03-01','2024-03-15'),(2,3,1,'2024-03-01','2024-03-20'),
  (4,7,1,'2024-03-11',NULL),(6,2,2,'2024-03-01','2024-03-12'),
  (9,8,2,'2024-03-21',NULL),(10,1,3,'2024-03-04','2024-03-10');

SELECT l.id, l.member_id, l.pickup
FROM loan l
WHERE l.pickup = (SELECT MAX(i.pickup) FROM loan i WHERE i.member_id = l.member_id)
ORDER BY l.member_id;
SQL

┌────┬───────────┬────────────┐
│ id │ member_id │   pickup   │
├────┼───────────┼────────────┤
│ 4  │ 1         │ 2024-03-11 │
│ 9  │ 2         │ 2024-03-21 │
│ 10 │ 3         │ 2024-03-04 │
└────┴───────────┴────────────┘

Giving the inner loan table the alias i and the outer one l is required: the same table appears in two different roles, so only the alias determines which one the member_id column belongs to. The row that draws the link is the WHERE i.member_id = l.member_id condition; because l is visible from inside, the subquery is correlated.

Measuring the Amount of Work

The cost of per-row evaluation can be shown by counting. To do this, a counter is placed into the query: a user-defined function called passthrough that increments a variable every time it is called and returns its argument unchanged. The function is placed in the inner table’s condition, so it runs once for every row scanned in the inner table, and the total call count gives the number of rows the inner table was touched for.

Two phrasings that produce the same result are compared: the correlated subquery, and a phrasing that groups the inner table once and then joins it.

cat > measure.mjs <<'JS'
import { DatabaseSync } from 'node:sqlite';

const db = new DatabaseSync(':memory:');
db.exec(`
  CREATE TABLE member(id INTEGER PRIMARY KEY, name TEXT);
  CREATE TABLE loan(id INTEGER PRIMARY KEY, member_id INT, pickup TEXT);
  INSERT INTO member VALUES (1,'Alice'),(2,'Ben'),(3,'Clara'),(4,'Derek'),
                         (5,'Evan'),(6,'Fiona'),(7,'Grace'),(8,'Hannah');
  INSERT INTO loan VALUES
    (1,1,'2024-03-01'),(2,1,'2024-03-01'),(3,1,'2024-03-04'),(4,1,'2024-03-11'),
    (5,1,'2024-03-18'),(6,2,'2024-03-01'),(7,2,'2024-03-06'),(8,2,'2024-03-11'),
    (9,2,'2024-03-21'),(10,3,'2024-03-04'),(11,3,'2024-03-06'),(12,3,'2024-03-13'),
    (13,3,'2024-03-25'),(14,4,'2024-03-04'),(15,4,'2024-03-13'),(16,4,'2024-03-20'),
    (17,5,'2024-03-06'),(18,5,'2024-03-11'),(19,5,'2024-03-25'),(20,6,'2024-03-04'),
    (21,6,'2024-03-13'),(22,6,'2024-03-20'),(23,7,'2024-03-11'),(24,7,'2024-03-18'),
    (25,8,'2024-03-13');
`);

let visits = 0;
db.function('passthrough', (value) => { visits += 1; return value; });

visits = 0;
const correlated = db.prepare(`
  SELECT m.name, (SELECT COUNT(*) FROM loan l WHERE passthrough(l.member_id) = m.id) AS count
  FROM member m ORDER BY m.id`).all();
console.log('correlated:', correlated.map((s) => s.count).join(','), '| visits:', visits);

visits = 0;
const joined = db.prepare(`
  SELECT m.name, COALESCE(s.count, 0) AS count
  FROM member m
  LEFT JOIN (SELECT member_id, COUNT(*) AS count FROM loan
             WHERE passthrough(member_id) IS NOT NULL GROUP BY member_id) AS s
    ON s.member_id = m.id
  ORDER BY m.id`).all();
console.log('joined     :', joined.map((s) => s.count).join(','),
            '| visits:', visits);
JS
node measure.mjs

correlated: 5,4,4,3,3,3,2,1 | visits: 200
joined     : 5,4,4,3,3,3,2,1 | visits: 25

Both phrasings produced the same eight numbers. The touch count on the inner table, though, was 200 against 25.

The number is not surprising: the outer table has 8 rows, the inner table has 25. In the correlated phrasing the inner table is scanned in full for every outer row, giving $8 \times 25 = 200$. In the joined phrasing the inner table is scanned and grouped once, giving 25; the two eight-row sets are then matched.

In general, with $m$ rows in the outer table and $n$ rows in the inner table, the correlated phrasing does $O(m \cdot n)$ work, and the phrasing that groups first and then joins does $O(m + n)$ work. In a library where the member count and the transaction count both grow tenfold together, the first phrasing’s work grows a hundredfold, and the second’s grows tenfold.

Seeing It in the Query Plan

Measurement shows what the engine actually did, from the outside. What the engine planned to do is read from the query plan. EXPLAIN QUERY PLAN prints the plan without running the query:

sqlite3 <<'SQL'
CREATE TABLE member(id INTEGER PRIMARY KEY, name TEXT, branch_id INT);
CREATE TABLE loan(id INTEGER PRIMARY KEY, book_id INT, member_id INT, pickup TEXT, returned TEXT);
.print -- without index --
EXPLAIN QUERY PLAN
SELECT m.name, (SELECT COUNT(*) FROM loan l WHERE l.member_id = m.id) AS count
FROM member m ORDER BY m.id;
CREATE INDEX loan_member ON loan(member_id);
.print
.print -- with index --
EXPLAIN QUERY PLAN
SELECT m.name, (SELECT COUNT(*) FROM loan l WHERE l.member_id = m.id) AS count
FROM member m ORDER BY m.id;
SQL

-- without index --
QUERY PLAN
|--SCAN m
`--CORRELATED SCALAR SUBQUERY 1
   `--SCAN l

-- with index --
QUERY PLAN
|--SCAN m
`--CORRELATED SCALAR SUBQUERY 1
   `--SEARCH l USING COVERING INDEX loan_member (member_id=?)

The CORRELATED SCALAR SUBQUERY line in the plan says the subquery is correlated and returns a single value. The line below it gives how the inner table is accessed: without an index, SCAN l — a full scan from start to end; with an index, SEARCH l USING … INDEX — direct access. The measured value of 200 is the first plan’s scan repeated eight times.

The second plan shows that a correlated subquery is not inherently expensive; what is expensive is a repeated scan without a suitable access path. With an index, each repeat is not a full scan but a single search, and the total work becomes proportional not to the row count but to the match count.

The Engine’s Right to Rewrite

A query says what is to be done, not how. Subject to leaving the result unchanged, the planner can convert a correlated subquery into a join or a semi-join, or materialize the inner result once and reuse it. These transformations are called subquery flattening, and their scope varies by engine.

The consequence cuts two ways. On one hand, saying “this is slow” every time a correlated phrasing is seen is wrong — the engine may have rescued it. On the other hand, it is also true that the rescue is not guaranteed: if the subquery has an aggregate function, a LIMIT, a null-sensitive condition, or a function with a side effect, the transformation would change the meaning, so it is not performed. Not assuming without measuring is, for this reason, a habit.

The Difference Between EXISTS and a Join

The second common form of correlated subquery is the EXISTS predicate, which asks about existence rather than a value. The same question can also be written with a join, but the two are not equivalent:

sqlite3 -box -header <<'SQL'
CREATE TABLE member(id INTEGER PRIMARY KEY, name TEXT, branch_id INT);
CREATE TABLE loan(id INTEGER PRIMARY KEY, book_id INT, member_id INT, pickup TEXT, returned TEXT);
INSERT INTO member VALUES (1,'Alice',4),(2,'Ben',4),(3,'Clara',5),(4,'Derek',5);
INSERT INTO loan VALUES
  (4,7,1,'2024-03-11',NULL),(9,8,2,'2024-03-21',NULL),
  (13,2,3,'2024-03-25',NULL),(16,4,3,'2024-03-20',NULL);

SELECT m.name FROM member m
WHERE EXISTS (SELECT 1 FROM loan l WHERE l.member_id = m.id AND l.returned IS NULL)
ORDER BY m.id;

SELECT m.name FROM member m
JOIN loan l ON l.member_id = m.id AND l.returned IS NULL
ORDER BY m.id;
SQL

┌───────┐
│ name  │
├───────┤
│ Alice │
│ Ben   │
│ Clara │
└───────┘
┌───────┐
│ name  │
├───────┤
│ Alice │
│ Ben   │
│ Clara │
│ Clara │
└───────┘

Clara appears twice in the second result, because she has two unreturned records and the join produces a row for every match. EXISTS, in contrast, asks “is there at least one match”; it stops at the first match and does not duplicate the row.

This difference is the limit of a join-based rewrite: if a transformation is wanted that does not change the row count, DISTINCT or a grouping has to be added to the join’s result. These additions are not free either — they bring a sorting or temporary-structure cost. Before turning a predicate written with EXISTS into a join, whether the match is unique has to be asked first.

Summary

• A correlated subquery references a column of the outer query and is, semantically, re-evaluated for each outer row.
• For $m$ rows in the outer table and $n$ rows in the inner table, a repeated scan does $O(m \cdot n)$ work, and a phrasing that groups first and then joins does $O(m + n)$ work; in the measurement this came out as 200 against 25.
• In EXPLAIN QUERY PLAN output, the CORRELATED SCALAR SUBQUERY line shows the correlation, and the SCAN or SEARCH line below it shows the access path.
• A correlated phrasing is not inherently expensive; with a suitable access path, each repeat comes down to a single search instead of a full scan.
• EXISTS does not duplicate a row, a join does; the two phrasings produce the same result only when the match is unique.

Next Step

The join-based phrasing in this lesson built its intermediate result as a subquery embedded inside FROM. Two or three layers deeper, this phrasing stops being readable: the intermediate result’s name gets lost in the middle of the query, and if the same intermediate result is needed in two places, it gets written twice. The next lesson introduces common table expressions, which name intermediate results at the start of the query and keep the body plain.