Skip to main content
SQL Interviews intermediate Lesson 6 of 10

CTEs, Subqueries, and Recursion

Why a named CTE scores better than a nested subquery that returns the same rows, when a correlated subquery runs once per row, and recursive CTEs for hierarchies.

A CTE and a subquery usually compile to the same plan. They do not read the same, and readability is a scored criterion.

The same query, two ways to write it

-- nested: correct, and nobody can verify it by reading
SELECT name, total FROM (
    SELECT c.name, sum(o.amount) AS total FROM customers c
    JOIN orders o USING (customer_id)
    WHERE o.status = 'shipped'
    GROUP BY c.name
) t
WHERE total > (
    SELECT avg(total) FROM (
        SELECT sum(amount) AS total FROM orders
        WHERE status = 'shipped' GROUP BY customer_id
    ) u
)
ORDER BY total DESC;
-- CTEs: same plan, readable top to bottom
WITH shipped AS (
    SELECT customer_id, amount FROM orders WHERE status = 'shipped'
),
per_customer AS (
    SELECT customer_id, sum(amount) AS total FROM shipped GROUP BY customer_id
),
average AS (
    SELECT avg(total) AS avg_total FROM per_customer
)
SELECT c.name, p.total, round(a.avg_total, 2) AS avg_total
FROM per_customer p
JOIN customers c USING (customer_id)
CROSS JOIN average a
WHERE p.total > a.avg_total
ORDER BY p.total DESC;
┌─────────┬────────┬───────────┐
│  name   │ total  │ avg_total │
├─────────┼────────┼───────────┤
│ Ana     │ 400.50 │    233.88 │
│ Bo      │ 310.00 │    233.88 │
└─────────┴────────┴───────────┘

The average is 233.88 rather than 286.83 because per_customer groups by customer_id before the join to customers — so order 108’s NULL customer contributes a fourth total of 75.00 to the average, then disappears from the output. Reading the number back and asking “average of how many customers?” is what surfaces it. Whether that row belongs in scope is a question for the interviewer.

Each CTE can be run alone. That is the practical argument, and the one to use in an interview: SELECT * FROM per_customer is a valid query, so you can verify each step before composing them. A nested subquery has to be unpicked before it can be tested.

CTEs are not a performance fence any more

EXPLAIN
WITH big AS (SELECT * FROM orders)
SELECT count(*) FROM big WHERE status = 'shipped';
┌───────────────────────────┐
│       Physical Plan       │
├───────────────────────────┤
│    UNGROUPED_AGGREGATE    │
│    count_star()           │
│              │            │
│         PROJECTION        │
│              │            │
│         SEQ_SCAN          │
│          orders           │
│   Filters: status='shipped'│
└───────────────────────────┘

The filter was pushed into the scan — the CTE did not force orders to be materialised first.

PostgreSQL behaved differently before version 12: every CTE was an optimisation fence, materialised whole. That is where “CTEs are slow” comes from, and it is now nine years out of date. From 12 onward:

WITH big AS MATERIALIZED   (SELECT * FROM orders) ...   -- force the old behaviour
WITH big AS NOT MATERIALIZED (SELECT * FROM orders) ... -- force inlining

Materialising deliberately is occasionally right — when a CTE is expensive and referenced three times, computing it once beats inlining it three times.

Correlated subqueries run per row

-- correlated: the inner query references the outer row
SELECT c.name,
       (SELECT count(*) FROM orders o WHERE o.customer_id = c.customer_id) AS order_count,
       (SELECT max(o.amount) FROM orders o WHERE o.customer_id = c.customer_id) AS biggest
FROM customers c ORDER BY c.name;
┌─────────┬─────────────┬─────────┐
│  name   │ order_count │ biggest │
├─────────┼─────────────┼─────────┤
│ Ana     │           3 │  200.00 │
│ Bo      │           2 │  310.00 │
│ Cy      │           1 │   45.00 │
│ Di      │           1 │  150.00 │
│ Eve     │           0 │    NULL │
│ Fay     │           0 │    NULL │
└─────────┴─────────────┴─────────┘

That result is correct and includes the zero-order customers for free — a genuine advantage over a join, which needs LEFT JOIN plus count(col).

The cost is two subqueries per customer. With six customers that is twelve inner executions; with a million it is two million. The join version is one pass:

SELECT c.name, count(o.order_id) AS order_count, max(o.amount) AS biggest
FROM customers c LEFT JOIN orders o USING (customer_id)
GROUP BY c.name ORDER BY c.name;
┌─────────┬─────────────┬─────────┐
│  name   │ order_count │ biggest │
├─────────┼─────────────┼─────────┤
│ Ana     │           3 │  200.00 │
│ Bo      │           2 │  310.00 │
│ Cy      │           1 │   45.00 │
│ Di      │           1 │  150.00 │
│ Eve     │           0 │    NULL │
│ Fay     │           0 │    NULL │
└─────────┴─────────────┴─────────┘

“Two scalar subqueries in the SELECT list means two inner executions per outer row unless the planner rewrites them. On six rows it does not matter; on a million-row customers table I’d use the LEFT JOIN, which is one pass. EXISTS and IN usually get rewritten into semi-joins; a scalar subquery in SELECT often does not.”

Saying that unprompted is what the “awareness” criterion from the intro is scored on.

EXISTS versus IN versus JOIN

-- three ways to ask "customers who have ordered"
SELECT name FROM customers c
WHERE EXISTS (SELECT 1 FROM orders o WHERE o.customer_id = c.customer_id)
ORDER BY name;

SELECT name FROM customers
WHERE customer_id IN (SELECT customer_id FROM orders)
ORDER BY name;

SELECT DISTINCT c.name FROM customers c
JOIN orders o USING (customer_id) ORDER BY c.name;
┌─────────┐     ┌─────────┐     ┌─────────┐
│  name   │     │  name   │     │  name   │
├─────────┤     ├─────────┤     ├─────────┤
│ Ana     │     │ Ana     │     │ Ana     │
│ Bo      │     │ Bo      │     │ Bo      │
│ Cy      │     │ Cy      │     │ Cy      │
│ Di      │     │ Di      │     │ Di      │
└─────────┘     └─────────┘     └─────────┘

Identical here. The differences that matter:

  • EXISTS stops at the first match — it is a semi-join, and it is NULL-safe. Prefer it.
  • IN with a NULL is safe for the positive case; NOT IN with a NULL is not, as the joins lesson showed.
  • JOIN needs DISTINCT because a customer with three orders would appear three times. The DISTINCT is the tell that a join is being used for an existence check — usually a sign that EXISTS was the right tool.

Recursive CTEs: walking a hierarchy

CREATE TABLE employees (id INTEGER, name VARCHAR, manager_id INTEGER);
INSERT INTO employees VALUES
    (1, 'Root',   NULL),
    (2, 'Ana',    1), (3, 'Bo',   1),
    (4, 'Cy',     2), (5, 'Di',   2), (6, 'Eve', 3),
    (7, 'Fay',    4);

WITH RECURSIVE chain AS (
    SELECT id, name, manager_id, 1 AS depth, name AS path
    FROM employees WHERE manager_id IS NULL          -- anchor
  UNION ALL
    SELECT e.id, e.name, e.manager_id, c.depth + 1, c.path || ' > ' || e.name
    FROM employees e JOIN chain c ON e.manager_id = c.id   -- recursive step
)
SELECT depth, name, path FROM chain ORDER BY path;
┌───────┬─────────┬──────────────────────┐
│ depth │  name   │         path         │
├───────┼─────────┼──────────────────────┤
│     1 │ Root    │ Root                 │
│     2 │ Ana     │ Root > Ana           │
│     3 │ Cy      │ Root > Ana > Cy      │
│     4 │ Fay     │ Root > Ana > Cy > Fay│
│     3 │ Di      │ Root > Ana > Di      │
│     2 │ Bo      │ Root > Bo            │
│     3 │ Eve     │ Root > Bo > Eve      │
└───────┴─────────┴──────────────────────┘

The structure is always the same three parts:

WITH RECURSIVE name AS (
    <anchor: the starting rows, no self-reference>
  UNION ALL
    <recursive step: joins the table to `name` itself>
)

The engine runs the anchor, then runs the recursive step against only the rows produced by the previous iteration, until an iteration produces nothing.

Infinite recursion, and the guard

INSERT INTO employees VALUES (8, 'Loop', 9), (9, 'Back', 8);   -- a cycle

WITH RECURSIVE chain AS (
    SELECT id, name, manager_id, 1 AS depth FROM employees WHERE id = 8
  UNION ALL
    SELECT e.id, e.name, e.manager_id, c.depth + 1
    FROM employees e JOIN chain c ON e.manager_id = c.id
)
SELECT count(*) FROM chain;
Error: Binder Error: Recursive CTE exceeded maximum recursion depth

Two employees pointing at each other. The recursive step never returns empty, and only the engine’s depth limit stops it.

The guard is a depth counter you enforce yourself:

WITH RECURSIVE chain AS (
    SELECT id, name, manager_id, 1 AS depth FROM employees WHERE id = 8
  UNION ALL
    SELECT e.id, e.name, e.manager_id, c.depth + 1
    FROM employees e JOIN chain c ON e.manager_id = c.id
    WHERE c.depth < 10                                    -- the guard
)
SELECT id, name, depth FROM chain ORDER BY depth;
┌───────┬─────────┬───────┐
│  id   │  name   │ depth │
├───────┼─────────┼───────┤
│     8 │ Loop    │     1 │
│     9 │ Back    │     2 │
│     8 │ Loop    │     3 │
│     9 │ Back    │     4 │
│     8 │ Loop    │     5 │
│     9 │ Back    │     6 │
│     8 │ Loop    │     7 │
│     9 │ Back    │     8 │
│     8 │ Loop    │     9 │
│     9 │ Back    │    10 │
└───────┴─────────┴───────┘

It terminates, and the repetition makes the cycle visible — which is often the actual goal. UNION instead of UNION ALL deduplicates and terminates on its own; carrying a visited path and checking NOT contains(path, e.name) is the version that reports where the cycle is.

“Any recursive CTE on data that could contain a cycle needs a depth guard. I add one by default and treat hitting it as a data quality alert, not a query bug.”

Generating a series

WITH RECURSIVE dates AS (
    SELECT DATE '2024-03-01' AS d
  UNION ALL
    SELECT d + INTERVAL 1 DAY FROM dates WHERE d < DATE '2024-03-05'
)
SELECT d::DATE AS day,
       coalesce(count(o.order_id), 0) AS orders
FROM dates LEFT JOIN orders o ON o.order_date = dates.d
GROUP BY d ORDER BY d;
┌────────────┬────────┐
│    day     │ orders │
├────────────┼────────┤
│ 2024-03-01 │      1 │
│ 2024-03-02 │      0 │
│ 2024-03-03 │      0 │
│ 2024-03-04 │      0 │
│ 2024-03-05 │      0 │
└────────────┴────────┘

Generating a complete date spine and LEFT JOINing to it is how you get zero rows for days with no activity — the thing a plain GROUP BY order_date can never produce, because absent days have no rows to group.

PostgreSQL has generate_series(start, stop, interval) and DuckDB has both; the recursive form works everywhere and is worth knowing for that reason.

Recognising it

SIGNAL                                          TOOL
query has more than one logical step            CTE per step, named
same subquery used twice                        one CTE, referenced twice
"does a related row exist"                      EXISTS — semi-join, NULL-safe
"does no related row exist"                     NOT EXISTS — never NOT IN
"a value from a related row, per row"           correlated scalar subquery, or a join
org chart, category tree, bill of materials     recursive CTE
"every day / month, including empty ones"       generate a spine, LEFT JOIN to it
graph traversal, shortest path in SQL           recursive CTE with a depth guard
CTE referenced 3+ times and expensive           MATERIALIZED (PostgreSQL 12+)

Practice

1. Rewrite a three-level nested subquery as CTEs. 
Each CTE runs alone: SELECT * FROM per_customer;

Same plan on any modern engine, and every step is independently testable. Readability is a scored criterion, not a style preference.

2. EXPLAIN a query wrapped in a CTE. 
Filters: status='shipped'   — pushed into the scan

The CTE was inlined. PostgreSQL before 12 materialised every CTE, which is where the “CTEs are slow” reputation comes from.

3. Put two scalar subqueries in the SELECT list. 
Two inner executions per outer row — 2 million on a million-row table.

Correct, and it gives zero-order customers for free. The LEFT JOIN version is one pass. Name the tradeoff rather than picking silently.

4. Run a recursive CTE over data containing a cycle. 
Binder Error: Recursive CTE exceeded maximum recursion depth

Add WHERE depth < N to the recursive step. Hitting the guard is a data quality signal, not a query bug.

Next: dates, cohorts and retention — the questions that look like SQL and are really calendar arithmetic.

Frequently Asked Questions

Are CTEs slower than subqueries?
Not in modern PostgreSQL, DuckDB, SQL Server, or MySQL 8 — the planner inlines them. PostgreSQL before version 12 materialised every CTE as an optimisation fence, which is where the reputation comes from; from 12 onward it inlines unless you write `MATERIALIZED`. Say which version you are assuming if it comes up.
When is a correlated subquery a problem?
When the planner cannot rewrite it into a join, it executes once per outer row — a thousand outer rows become a thousand inner queries. EXISTS and IN are usually rewritten; a scalar subquery in the SELECT list often is not. Check with EXPLAIN rather than assuming either way.
What does a recursive CTE actually do?
It runs the anchor query once, then repeatedly runs the recursive query against the rows produced by the previous iteration, until an iteration returns nothing. It is how you walk an org chart, a category tree, a graph, or generate a series of dates.
Why did my recursive CTE run forever?
Either the recursive step never returns an empty result — commonly a cycle in the data — or you wrote UNION ALL where the row set never shrinks. Add a depth counter with a limit, or use UNION instead of UNION ALL to deduplicate. Most engines have a recursion depth setting as a backstop.