Running totals with SUM OVER in SQL - Time & Space Complexity

Time Complexity: Running totals with SUM OVER

O(n^2)

Understanding Time Complexity

We want to understand how the time to calculate running totals grows as the data size increases.

How does the database handle summing values step-by-step for many rows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT
  order_id,
  order_date,
  amount,
  SUM(amount) OVER (ORDER BY order_date) AS running_total
FROM orders;
    

This query calculates a running total of order amounts ordered by date.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Summing amounts for each row up to that row.
• How many times: For each row, the database sums all previous rows in order.

How Execution Grows With Input

As the number of rows grows, the work to calculate each running total grows too.

Input Size (n)	Approx. Operations
10	About 55 sums (1+2+...+10)
100	About 5,050 sums
1000	About 500,500 sums

Pattern observation: The total work grows much faster than the number of rows, roughly like the square of the input size.

Final Time Complexity

Time Complexity: O(n^2)

This means the time to compute running totals grows roughly with the square of the number of rows.

Common Mistake

[X] Wrong: "Calculating running totals is always fast and grows linearly with data size."

[OK] Correct: Because each running total sums all previous rows, the work adds up quickly, making it slower than just reading each row once.

Interview Connect

Understanding how running totals scale helps you explain query performance and shows you can think about how databases handle data step-by-step.

Self-Check

"What if we added a PARTITION BY clause to reset running totals for each group? How would the time complexity change?"

Practice

1. What does the SQL expression SUM(amount) OVER (ORDER BY date) calculate?

easy

A. A running total of the amount column ordered by date

B. The total sum of amount for all rows without order

C. The average amount grouped by date

D. The maximum amount value in the table

Solution

1. Step 1: Understand SUM() with OVER()

   The SUM() function adds values, and OVER() defines how to apply it across rows.

2. Step 2: Analyze ORDER BY in OVER()

   ORDER BY date means the sum accumulates in date order, creating a running total.

3. Final Answer:

   A running total of the amount column ordered by date -> Option A

4. Quick Check:

   SUM() OVER(ORDER BY) = running total [OK]

Hint: SUM() with ORDER BY inside OVER() means running total [OK]

Common Mistakes:

• Thinking SUM() without OVER() gives running total
• Confusing running total with group total
• Ignoring ORDER BY inside OVER()

2. Which of the following is the correct syntax to calculate a running total of sales ordered by sale_date?

easy

A. SELECT sales, SUM(sales) OVER (PARTITION BY sale_date) FROM sales_table;

B. SELECT sales, SUM(sales) OVER (ORDER BY sale_date) FROM sales_table;

C. SELECT sales, SUM(sales) FROM sales_table ORDER BY sale_date;

D. SELECT sales, SUM(sales) OVER () ORDER BY sale_date FROM sales_table;

Solution

1. Step 1: Identify correct use of SUM() OVER()

   Running total requires SUM() OVER with ORDER BY clause inside OVER().

2. Step 2: Check each option's syntax

   SELECT sales, SUM(sales) OVER (ORDER BY sale_date) FROM sales_table; uses SUM(sales) OVER (ORDER BY sale_date), which is correct syntax for running total.

3. Final Answer:

   SELECT sales, SUM(sales) OVER (ORDER BY sale_date) FROM sales_table; -> Option B

4. Quick Check:

   SUM() OVER (ORDER BY ...) = running total syntax [OK]

Hint: Use SUM() OVER (ORDER BY column) for running totals [OK]

Common Mistakes:

• Using PARTITION BY instead of ORDER BY for running total
• Omitting OVER() clause
• Placing ORDER BY outside OVER()

3. Given the table sales_data with columns id, sale_date, and amount, what is the output of this query?

SELECT id, sale_date, amount, SUM(amount) OVER (ORDER BY sale_date) AS running_total FROM sales_data ORDER BY id;

Assume the data:
id | sale_date | amount
1 | 2024-01-01 | 100
2 | 2024-01-03 | 200
3 | 2024-01-02 | 150

medium

A. Running totals: 100, 350, 450 ordered by id

B. Running totals: 100, 150, 350 ordered by id

C. Running totals: 100, 450, 250 ordered by id

D. Running totals: 100, 300, 450 ordered by id

Solution

1. Step 1: Order rows by sale_date for running total

   Order by sale_date: id=1(2024-01-01), id=3(2024-01-02), id=2(2024-01-03).

2. Step 2: Calculate running total in sale_date order

   Running totals: 100 (id=1), 100+150=250 (id=3), 250+200=450 (id=2).

3. Step 3: Output ordered by id

   Order by id: id=1 (100), id=2 (450), id=3 (250).

4. Final Answer:

   Running totals: 100, 450, 250 ordered by id -> Option C

5. Quick Check:

   Running total sums in sale_date order, output sorted by id [OK]

Hint: Running total sums by ORDER BY inside OVER, output order separate [OK]

Common Mistakes:

• Assuming running total follows output ORDER BY
• Adding amounts in id order instead of sale_date order
• Confusing running total with simple sum

4. Identify the error in this query intended to calculate a running total of points ordered by game_date:

SELECT player_id, points, SUM(points) OVER (PARTITION BY player_id) ORDER BY game_date FROM game_scores;

medium

A. ORDER BY clause is outside the OVER() function

B. PARTITION BY cannot be used with SUM()

C. Missing GROUP BY clause

D. SUM() cannot be used with window functions

Solution

1. Step 1: Check placement of ORDER BY

   ORDER BY for running total must be inside OVER(), not outside the function.

2. Step 2: Understand correct syntax

   Correct syntax: SUM(points) OVER (PARTITION BY player_id ORDER BY game_date).

3. Final Answer:

   ORDER BY clause is outside the OVER() function -> Option A

4. Quick Check:

   ORDER BY must be inside OVER() for running totals [OK]

Hint: Put ORDER BY inside OVER() for running totals [OK]

Common Mistakes:

• Placing ORDER BY outside OVER()
• Confusing PARTITION BY with GROUP BY
• Thinking SUM() can't be window function

5. You have a sales table with columns region, sale_date, and amount. You want to calculate a running total of sales per region ordered by sale_date. Which query correctly achieves this?

hard

A. SELECT region, sale_date, amount, SUM(amount) OVER (ORDER BY sale_date) AS running_total FROM sales;

B. SELECT region, sale_date, amount, SUM(amount) OVER (PARTITION BY sale_date ORDER BY region) AS running_total FROM sales;

C. SELECT region, sale_date, amount, SUM(amount) FROM sales GROUP BY region, sale_date ORDER BY sale_date;

D. SELECT region, sale_date, amount, SUM(amount) OVER (PARTITION BY region ORDER BY sale_date) AS running_total FROM sales;

Solution

1. Step 1: Understand requirement for running total per region

   We need to reset running total for each region, so PARTITION BY region is required.

2. Step 2: Check ORDER BY for running total

   ORDER BY sale_date inside OVER() ensures running total accumulates by date within each region.

3. Step 3: Evaluate options

   SELECT region, sale_date, amount, SUM(amount) OVER (PARTITION BY region ORDER BY sale_date) AS running_total FROM sales; correctly uses PARTITION BY region and ORDER BY sale_date inside SUM() OVER().

4. Final Answer:

   SELECT region, sale_date, amount, SUM(amount) OVER (PARTITION BY region ORDER BY sale_date) AS running_total FROM sales; -> Option D

5. Quick Check:

   PARTITION BY region + ORDER BY sale_date = running total per region [OK]

Hint: Use PARTITION BY for groups, ORDER BY for running total order [OK]

Common Mistakes:

• Omitting PARTITION BY to separate groups
• Using GROUP BY instead of window functions
• Swapping ORDER BY columns inside OVER()