Subqueries that Run per Row

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

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

Output contract for this stage

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

What you should see when done

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