Running total without window functions in SQL - Time & Space Complexity

Time Complexity: Running total without window functions

O(n²)

Understanding Time Complexity

We want to understand how the time needed to calculate a running total grows as the data size increases.

How does the number of operations change when we sum values step-by-step without special functions?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT a.id, a.value,
  (SELECT SUM(b.value) FROM table1 b WHERE b.id <= a.id) AS running_total
FROM table1 a
ORDER BY a.id;

This code calculates a running total by summing all values up to the current row's id without using window functions.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: For each row, the inner query sums values from the start up to that row.
• How many times: The inner sum runs once for every row in the table.

How Execution Grows With Input

As the number of rows grows, the amount of work grows much faster because each new row sums more values.

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 roughly like the square of the number of rows.

Final Time Complexity

Time Complexity: O(n²)

This means if you double the number of rows, the work needed to calculate running totals roughly quadruples.

Common Mistake

[X] Wrong: "Calculating running totals like this only takes time proportional to the number of rows."

[OK] Correct: Because for each row, the query sums all previous rows, so the total work adds up much faster than just one pass.

Interview Connect

Understanding how nested queries affect performance helps you write better SQL and explain your reasoning clearly in interviews.

Self-Check

"What if we replaced the subquery with a window function like SUM() OVER()? How would the time complexity change?"

Practice

1. What is the main idea behind calculating a running total without using window functions in SQL?

easy

A. Use GROUP BY to group all rows together.

B. Use the SUM() function without any conditions.

C. Use a JOIN to combine unrelated tables.

D. Use a subquery to sum all previous rows up to the current row.

Solution

1. Step 1: Understand running total concept

   A running total means adding values step-by-step, including all previous rows up to the current one.

2. Step 2: Identify method without window functions

   Without window functions, a common way is to use a subquery that sums all rows with an ID less than or equal to the current row's ID.

3. Final Answer:

   Use a subquery to sum all previous rows up to the current row. -> Option D

4. Quick Check:

   Running total = cumulative sum using subquery [OK]

Hint: Think cumulative sum using subquery with condition [OK]

Common Mistakes:

• Using SUM() without filtering rows
• Trying to use GROUP BY for running total
• Confusing JOIN with running total calculation

2. Which of the following SQL queries correctly calculates a running total of the amount column without using window functions, assuming id orders the rows?

easy

A. SELECT id, amount, (SELECT SUM(amount) FROM sales WHERE id <= s.id) AS running_total FROM sales s ORDER BY id;

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

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

D. SELECT id, amount, amount + LAG(amount) FROM sales ORDER BY id;

Solution

1. Step 1: Identify correct syntax without window functions

   SELECT id, amount, (SELECT SUM(amount) FROM sales WHERE id <= s.id) AS running_total FROM sales s ORDER BY id; uses a correlated subquery summing amounts where id is less or equal to current row's id, which is correct for running total without window functions.

2. Step 2: Check other options for errors

   SELECT id, amount, SUM(amount) OVER (ORDER BY id) AS running_total FROM sales ORDER BY id; uses window function SUM() OVER, which is not allowed here. SELECT id, amount, SUM(amount) FROM sales GROUP BY id ORDER BY id; misuses GROUP BY without running total logic. SELECT id, amount, amount + LAG(amount) FROM sales ORDER BY id; uses LAG() which is a window function.

3. Final Answer:

   SELECT id, amount, (SELECT SUM(amount) FROM sales WHERE id <= s.id) AS running_total FROM sales s ORDER BY id; -> Option A

4. Quick Check:

   Subquery sums previous rows correctly [OK]

Hint: Look for subquery with condition id <= current id [OK]

Common Mistakes:

• Using window functions despite instructions
• Misusing GROUP BY without aggregation logic
• Using LAG() which is a window function

3. Given the table sales with rows:
id | amount
1 | 10
2 | 20
3 | 15
What is the output of this query?

SELECT id, amount, (SELECT SUM(amount) FROM sales WHERE id <= s.id) AS running_total FROM sales s ORDER BY id;

medium

A. 1 | 10 | 102 | 20 | 203 | 15 | 15

B. 1 | 10 | 102 | 20 | 303 | 15 | 45

C. 1 | 10 | 102 | 20 | 253 | 15 | 40

D. 1 | 10 | 102 | 20 | 303 | 15 | 15

Solution

1. Step 1: Calculate running total for each row

   For id=1: sum amounts where id <=1 is 10.
   For id=2: sum amounts where id <=2 is 10+20=30.
   For id=3: sum amounts where id <=3 is 10+20+15=45.

2. Step 2: Match calculated values with options

   1 | 10 | 10
   2 | 20 | 30
   3 | 15 | 45 matches these running totals exactly.

3. Final Answer:

   1 | 10 | 10
   2 | 20 | 30
   3 | 15 | 45 -> Option B

4. Quick Check:

   Running total sums all previous rows [OK]

Hint: Add amounts cumulatively by id order [OK]

Common Mistakes:

• Summing only current row amount
• Not including all previous rows in sum
• Mixing up running total values

4. Consider this query intended to calculate a running total:

SELECT id, amount, (SELECT SUM(amount) FROM sales WHERE id < s.id) AS running_total FROM sales s ORDER BY id;

What is the main issue with this query?

medium

A. It will cause a syntax error due to missing GROUP BY.

B. It uses window functions which are not allowed.

C. It excludes the current row's amount from the running total.

D. It sums amounts from unrelated tables.

Solution

1. Step 1: Analyze the subquery condition

   The subquery sums amounts where id is less than current row's id, so it excludes the current row's amount.

2. Step 2: Understand running total definition

   Running total should include the current row's amount, so condition should be id <= s.id, not id < s.id.

3. Final Answer:

   It excludes the current row's amount from the running total. -> Option C

4. Quick Check:

   Use id <= current id to include current row [OK]

Hint: Check if current row is included in sum condition [OK]

Common Mistakes:

• Using < instead of <= in subquery condition
• Expecting window functions in this query
• Assuming syntax error due to GROUP BY

5. You have a transactions table with columns trans_id, user_id, and amount. You want to calculate a running total of amount for each user_id ordered by trans_id, but you cannot use window functions. Which query correctly achieves this?

hard

A. SELECT t1.trans_id, t1.user_id, t1.amount, (SELECT SUM(t2.amount) FROM transactions t2 WHERE t2.user_id = t1.user_id AND t2.trans_id <= t1.trans_id) AS running_total FROM transactions t1 ORDER BY t1.user_id, t1.trans_id;

B. SELECT trans_id, user_id, amount, SUM(amount) OVER (PARTITION BY user_id ORDER BY trans_id) AS running_total FROM transactions ORDER BY user_id, trans_id;

C. SELECT trans_id, user_id, amount, SUM(amount) FROM transactions GROUP BY user_id, trans_id ORDER BY user_id, trans_id;

D. SELECT t1.trans_id, t1.user_id, t1.amount, (SELECT SUM(amount) FROM transactions WHERE trans_id <= t1.trans_id) AS running_total FROM transactions t1 ORDER BY user_id, trans_id;

Solution

1. Step 1: Understand requirement for per-user running total

   Running total must reset for each user_id and sum amounts up to current trans_id.

2. Step 2: Analyze options for correct filtering

   SELECT t1.trans_id, t1.user_id, t1.amount, (SELECT SUM(t2.amount) FROM transactions t2 WHERE t2.user_id = t1.user_id AND t2.trans_id <= t1.trans_id) AS running_total FROM transactions t1 ORDER BY t1.user_id, t1.trans_id; uses a correlated subquery filtering by same user_id and trans_id less or equal current, correctly calculating running total per user.

3. Step 3: Identify errors in other options

   SELECT trans_id, user_id, amount, SUM(amount) OVER (PARTITION BY user_id ORDER BY trans_id) AS running_total FROM transactions ORDER BY user_id, trans_id; uses window functions (not allowed). SELECT trans_id, user_id, amount, SUM(amount) FROM transactions GROUP BY user_id, trans_id ORDER BY user_id, trans_id; misuses GROUP BY without running total logic. SELECT t1.trans_id, t1.user_id, t1.amount, (SELECT SUM(amount) FROM transactions WHERE trans_id <= t1.trans_id) AS running_total FROM transactions t1 ORDER BY user_id, trans_id; sums amounts ignoring user_id, mixing all users.

4. Final Answer:

   SELECT t1.trans_id, t1.user_id, t1.amount, (SELECT SUM(t2.amount) FROM transactions t2 WHERE t2.user_id = t1.user_id AND t2.trans_id <= t1.trans_id) AS running_total FROM transactions t1 ORDER BY t1.user_id, t1.trans_id; -> Option A

5. Quick Check:

   Subquery filters by user and trans_id for running total [OK]

Hint: Filter subquery by user_id and trans_id <= current [OK]

Common Mistakes:

• Ignoring user_id in running total calculation
• Using window functions despite restriction
• Not ordering results properly