Cumulative Employee Salary

Overview

The goal is to calculate a running total (or prefix sum) of salaries for employees based on the order of their id. For each row in the output, we need to sum the current employee's salary with the salaries of every employee whose id is smaller than the current one.

SQLite provides two primary ways to achieve this:

1. Correlated Subqueries: Recalculating the sum for every row (useful for understanding the logic).
2. Window Functions: A modern, optimized approach designed specifically for sequential calculations across a set of rows.

Straightforward / Naive SQL

A straightforward approach uses a correlated subquery. For every row in the main query, we trigger a "sub-query" that scans the table to find and sum all salaries where the id is less than or equal to the id of the current outer row.

SELECT 
  e1.id, 
  e1.name, 
  e1.salary,
  (
    SELECT SUM(e2.salary) 
    FROM p_cumul_employees e2 
    WHERE e2.id <= e1.id
  ) AS cumulative_salary
FROM p_cumul_employees e1
ORDER BY e1.id ASC;

Time complexity (typical): O(N²) — For each of the N rows in the outer table, SQLite must perform a scan (or index seek) of the inner table to sum previous records. Space / working set: O(N) — Result set storage and sorting.

Better / Optimized SQL

The modern and standard way to solve "running total" problems is using Window Functions. The SUM(...) OVER (...) syntax allows SQLite to iterate through the data once, maintaining an internal accumulator as it moves from row to row.

By specifying ORDER BY id within the OVER clause, SQLite creates a default window frame from the start of the partition up to the current row.

SELECT 
  id, 
  name, 
  salary,
  SUM(salary) OVER (ORDER BY id ASC) AS cumulative_salary
FROM p_cumul_employees
ORDER BY id ASC;

Time complexity (typical): O(N log N) — Dominated by the sort required for the ORDER BY clause. The actual summation pass is linear O(N). Space / working set: O(N) — To hold the sorted rows before calculating the window sum.

Why this works

• The Frame: In the optimized solution, SUM(salary) OVER (ORDER BY id) uses an implicit frame: RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW. This is exactly what is needed for a cumulative total.
• Performance: Unlike the naive approach which re-reads data multiple times (O(N²)), the window function approach is much more efficient because it remembers the sum from the previous row and simply adds the current row's salary to it.
• Tie-breaking: In this specific schema, id is a PRIMARY KEY, meaning there are no duplicate IDs. If id were not unique, using ORDER BY id in a window function would sum all salaries for the "tied" IDs at once at that step.