Case Study 1 — From O(n²) to One Pass: The Running Total Rewrite

A reporting query that computed running totals with a correlated subquery worked fine in testing and ground to a halt in production. Rewriting it as a window function changed the algorithm from quadratic to linear — same answer, hundreds of times faster.

Background

A finance dashboard showed cumulative revenue over time — for each day, the total revenue from the beginning of the year through that day. The original query computed each day's running total with a correlated subquery that re-summed all prior days:

-- Running total via correlated subquery   ⚠️ O(n²)
SELECT d.day,
       d.revenue,
       (SELECT SUM(d2.revenue)
        FROM daily_revenue d2
        WHERE d2.day <= d.day) AS running_total
FROM daily_revenue d
ORDER BY d.day;

For a 30-day month it was instant. For three years of daily data (~1,000 rows) it was sluggish; for the per-store version (thousands of series), it timed out. The complaint: "the cumulative report takes forever."

What went wrong: quadratic work

For each of the N rows, the correlated subquery scans and sums all prior rows — on average N/2 rows. That's N × N/2 ≈ N²/2 units of work. At 1,000 rows that's ~500,000 sum operations for a report that should be trivial; scale to tens of thousands of rows (multiple stores × years) and it's hundreds of millions. The algorithm, not the database, was the problem: computing a running total by re-summing the prefix at every row is inherently quadratic.

The fix: a window function (one pass)

A window function computes the running total in a single ordered pass, carrying the cumulative sum as it goes:

-- Running total via window function   ✅ O(n)
SELECT day,
       revenue,
       SUM(revenue) OVER (ORDER BY day
            ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS running_total
FROM daily_revenue
ORDER BY day;

(The explicit frame ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW is the cumulative frame; with ORDER BY day it's also the default, so SUM(revenue) OVER (ORDER BY day) is equivalent — the explicit form just documents intent.) The database sorts once by day, then sweeps through accumulating the sum — N units of work, not N². For the per-store version, add PARTITION BY store_id and each store's running total resets correctly, still in one pass.

The report dropped from a timeout to milliseconds. The numbers were identical; only the amount of work changed.

More than speed: clarity and correctness

The window version is also clearer and less error-prone. The correlated-subquery version has a subtle correctness trap: WHERE d2.day <= d.day includes ties (multiple rows on the same day) in a way that's easy to get wrong, and handling "running total per store" means threading a second correlation through. The window version expresses "cumulative over this order, within this partition" declaratively, and ties/partitions are handled by the frame and PARTITION BY — fewer places to make a mistake.

The analysis

  1. Correlated subqueries that re-scan a prefix are quadratic. Any "for each row, aggregate over the rows before it" written as a correlated subquery is O(n²). Running totals, ranks, "count of earlier rows," "previous value" — all of these are window-function jobs.

  2. Window functions do it in one pass. They sort once and sweep, computing rankings, running totals, and adjacent-row comparisons in O(n log n) (the sort) or O(n) if already ordered by an index. This is the algorithmic win.

  3. "Reaching for a self-join or correlated subquery to compare a row to others in its group" is the signal. When you catch yourself doing that, stop and ask: "is this a window function?" Almost always, yes.

  4. Small-data testing hides quadratic blowups. N² is invisible at N=30 and lethal at N=30,000. Test performance-sensitive analytics against realistic data volumes (load generate_data.sql).

  5. EXPLAIN ANALYZE confirms it (Chapter 24): the window version shows a single WindowAgg over a sort; the subquery version shows the inner aggregate re-executing per row. Reading the plan turns "it's slow" into "here's the quadratic step."

Discussion questions

  1. Explain why the correlated-subquery running total is O(n²) and the window version is effectively O(n).
  2. Rewrite the running total to reset per store. How much harder is that with the window function vs. the subquery?
  3. Why is SUM(revenue) OVER (ORDER BY day) equivalent to the explicit cumulative frame?
  4. What other "for each row, look at earlier rows" computations are really window-function jobs?
  5. ⭐ Are there cases where a correlated subquery is still the right tool over a window function? When?