Subqueries

Queries inside queries. Scalar subqueries, and SQLite's habit of quietly using the first row when a scalar subquery returns 427; IN and EXISTS and the joins they are equivalent to, which count 1,210 statin users where a plain join counts 1,217; NOT IN against NOT EXISTS when the subquery holds a NULL, a difference of 0 drugs against 475; correlated subqueries and their rewrites as a window function and a join; derived tables and common table expressions; and recursive common table expressions, used here to generate the empty bins of a histogram. On the NHANES 2017-2018 database in SQLite.

Of the 5,247 adults with a measured blood pressure, how many are above the average? The question has two steps, compute the average and then compare each adult with it, and SQL lets the first step be written inside the second:

SELECT COUNT(*) AS above_mean
FROM adult_bp
WHERE sbp > (SELECT AVG(sbp) FROM adult_bp);     -- 2,247

The parenthesized SELECT is a subquery. It returns the mean systolic pressure, 126.36 mm Hg, and the outer query counts the 2,247 adults above it. (adult_bp is a view with one row per adult: person number, sex, age and mean systolic pressure over up to three readings, as built in Aggregate Functions.)

A query's result is a table (Simple SQL Queries), and a subquery is a query used wherever a value, a list or a table is expected. This article covers the three uses, the difference between a subquery that runs once and one that runs for every row, the EXISTS and NOT EXISTS tests and the trap in NOT IN, and common table expressions, which name subqueries and, in their recursive form, let SQL generate rows it does not store.

Scalar subqueries

A subquery that returns one row and one column is a scalar subquery and can be used anywhere a single value can: in WHERE, as above, or in the SELECT list, where it adds the same value to every row:

SELECT seqn, sbp, sbp - (SELECT AVG(sbp) FROM adult_bp) AS above_mean
FROM adult_bp;

The first adult in the file, person 93705, has a mean systolic pressure of 202 and is 75.64 above the mean.

What happens when a scalar subquery does not return exactly one row differs between databases. With no rows, the value is NULL in SQLite and in PostgreSQL. With more than one row, PostgreSQL, following the standard, raises an error: its documentation states that "It is an error to use a query that returns more than one row or more than one column as a scalar subquery" (PostgreSQL Global Development Group, n.d.-a). SQLite does not: "The value of a subquery expression is the first row of the result from the enclosed SELECT statement" (SQLite, n.d.-a). So

SELECT (SELECT seqn FROM person WHERE age = 80);   -- 93768

returns one person number, without complaint, although 427 people are aged 80. A subquery meant to look up one value by a key that turns out not to be unique gives a silently arbitrary answer in SQLite and an error elsewhere. Aggregating inside the subquery (MAX, COUNT) or filtering on a primary key makes the single row certain.

IN and EXISTS

Subqueries that return a list

A subquery after IN returns a column of values, and the outer row is kept if its value is among them. People taking a statin:

SELECT COUNT(*) FROM person
WHERE seqn IN (SELECT p.seqn
               FROM prescription AS p JOIN drug AS d USING (drug_id)
               WHERE d.name LIKE '%STATIN' AND d.name <> 'NYSTATIN');   -- 1,210

(The name pattern and the exclusion of nystatin, an antifungal, are explained in Special Operators and Clauses.) The subquery returns the person number of every statin prescription; the outer query keeps each person once, however often their number appears in the list.

EXISTS

EXISTS (subquery) is true when the subquery returns at least one row; what the rows contain does not matter, so the subquery is often written SELECT 1 (SQLite, n.d.-a). The same question in this form:

SELECT COUNT(*) FROM person AS pe
WHERE EXISTS (SELECT 1
              FROM prescription AS p JOIN drug AS d USING (drug_id)
              WHERE p.seqn = pe.seqn
                AND d.name LIKE '%STATIN' AND d.name <> 'NYSTATIN');   -- 1,210

The subquery refers to pe.seqn, a column of the outer query, so it is evaluated for each person; it is a correlated subquery, discussed below. IN asks "is this value in that list?"; EXISTS asks "is there a matching row?". For most questions they are interchangeable, and modern planners often turn one into the other.

Their relation to joins

Both forms are semi-joins: they keep rows of the outer table that have a match, each at most once. An inner join is not a semi-join, because it returns a row for every match:

Query Result
IN (subquery) 1,210 people
EXISTS (subquery) 1,210 people
JOIN, COUNT(*) 1,217 rows
JOIN, COUNT(DISTINCT pe.seqn) 1,210 people

A few people report more than one statin prescription, and the join repeats them, adding seven rows. For a count the repair is DISTINCT, but for anything averaged over the joined rows the duplicates change the answer. The mean total cholesterol of statin users with a cholesterol result is 169.50 mg/dL over 1,088 people with IN, and 169.41 over 1,093 rows with a join, in which the repeated people count more than once. The difference here is small; Join Queries shows the same mechanism move a mean blood pressure by more than a millimeter. When the question is whether a match exists, a semi-join states it exactly.

Rewriting a subquery as a join is sometimes recommended for speed, on the grounds that a join is optimized as a whole. The steps are to move the subquery's table into the outer FROM clause, turn the link between the queries into a join condition, and add DISTINCT if the join can repeat outer rows. The last step is the one that is easy to forget and, as the table shows, it is not enough when the query computes more than counts. Current planners also do much of this work themselves. SQLite's plan for the IN query evaluates the subquery once into a list (and in SQLite 3.49 adds a Bloom filter to speed up lookups), and its documentation describes how it flattens subqueries in the FROM clause into the outer query, under a long list of conditions, because "performance of complex queries and/or queries involving views tends to suffer if query flattening is more conservative" (SQLite, n.d.-c). The clearer formulation is usually the better starting point, with EXPLAIN QUERY PLAN consulted if it turns out slow.

NOT IN and NOT EXISTS

The negations are where the forms part company. The question: how many of the 666 drugs in the database does no child take? The 1,082 prescriptions reported for people under 18 include 23 recorded only as an unknown, refused or don't-know code, whose drug_id is NULL.

SELECT COUNT(*) FROM drug
WHERE drug_id NOT IN (SELECT p.drug_id
                      FROM prescription AS p JOIN person AS pe USING (seqn)
                      WHERE pe.age < 18);                                     -- 0

SELECT COUNT(*) FROM drug AS d
WHERE NOT EXISTS (SELECT 1
                  FROM prescription AS p JOIN person AS pe USING (seqn)
                  WHERE pe.age < 18 AND p.drug_id = d.drug_id);              -- 475

The NOT EXISTS query finds 475 drugs that no child takes, which with the 191 that some child takes accounts for all 666. The NOT IN query finds none. For a drug that no child takes, drug_id NOT IN (list) means drug_id <> x for every x in the list, and one of those x is NULL, so the condition is unknown rather than true for every drug, and every drug is dropped. The SQLite documentation's table of IN results gives exactly this: when the right operand contains NULL and the left value is not found, both IN and NOT IN are NULL (SQLite, n.d.-a). Special Operators and Clauses shows the same effect with a literal list.

The query does not look dangerous, the NULLs are not visible in it, and the answer, zero, is plausible enough to pass a quick check. Adding AND p.drug_id IS NOT NULL to the subquery repairs it and gives 475, but the safer habit is to use NOT EXISTS for anti-joins, because it tests for a matching row and a NULL never matches. A left join with an IS NULL test, shown in Join Queries, is equally safe.

Correlated subqueries

A subquery that refers to a column of the outer query is correlated. Its result depends on the outer row, so logically it is evaluated again for each row; the SQLite documentation says that "A correlated subquery is reevaluated each time its result is required. An uncorrelated subquery is evaluated only once and the result reused as necessary" (SQLite, n.d.-a). Comparing each adult's blood pressure with the mean for adults of the same sex and decade of age:

SELECT COUNT(*) AS above_group_mean
FROM adult_bp AS a
WHERE a.sbp > (SELECT AVG(b.sbp)
               FROM adult_bp AS b
               WHERE b.sex = a.sex AND b.age / 10 = a.age / 10);   -- 2,368

The aliases are essential: a is the outer adult and b ranges over the adults in the subquery, and without them sex and age would refer to the inner table only. Read literally, the query computes a group mean 5,247 times, once per adult, although there are only 16 groups. A database may cache or rewrite such work, but it is not obliged to; SQLite's plan here labels the subquery CORRELATED SCALAR SUBQUERY and re-evaluates it.

Two rewrites compute each group mean once. A window function places the group mean on every row (Aggregate Functions):

SELECT COUNT(*) FROM (
  SELECT sbp, AVG(sbp) OVER (PARTITION BY sex, age / 10) AS m FROM adult_bp)
WHERE sbp > m;                                                      -- 2,368

and a join to a grouped table does the same in standard SQL that predates window functions:

SELECT COUNT(*)
FROM adult_bp AS a
JOIN (SELECT sex, age / 10 AS decade, AVG(sbp) AS m
      FROM adult_bp GROUP BY sex, decade) AS g
  ON g.sex = a.sex AND g.decade = a.age / 10
WHERE a.sbp > g.m;                                                  -- 2,368

All three return 2,368. The correlated form reads most like the question and is fine on small tables; the other two scale better. A correlated scalar subquery in the SELECT list is also a convenient way to attach a count to each row, such as (SELECT COUNT(*) FROM prescription AS p WHERE p.seqn = pe.seqn) AS medicines, which gives 0 for people with no prescriptions where an inner join would drop them.

Subqueries in FROM: derived tables

A subquery in the FROM clause produces a table for the outer query to read, called a derived table. It is the standard way to aggregate in two steps, first to one row per person and then across people:

SELECT sex, COUNT(*) AS adults, ROUND(AVG(sbp), 2) AS mean_sbp
FROM (SELECT p.seqn, p.sex, AVG(r.sbp) AS sbp
      FROM person AS p JOIN bp_reading AS r USING (seqn)
      WHERE p.age >= 18 AND r.reading <= 3
      GROUP BY p.seqn, p.sex) AS per_person
GROUP BY sex;

This gives 125.37 mm Hg for 2,700 women and 127.41 for 2,547 men, the person-weighted means of Aggregate Functions, without a stored view. The SQL standard requires the derived table to have a name (AS per_person), and so do MySQL and SQL Server (MySQL, n.d.; Microsoft, n.d.); SQLite does not insist, and PostgreSQL allows the name to be omitted (PostgreSQL Global Development Group, n.d.-b). Naming it costs nothing and keeps the query portable.

Common table expressions

Nested derived tables become hard to read from the inside out. A common table expression (CTE) names a subquery before the main query, with WITH, and the main query then uses the name like a table. The SQLite documentation describes ordinary CTEs as acting "like temporary views that exist only for the duration of a single SQL statement" (SQLite, n.d.-b). Several can be defined in one WITH, and later ones can use earlier ones:

WITH per_person AS (
    SELECT seqn, AVG(sbp) AS sbp
    FROM bp_reading
    WHERE reading <= 3
    GROUP BY seqn
),
statin_users AS (
    SELECT DISTINCT p.seqn
    FROM prescription AS p JOIN drug AS d USING (drug_id)
    WHERE d.name LIKE '%STATIN' AND d.name <> 'NYSTATIN'
)
SELECT CASE WHEN s.seqn IS NULL THEN 'no statin' ELSE 'statin' END AS group_,
       COUNT(*) AS adults,
       ROUND(AVG(b.sbp), 2) AS mean_sbp,
       ROUND(AVG(l.chol), 2) AS mean_chol
FROM person AS pe
JOIN per_person AS b USING (seqn)
LEFT JOIN lab AS l USING (seqn)
LEFT JOIN statin_users AS s USING (seqn)
WHERE pe.age >= 40
GROUP BY group_;
group_ adults mean_sbp mean_chol
no statin 2,411 131.19 202.02
statin 1,091 134.12 169.14

Among adults aged 40 and over with a blood pressure reading, those taking a statin have a mean total cholesterol 33 mg/dL lower and a systolic pressure 3 mm Hg higher than those not taking one. The query reads top to bottom: define the people's blood pressure, define who takes a statin, then compare. The comparison itself illustrates why grouped differences need care (Exploring Data with Groups and Pivot Tables): statin users are older, 66.9 years on average against 58.0, and are taking the drug because their cholesterol was high, so neither difference is the effect of the drug.

CTEs are mainly a tool for readability. Whether the database evaluates a CTE once and stores the result or merges it into the main query depends on the system and version; SQLite decides for itself and accepts hints (AS MATERIALIZED, AS NOT MATERIALIZED) to override it (SQLite, n.d.-b).

Recursive common table expressions

One capability is new rather than a convenience. A CTE declared with WITH RECURSIVE may refer to itself, which lets a query generate rows that are not stored anywhere and walk trees and graphs. The SQLite documentation calls this "a capability that is not otherwise available in the SQL language" (SQLite, n.d.-b). The simplest example counts:

WITH RECURSIVE n(i) AS (
    SELECT 1                              -- initial row
    UNION ALL
    SELECT i + 1 FROM n WHERE i < 5       -- recursive step
)
SELECT i, i * i AS square FROM n;

It returns the integers 1 to 5 and their squares. The body is a compound select: an initial select that produces the starting rows, then UNION ALL, then a recursive select that refers to the CTE once. SQLite evaluates it with a queue: it runs the initial select, then repeatedly takes one row from the queue, runs the recursive select as if that row were the whole table, and adds the results to the queue, until the queue is empty (SQLite, n.d.-b). The WHERE i < 5 is what empties the queue; without a terminating condition the recursion runs until something else stops it.

A practical use is filling gaps. A histogram of adult BMI in bins five units wide, computed with GROUP BY, has a row only for bins that contain someone:

SELECT CAST(bmi / 5 AS INTEGER) * 5 AS lower, COUNT(*) AS adults
FROM exam JOIN person USING (seqn)
WHERE age >= 20 AND bmi IS NOT NULL
GROUP BY lower;

The result jumps from the bin starting at 70 to the one starting at 80: no adult has a BMI from 75 to 80, so that bin is not in the output, and a chart drawn from it would silently close the gap. Generating the bins first and joining the data to them puts the empty bin back:

WITH RECURSIVE bins(lower) AS (
    SELECT 10
    UNION ALL
    SELECT lower + 5 FROM bins WHERE lower < 85
)
SELECT b.lower, b.lower + 5 AS upper, COUNT(e.seqn) AS adults
FROM bins AS b
LEFT JOIN (SELECT e.seqn, e.bmi
           FROM exam AS e JOIN person AS p USING (seqn)
           WHERE p.age >= 20) AS e
  ON e.bmi >= b.lower AND e.bmi < b.lower + 5
GROUP BY b.lower;
lower upper adults
15 20 233
20 25 1,101
25 30 1,667
30 35 1,132
35 40 569
40 45 277
45 50 101
50 55 50
55 60 22
60 65 12
65 70 5
70 75 1
75 80 0
80 85 1
85 90 1

(and 3 adults in the bin from 10 to 15). COUNT(e.seqn) rather than COUNT(*) is what makes the empty bin 0 instead of 1: the left join produces one row for the empty bin with NULLs on the data side, and COUNT of a column skips them. The same pattern, a generated series left-joined to the data, fills missing dates in a time series and missing categories in a report. PostgreSQL has a built-in generate_series for the purpose; in SQLite and in portable SQL the recursive CTE does the job.

The other classic use is hierarchies: an employee table whose rows point to their managers, a parts list in which parts contain parts. Codd's own example of a relation with two columns drawn from the same domain was such a table, component, in which one part is a component of another, "a relation which plays a critical role in the parts explosion problem" (Codd, 1970). A recursive CTE starts from one part and repeatedly joins the table to the rows found so far, listing every component at every level. The SQLite documentation works through such queries on an organization chart and a family tree (SQLite, n.d.-b).

In Python

import sqlite3
import pandas as pd

con = sqlite3.connect("nhanes.db")
drugs_no_child_takes = pd.read_sql("""
    SELECT d.name FROM drug AS d
    WHERE NOT EXISTS (SELECT 1 FROM prescription AS p JOIN person AS pe USING (seqn)
                      WHERE pe.age < 18 AND p.drug_id = d.drug_id)
    ORDER BY d.name""", con)
len(drugs_no_child_takes)     # 475

# the anti-join in pandas
child_drugs = pd.read_sql("""SELECT p.drug_id FROM prescription AS p
                             JOIN person AS pe USING (seqn) WHERE pe.age < 18""", con)
drug = pd.read_sql("SELECT * FROM drug", con)
(~drug.drug_id.isin(child_drugs.drug_id)).sum()   # 475

isin in pandas does not use three-valued logic: a missing value in the list can match only a missing value in the column, and drug_id has none, so the negated isin behaves like NOT EXISTS, not like SQL's NOT IN. The numbers in this article are computed by tools/experiments/data-science/sql-subqueries.py in the site's repository.

References