Advanced SQL: Window Functions, CTEs, and Subqueries Questions

Direct answer: A bill-of-materials (BOM) table describes which parts (children) go into building another part or product (the parent), and how many of each (qty). To roll up total cost for a top-level product, walk down the tree with a recursive common table expression (CTE), multiplying quantity along each path (2 of part A, each needing 3 of part B, means 6 of part B overall), then join the exploded quantities to a cost table and sum. A visited-path array, checked on every recursive step, stops a bad parent/child link from looping forever, exactly the same mechanism used for an org-chart cycle guard, just walking down a tree instead of up one.

Approach

Anchor at the root product's direct children; recursive term joins each intermediate component to its own children, multiplying the accumulated quantity at each step, and refuses to revisit any component already on the current path.

WITH RECURSIVE exploded AS (
  -- anchor: direct children of the root product
  SELECT
    b.parent_id AS root_id,
    b.child_id AS component_id,
    b.qty::numeric AS qty_needed,
    ARRAY[b.parent_id, b.child_id] AS visited
  FROM bill_of_materials b
  WHERE b.parent_id = :root_id

  UNION ALL

  -- recursive term: expand one level down, multiply quantities, guard cycles
  SELECT
    e.root_id,
    child.child_id,
    e.qty_needed * child.qty::numeric,
    e.visited || child.child_id
  FROM exploded e
  JOIN bill_of_materials child ON child.parent_id = e.component_id
  WHERE NOT (child.child_id = ANY (e.visited))
)
SELECT
  e.component_id,
  SUM(e.qty_needed) AS total_qty_required,
  cc.unit_cost,
  SUM(e.qty_needed) * cc.unit_cost AS component_cost
FROM exploded e
JOIN component_cost cc ON cc.component_id = e.component_id
GROUP BY e.component_id, cc.unit_cost
ORDER BY e.component_id;

Key points

• Multiplication, not addition, accumulates along a path: a product needing 2 of a sub-assembly that itself needs 3 of a raw part needs 6 of that raw part, not 2 + 3.
• SUM(e.qty_needed) in the final GROUP BY combines quantity contributed through every distinct path to the same component, which matters when a component is reachable more than one way through the tree (e.g., both directly under the root and indirectly through a sub-assembly).
• The visited-path array check (NOT (child.child_id = ANY (e.visited))) is the same cycle-guard pattern as an org-chart walk, just walking downward through children instead of upward through managers.

Worked example

bill_of_materials(parent_id, child_id, qty): product 1 needs 2 of part 10, and 1 of part 20 directly; part 10 needs 3 of part 100. component_cost: part 10 = 0 (a sub-assembly, not purchased directly), part 20 = 5, part 100 = 2.

Verified in PostgreSQL:

Part 100's quantity (6) is 2 (units of part 10 per product) × 3 (units of part 100 per part 10), confirming the multiplicative rollup. Total product cost = 0 + 5 + 12 = 17.

graph TD
  Product1["Product 1"] -->|qty 2| Part10["Part 10"]
  Product1 -->|qty 1| Part20["Part 20 ($5)"]
  Part10 -->|qty 3| Part100["Part 100 ($2)"]

Complexity
Worst case, a BOM tree with branching factor b and depth d expands to O(b^d) exploded rows before deduplication, because a recursive CTE re-derives every distinct path rather than reusing work across shared sub-trees (a plain recursive join does not memoize). An index on bill_of_materials(parent_id) keeps each individual recursive step an efficient lookup rather than a full scan, but it does not change that exponential worst case; for a genuinely deep or wide BOM, that worst case is the real constraint, not query planning.

Edge cases

• Cycle in the data (a bad edit makes part A a child of one of its own descendants): the visited-array check stops recursion the moment a component would revisit a node already on its own path, the same way it did for the org-chart cycle test; without a depth cap as a second line of defense, a query that (incorrectly) omitted the visited-array check entirely would not terminate on cyclic data.
• A component reachable via two different paths through the tree with different accumulated quantities: both paths are legitimately summed at the final GROUP BY; this is correct, not double counting, as long as the two paths represent genuinely separate physical usages.
• Fractional quantities and rounding: quantities are cast to numeric here to avoid integer-division truncation partway through a multi-level multiplication; decide the rounding point deliberately (round only the final cost, not intermediate quantities) to avoid compounding rounding error across many levels.

Trade-offs & pitfalls

Deep BOMs are memory- and CPU-heavy for a recursive CTE specifically because of the exponential-worst-case expansion above; a genuinely deep or frequently-queried BOM benefits from precomputing and persisting a flattened, transitive-closure table (updated when the BOM itself changes) rather than recomputing this recursive query on every cost lookup. This same "aggregate a multiplicative or additive quantity up (or down) a tree, with a cycle guard" competency recurs under several different domain names: rolling up account balances through an organizational hierarchy per reporting date, rolling up cumulative revenue through a product-category tree, and rolling up referral-network revenue to a bounded depth (comparable to an affiliate-commission structure capped at, say, 3 levels). The tree-walking and cycle-safety mechanics are identical across all of them; only the aggregation operator (multiply vs. sum) and the business meaning of the nodes change.

Direct answer: For each user, number the activity dates in order with ROW_NUMBER(), then subtract that row number (in days) from the actual date. Within one unbroken run of consecutive days, the date increases by exactly 1 each row while the row number also increases by exactly 1, so date - row_number is a constant for the entire run and jumps to a new constant the moment there's a gap. That constant is a ready-made, stable group id: group by it (per user) and aggregate to get each streak's start, end, and length.

Structured elaboration

Why the trick works, concretely. If a user is active on Jan 1, 2, 3 (three consecutive days), their row numbers are 1, 2, 3. date - row_number, expressed as date - (row_number * INTERVAL 1 day) so both sides are dates, gives Dec 31, Dec 31, Dec 31 for all three rows: the row number is climbing at exactly the same rate as the date, so the difference is invariant. The moment there's a gap (say the next activity is Jan 5, skipping Jan 4), the row number continues climbing by 1 (to 4) but the date jumps by 2, so date - row_number shifts to a new constant. Every row in a contiguous run shares one constant; every gap produces a new constant. That is why grouping by this value is safe and deterministic, unlike an arbitrary running counter that would need a separate flag-and-cumsum step (the LAG-based alternative below does exactly that instead).

WITH numbered AS (
  SELECT user_id, activity_date,
    ROW_NUMBER() OVER (PARTITION BY user_id ORDER BY activity_date) AS rn
  FROM activity
),
grouped AS (
  SELECT user_id, activity_date,
    activity_date - (rn * INTERVAL '1 day') AS island_id
  FROM numbered
)
SELECT user_id, island_id,
  MIN(activity_date) AS streak_start, MAX(activity_date) AS streak_end, COUNT(*) AS streak_length
FROM grouped
GROUP BY user_id, island_id
ORDER BY user_id, streak_start;

LAG-based equivalent. Instead of arithmetic on the date, compare each row directly to the previous one: flag a new streak whenever activity_date <> prev_date + 1, then take a running SUM of that flag as the group id. This produces the identical grouping, at the cost of one extra window pass; it generalizes more naturally when the gap rule is not a fixed "+1 day" (see below).

Worked example (executed in DuckDB). User 1's activity dates: Jan 1, 2, 3 (a 3-day streak), then Jan 5, 6 (a 2-day streak after a 1-day gap), then Jan 10 (an isolated day).

user_id | streak_start | streak_end | streak_length
1       | 2025-01-01   | 2025-01-03 | 3
1       | 2025-01-05   | 2025-01-06 | 2
1       | 2025-01-10   | 2025-01-10 | 1

The island_id values produced internally were three distinct dates (one per run), confirming the arithmetic correctly separated the three streaks without any explicit gap-detection logic.

Generalizing the same island logic

• Coarser granularity (3+ consecutive weeks). Replace "day" with "week": truncate each activity date to its week start (e.g. date_trunc('week', activity_date)), dedupe to one row per (user, week), then apply the identical date - row_number trick using INTERVAL '1 week' instead of '1 day'. The mechanism is unchanged; only the unit of contiguity changes.
• A per-user variable gap threshold. If "consecutive" means something other than a fixed 1-day gap per user (e.g. some users are only expected to be active every other day), the date-minus-row-number arithmetic trick stops applying cleanly, because it depends on the gap being a fixed, known constant. Switch to the LAG-based form and compare against a per-user threshold column instead of a literal + 1: CASE WHEN activity_date > prev_date + gap_threshold THEN 1 ELSE 0 END.
• A tolerance window on the contiguity test. If a single missed day should still count as "the same streak" (a grace-day rule), change the LAG comparison from <> prev_date + 1 to > prev_date + tolerance_days, i.e. only break the streak when the gap exceeds the tolerance, not on any gap at all.
• The same pattern on a non-boolean series. The identical island logic applies to "3+ consecutive days of declining revenue" or "consecutive growing-revenue days": instead of flagging by date contiguity, flag each row by CASE WHEN revenue < LAG(revenue) OVER (...) THEN 1 ELSE 0 END (a direction change breaks the streak) and take the running SUM of direction-changes as the group id. The grouping mechanism (a monotonically non-decreasing counter that only increments at a boundary) is exactly the same; only the definition of "boundary" changes.

Trade-offs & pitfalls

• Deduplicate same-day activity before ranking (GROUP BY user_id, activity_date first); otherwise a duplicate row inflates streak_length without representing a real extra day.
• The date-minus-row-number trick specifically needs a fixed, known step size (1 day, 1 week); once the gap rule is conditional or per-user, fall back to the LAG-and-cumulative-sum form, which handles any boundary condition you can express as a boolean.
• date - row_number only produces a stable id within one user's partition; always include user_id in the final GROUP BY, or two different users' unrelated streaks that happen to land on the same constant will merge.

Direct answer: Order each user's page views by time, use LEAD to look at the next event's page and timestamp, and keep rows where the current page is 'A', the next page is 'B', and the time between them is within 10 minutes. Because LEAD only looks at the immediately following row per user, this only matches A directly followed by B, not A followed eventually by B with other pages in between. Generalizing to a longer chain (a 3-step funnel) means chaining multiple LEAD calls, one per step, each with its own offset.

Structured elaboration

WITH ordered AS (
  SELECT user_id, page, viewed_at,
    LEAD(page) OVER (PARTITION BY user_id ORDER BY viewed_at) AS next_page,
    LEAD(viewed_at) OVER (PARTITION BY user_id ORDER BY viewed_at) AS next_viewed_at
  FROM page_views
)
SELECT user_id, viewed_at AS a_time, next_viewed_at AS b_time
FROM ordered
WHERE page = 'A' AND next_page = 'B'
  AND next_viewed_at <= viewed_at + INTERVAL '10 minutes';

Worked example (executed in DuckDB). User 1: A at 10:00, B at 10:05 (5-minute gap, qualifies). User 2: A at 11:00, B at 11:25 (25-minute gap, does not qualify).

user_id | a_time   | b_time
1       | 10:00:00 | 10:05:00

Only user 1 appears in the result: user 2's A-then-B pair is correctly excluded because 25 minutes exceeds the 10-minute window, even though B genuinely followed A in their event stream.

Generalizing to a longer chain (a 3-step funnel). Two workable shapes:

1. Stacked LEAD offsets in one CTE (common table expression: a named, temporary result set defined with WITH ... AS (...) that the rest of the query can reference like a table). LEAD(page, 1) and LEAD(viewed_at, 1) give the next event, LEAD(page, 2) and LEAD(viewed_at, 2) give the one after that. Filtering page = 'A' AND LEAD(page,1) = 'B' AND LEAD(page,2) = 'C' (plus a time bound between the first and last step) finds users whose next two events, in order, were exactly B then C.
2. Chained CTEs, one per step, each filtering down to users who completed the previous step, then joining forward to the next page within the window: a landing-page common table expression, then an add-to-cart one that self-joins to it on user_id and a time bound, then a purchase one the same way. This is more verbose but scales cleanly to N steps without adding a new LEAD(page, k) term for every step, and it reads closer to how a funnel is usually described ("how many made it from step 2 to step 3").

-- Stacked-LEAD version of a 3-step A -> B -> C funnel within 30 minutes total
WITH ordered AS (
  SELECT user_id, page, viewed_at,
    LEAD(page,1) OVER (PARTITION BY user_id ORDER BY viewed_at) AS p2,
    LEAD(viewed_at,1) OVER (PARTITION BY user_id ORDER BY viewed_at) AS t2,
    LEAD(page,2) OVER (PARTITION BY user_id ORDER BY viewed_at) AS p3,
    LEAD(viewed_at,2) OVER (PARTITION BY user_id ORDER BY viewed_at) AS t3
  FROM page_views
)
SELECT user_id, viewed_at AS a_time, t2 AS b_time, t3 AS c_time
FROM ordered
WHERE page = 'A' AND p2 = 'B' AND p3 = 'C'
  AND t3 <= viewed_at + INTERVAL '30 minutes';

Run against a 3-event chain for user 1 (A 10:00, B 10:05, C 10:12), this returns exactly that one row with a_time=10:00, b_time=10:05, c_time=10:12, confirming the offset chain correctly threads through all three steps in order.

Trade-offs & pitfalls

• Requiring the events to be immediately consecutive (via LEAD(...,1), LEAD(...,2)) is a strict funnel definition: a stray click on an unrelated page between A and B breaks the match. If the real requirement is "A eventually followed by B, other pages allowed in between," you need a different construction: the first B-or-later event after each A, found via a window frame or a self-join with a MIN, not sequential LEAD offsets.
• Stacked LEAD(page, k) terms don't scale gracefully past a handful of steps; a 10-step funnel is more maintainable as chained CTEs or a recursive approach than ten hardcoded LEAD(page, k) columns.
• Watch for a user who visits A multiple times in a row before B; this query matches every A immediately followed by B, so a user with A, A, B produces one qualifying pair (the second A to B), not necessarily the one you intended if you wanted "first A to first B" specifically.

A correlated subquery references a column from the outer query inside its own WHERE (or other) clause, so conceptually the database re-runs it once per outer row, substituting that row's values each time. A non-correlated subquery has no reference back to the outer query at all, so it's evaluated once, independent of how many outer rows exist, and its result is reused for every row. Using employees(emp_id, department_id, salary), a correlated subquery can put each employee's department average right next to their own salary; a non-correlated subquery is the right tool for a single, outer-row-independent value like the company-wide average.

Correlated example: salary next to department average

SELECT
  e.emp_id,
  e.department_id,
  e.salary,
  (
    SELECT AVG(d.salary)
    FROM employees d
    WHERE d.department_id = e.department_id   -- correlated: references the outer row
  ) AS dept_avg_salary
FROM employees e
ORDER BY e.department_id, e.emp_id;

The inner query's WHERE d.department_id = e.department_id is what makes this correlated: e comes from the outer query, so the average has to be recomputed (conceptually) for every distinct department that appears in the outer rows.

Non-correlated example: a different, single-value comparison

SELECT emp_id, department_id, salary
FROM employees
WHERE salary > (
  SELECT AVG(salary) FROM employees   -- non-correlated: no reference to the outer row
);

The inner SELECT AVG(salary) FROM employees never mentions the outer table, so it produces one number, computed once, and every outer row is compared against that same value.

Key points

• The defining test is a reference, not the shape: a subquery becomes correlated the moment it uses a column from an outer table in its own filter or expression.
• A correlated scalar subquery in the SELECT list (as above) must return at most one row per outer row, or the database raises an error at runtime; the department-average query is safe because AVG() always collapses to one value.
• Real engines don't literally re-execute a correlated subquery row by row in every plan; a good optimizer can often rewrite it into a join or semi-join internally. "Conceptually re-runs per row" describes the logical semantics you should reason about when writing the query, not a guarantee about the physical execution plan.

Complexity

Logically, a correlated subquery costs O(rows in outer query) times O(cost of one inner-query execution). Whether that's actually slow depends entirely on whether the optimizer can turn it into a join or hash-based plan instead of a literal nested loop; an unindexed correlated lookup against a large table is the case where the naive per-row cost is real and painful. The non-correlated subquery costs O(1) execution of the inner query plus O(rows) for the outer comparison, since the inner result is just a constant once computed.

Worked example

With five employees across two departments (department 10: salaries 60000, 80000, 70000; department 20: salaries 50000, 90000), the correlated query above gives every department-10 employee a dept_avg_salary of 70000 and every department-20 employee 70000 as well (their department average happens to also be 70000: (50000+90000)/2). The non-correlated query, filtering against the company-wide average of 70000 ((60000+80000+70000+50000+90000)/5), returns exactly the two employees earning above it: the 80000 earner in department 10 and the 90000 earner in department 20. (Verified by executing both queries against SQLite 3.51 with this exact data.)

Trade-offs and pitfalls

For simple, single-value lookups and department-style row-level comparisons, either form works and correlated subqueries are often the most readable option. At production scale, prefer rewriting the correlated form as a JOIN against a pre-aggregated GROUP BY subquery or CTE (common table expression), or as an equivalent window function (AVG(salary) OVER (PARTITION BY department_id)), especially once you've checked EXPLAIN and confirmed the optimizer isn't already rewriting it for you; large, unindexed correlated subqueries are the classic case where a query silently degrades from fast in a small test dataset to slow in production.

A window function computes each row's result from raw input values visible inside its frame (the slice of rows defined by PARTITION BY/ORDER BY/the frame bounds); it cannot reference the output that another invocation of itself produced for a previous row. An exponentially weighted running value, such as an exponential moving average (EMA), is defined by $EMA_t = \alpha \, x_t + (1-\alpha)\, EMA_{t-1}$, where each row's result depends on the previous row's already-computed result, not just the previous row's raw x. That is a genuine recurrence relation, and standard window functions have no mechanism to feed a row's own output back in as an input to the next row. A recursive CTE (common table expression, a WITH block that references itself) can express this because each recursive step explicitly carries forward the prior step's computed value.

Why window functions can't do this

SUM(...) OVER (ORDER BY t ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) looks similar to a running EMA, but it only ever combines raw x values in the frame with a fixed operator (sum); it never lets one row's already-computed window-function result feed into the formula for the next row. The EMA recurrence needs exactly that feedback loop, so it falls outside what OVER (...) frames are built to express.

There is an escape hatch when the recurrence has a constant decay factor like EMA's: unroll it algebraically into a plain weighted sum over all prior rows, which is expressible as an ordinary window aggregate. Setting $r = 1-\alpha$ and unrolling from a seed of $EMA_0 = 0$ gives

$EMA_t = \alpha \sum_{i=1}^{t} r^{\,t-i}\, x_i.$

The exponent $t-i$ splits into a part that depends on $t$ and a part that depends on $i$:

$r^{\,t-i} = r^{t} \cdot r^{-i}.$

Since $r^{t}$ does not depend on the summation index $i$, it can be factored outside the sum:

$EMA_t = \alpha \, r^{t} \sum_{i=1}^{t} r^{-i}\, x_i.$

Substituting $y_i = x_i \, r^{-i}$ for the piece left inside the sum turns the geometric weights into a plain running sum:

$EMA_t = \alpha \, r^{t} \sum_{i=1}^{t} y_i.$

That inner sum is an ordinary ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW window SUM, so the whole thing can be computed in one pass without recursion:

WITH ordered AS (
  SELECT t, x, ROW_NUMBER() OVER (ORDER BY t) AS rn
  FROM series
),
scaled AS (
  SELECT rn, t, x, x * POWER(0.5, -rn) AS y   -- r = 1 - alpha = 0.5 here
  FROM ordered
)
SELECT
  t, x,
  0.5 * POWER(0.5, rn)
    * SUM(y) OVER (ORDER BY rn ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS ema
FROM scaled
ORDER BY rn;

This closed-form rewrite is faster (one linear pass, fully set-based, no recursion cap to worry about) but it is numerically fragile: r^{-i} grows without bound as i increases (since r < 1), so for a long series it overflows or loses precision in floating point long before the recursive version would. It also only works because the recurrence is linear with a constant decay; a recurrence whose next-step formula depends on more than "previous output plus current input" (a conditional reset, a variable decay, a cap) generally has no such closed form and needs either a recursive CTE or a genuine iterative/procedural pass outside plain SQL.

Guardrails before shipping a recursive CTE to production

Worked example

With $\alpha = 0.5$ and inputs x = [10, 20, 15, 30, 25] for t = 1..5, evaluating the recurrence step by step gives EMA = [5.0, 12.5, 13.75, 21.875, 23.4375]. Running both the recursive-CTE form and the closed-form window-SUM rewrite above against this exact data (verified against SQLite 3.51, which supports both WITH RECURSIVE and window functions) reproduces this identical sequence row for row, confirming the algebraic unrolling is correct, not just plausible.

Complexity

The recursive CTE does O(n) work total (one recursive step per row) but is strictly sequential: step t cannot start until step t-1's value is known, so it cannot be parallelized across rows the way a normal aggregate can, and most engines evaluate it row-at-a-time rather than in a vectorized batch. The closed-form window rewrite is also O(n), but as a single ordered pass with a standard running SUM, which query engines vectorize and optimize far more aggressively; the cost is the numerical-precision risk described above, which grows with n.

Trade-offs and pitfalls

Reach for the recursive CTE, not the closed-form rewrite, whenever the recurrence isn't a clean constant-decay geometric series (variable alpha, resets, caps, branching logic), when the series is long enough that r^{-i} would over/underflow, or when the team needs the logic to stay obviously correct and auditable rather than "algebraically clever." Reach for the closed-form rewrite when you've confirmed the recurrence really is linear-with-constant-decay, the series length is bounded enough to stay numerically safe, and the query needs to run as one set-based pass in an engine (or a business intelligence, BI, tool) that doesn't want a recursive CTE in its execution plan at all. Either way, ship it with the guardrails above: an un-capped recursive CTE with no depth limit, no timeout, and no ordering guarantee is a production incident waiting for a data quality problem (a cycle, a runaway series, an unstable sort) to trigger it.