Subqueries that Run per Row

Resolve names through nested scopes, so that a subquery may name the outer query's columns while the outer query never sees the subquery's, and run such a correlated subquery once per row that reaches it, reporting the runs as loops=N.

Not run yet · 7 tests

Why this stage exists

"Users who have at least one order" is exists (select 1 from orders o where o.user_id = u.id). The subquery mentions u.id, a column of the outer query, so its answer is different for every user. It cannot run once. It must run again for each user, with that user's id.

That is a correlated subquery, and it needs two things this part has not built yet: a binder that can see outwards, and a subquery that runs per row.

Scopes

The qualified-names stage resolved every name against one FROM. Now there are nested ones: the subquery's FROM inside the outer query's. Names are looked up inside first, then outwards:

in o.user_id = u.id, o is found in the subquery's FROM and u one level out;
a bare id that both have means the inner one: in exists (select 1 from orders o where id = 10), id is o.id, and the subquery is not correlated at all;
names never travel the other way: the outer query cannot mention o, which is 01701, nor a column only the subquery's tables have, written bare, such as total, which is 00402.

A column found in an outer scope is an outer reference. For one run of the subquery it is just a value, as a literal would be. So o.user_id = u.id can even use an index on orders (user_id), printed key=u.id, exactly like the lookup of an index nested loop.

Per row

select u.name from users u where exists (select 1 from orders o where o.user_id = u.id)

Filter (EXISTS (subquery 1))

↑ 3 rows

SeqScan (table=users, alias=u)

ran

Subquery (1, per row)

Project (cols=[1])

Filter (o.user_id = u.id)

↑ 6 rows over 3 runs

SeqScan (table=orders, alias=o)

One run per user: loops=3. EXISTS stops each run at the first matching order: 1 row for ada, 2 for bob, 3 for cy.

If that looks like a nested loop join, it is one: users outside, orders inside, a condition between them. Real planners notice, and rewrite EXISTS into a semi-join and NOT EXISTS into an anti-join, so that the hash and merge joins of this part can run them. Running the subquery per row is the plain version every rewrite must agree with.

NOT EXISTS against NOT IN

With an order whose user_id is NULL, the last stage's id not in (select user_id from orders) returned nothing. not exists (select 1 from orders o where o.user_id = u.id) asks a different question for each user: is there an order whose user_id equals this id? For cy there is none (the NULL order equals nobody), so NOT EXISTS keeps cy. That is the answer people expect, and why NOT EXISTS is usually the safer way to write "has no ...".

The algorithm in words

Binding through scopes

Inside first, then outwards.

1.Each SELECT is a scope holding its FROM's entries; a subquery's scope sits inside the scope of the query around it.
2.A bare column is the column of the innermost scope that has an entry with it (01702 if two entries there have it).
3.A qualified q.c is in the innermost scope that has an entry named q (01701 if none), and must be a column of it (00402).
4.A column found in an outer scope is an outer reference. A subquery with one, at any depth inside it, is correlated.

Running a correlated subquery

Once per evaluation.

1.Each time its expression is evaluated, put the outer row's values in place of the outer references and run the subquery.
2.Use its result for this row only: scalar, IN and EXISTS as in the previous stage. EXISTS still stops at its first row.
3.Count every run in rows_examined, and in explain analyze report loops = the number of runs.

Output contract for this stage

These are the exact lines the tests check. The full definition is on the output contract page, section 78.

Input	Output
`select o.total from users u where exists (select 1 from orders o where o.user_id = u.id);`	`[ERROR:01701] ...`
`explain` of the EXISTS query	`Filter (EXISTS (subquery 1))` over the users scan and `Subquery (1, per row)`
`explain analyze` of it, 3 users	`Subquery (1, per row) (actual rows=2 pages=0 loops=3)`

What you should see when done

shell

$droid --db corr.db
Welcome to droid!
>create table users (id int primary key, name varchar(20));
Create table statement executed successfully
>create table orders (id int primary key, user_id int);
Create table statement executed successfully
>insert into users (id, name) values (1, 'ada');
Insert statement executed successfully (1 rows)
>insert into users (id, name) values (2, 'cy');
Insert statement executed successfully (1 rows)
>insert into orders (id, user_id) values (10, 1);
Insert statement executed successfully (1 rows)
>select u.name, (select count(*) from orders o where o.user_id = u.id) as n from users u;
name | n
ada | 1
cy | 0
(2 rows)
[EXEC] rows_examined=4
>.exit
exiting.. good bye!

Common bugs in this stage

Running a correlated subquery once. Every row gives it different values.
Looking names up outside first. The inner scope wins.
Letting the outer query see inner entries. They are 01701 there.
Caching the result across rows. Only an uncorrelated subquery may keep its answer.
Counting loops for the whole statement. It is the number of runs: the rows that reached the expression.

Language notes

The page above is the same for every language. These are the only language-specific hints.

C: give each scope a pointer to its parent; an outer reference stores how many levels out it is and reads that scope's current row.
C++: a Scope* parent chain in the binder; at run time, each subquery evaluation gets a pointer to the outer row.
Rust: pass the outer rows down as a slice &[&Row], indexed by scope depth.
Zig: a slice of outer row pointers passed into the subquery's open.

Loading starter code…

No run yet

7 tests wait for your first run

Run tests builds your code, drives the binary through every case for this stage, and shows expected and received output side by side here. Failing cases come first.