SUM, AVG, COUNT as window functions in PostgreSQL - Time & Space Complexity

Time Complexity: SUM, AVG, COUNT as window functions

O(n)

Understanding Time Complexity

We want to understand how the time to run window functions like SUM, AVG, and COUNT changes as the data grows.

How does the work needed grow when we have more rows in the table?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT employee_id, department_id, salary,
       SUM(salary) OVER (PARTITION BY department_id) AS dept_total_salary,
       AVG(salary) OVER (PARTITION BY department_id) AS dept_avg_salary,
       COUNT(*) OVER (PARTITION BY department_id) AS dept_employee_count
FROM employees;
    

This query calculates the total, average, and count of salaries for each department using window functions.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The database scans all rows once and computes aggregates per partition (department).
• How many times: Each row is processed once, but the window function groups rows by department and calculates aggregates over those groups.

How Execution Grows With Input

As the number of rows grows, the database does more work to group and aggregate salaries per department.

Input Size (n)	Approx. Operations
10	About 10 operations to scan and aggregate
100	About 100 operations, grouping by department
1000	About 1000 operations, still grouping by department

Pattern observation: The work grows roughly in direct proportion to the number of rows.

Final Time Complexity

Time Complexity: O(n)

This means the time to run these window functions grows linearly with the number of rows.

Common Mistake

[X] Wrong: "Window functions like SUM or AVG run a separate calculation for each row, so time grows much faster than the number of rows."

[OK] Correct: The database optimizes by grouping rows and calculating aggregates efficiently, so it does not repeat full calculations for each row.

Interview Connect

Understanding how window functions scale helps you explain query performance clearly and shows you know how databases handle grouped calculations efficiently.

Self-Check

"What if we removed the PARTITION BY clause? How would the time complexity change?"