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?"

Practice

1. What does the COUNT(*) OVER() window function do in PostgreSQL?

easy

A. Counts all rows in the result set without grouping them.

B. Counts only distinct rows in the table.

C. Counts rows and groups them by a specified column.

D. Counts rows but returns only one aggregated result.

Solution

1. Step 1: Understand COUNT(*) OVER() usage

   The function counts all rows in the query result but does not group or collapse rows.

2. Step 2: Difference from GROUP BY

   Unlike GROUP BY, it keeps all rows visible and adds the count as a column.

3. Final Answer:

   Counts all rows in the result set without grouping them. -> Option A

4. Quick Check:

   COUNT(*) OVER() counts all rows [OK]

Hint: Window COUNT(*) counts all rows without grouping [OK]

Common Mistakes:

• Confusing window COUNT with GROUP BY count
• Thinking it returns a single aggregated row
• Assuming it counts distinct values only

2. Which of the following is the correct syntax to calculate a running total of sales using SUM as a window function in PostgreSQL?

easy

A. SELECT sales, SUM(sales) OVER (ORDER BY date) AS running_total FROM sales_data;

B. SELECT sales, SUM(sales) FROM sales_data ORDER BY date;

C. SELECT sales, SUM(sales) PARTITION BY date FROM sales_data;

D. SELECT sales, SUM(sales) OVER PARTITION BY date FROM sales_data;

Solution

1. Step 1: Identify correct window function syntax

   SUM(sales) OVER (ORDER BY date) calculates cumulative sum ordered by date.

2. Step 2: Check other options for syntax errors

   The other options misuse window function syntax or omit OVER keyword.

3. Final Answer:

   SELECT sales, SUM(sales) OVER (ORDER BY date) AS running_total FROM sales_data; -> Option A

4. Quick Check:

   SUM() OVER (ORDER BY ...) is correct syntax [OK]

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

Common Mistakes:

• Omitting OVER() clause
• Using PARTITION BY without OVER()
• Confusing GROUP BY with window functions

3. Given the table employees with columns department and salary, what will the following query return?

SELECT department, salary, AVG(salary) OVER (PARTITION BY department) AS avg_dept_salary FROM employees;

medium

A. Syntax error due to missing GROUP BY clause.

B. Each row shows salary and overall average salary of all employees.

C. Each row shows salary and average salary of all departments combined.

D. Each row shows salary and average salary of its department.

Solution

1. Step 1: Understand PARTITION BY in AVG window function

   AVG(salary) OVER (PARTITION BY department) calculates average salary per department for each row.

2. Step 2: Confirm output per row

   Each row keeps salary and adds average salary of that row's department without grouping rows.

3. Final Answer:

   Each row shows salary and average salary of its department. -> Option D

4. Quick Check:

   AVG() OVER (PARTITION BY ...) averages per group per row [OK]

Hint: PARTITION BY groups rows but keeps all rows visible [OK]

Common Mistakes:

• Thinking it aggregates to one row per group
• Confusing window AVG with GROUP BY AVG
• Expecting overall average without PARTITION BY

4. Identify the error in this query:

SELECT employee_id, salary, COUNT(*) OVER PARTITION BY department FROM employees;

medium

A. COUNT(*) cannot be used as a window function.

B. Missing parentheses around PARTITION BY clause in OVER().

C. employee_id cannot be selected with window functions.

D. No error; query is correct.

Solution

1. Step 1: Check syntax of window function

   OVER clause must have parentheses: OVER (PARTITION BY department).

2. Step 2: Validate other parts

   COUNT(*) is valid as window function; selecting employee_id is allowed.

3. Final Answer:

   Missing parentheses around PARTITION BY clause in OVER(). -> Option B

4. Quick Check:

   OVER() requires parentheses [OK]

Hint: Always use parentheses after OVER keyword [OK]

Common Mistakes:

• Omitting parentheses in OVER()
• Thinking COUNT(*) can't be window function
• Assuming window functions require GROUP BY

5. You want to find the cumulative count of orders per customer ordered by order date. Which query correctly uses COUNT as a window function to achieve this?

hard

A. SELECT customer_id, order_date, COUNT(*) FROM orders GROUP BY customer_id, order_date ORDER BY order_date;

B. SELECT customer_id, order_date, COUNT(*) OVER (ORDER BY order_date) AS cumulative_orders FROM orders;

C. SELECT customer_id, order_date, COUNT(*) OVER (PARTITION BY customer_id ORDER BY order_date) AS cumulative_orders FROM orders;

D. SELECT customer_id, order_date, COUNT(*) OVER (PARTITION BY order_date ORDER BY customer_id) AS cumulative_orders FROM orders;

Solution

1. Step 1: Understand cumulative count per customer

   COUNT(*) OVER (PARTITION BY customer_id ORDER BY order_date) counts rows per customer in order of order_date cumulatively.

2. Step 2: Check other options for correctness

   SELECT customer_id, order_date, COUNT(*) FROM orders GROUP BY customer_id, order_date ORDER BY order_date; uses GROUP BY, not cumulative count; C lacks partition by customer; D partitions by order_date, not customer.

3. Final Answer:

   SELECT customer_id, order_date, COUNT(*) OVER (PARTITION BY customer_id ORDER BY order_date) AS cumulative_orders FROM orders; -> Option C

4. Quick Check:

   Use PARTITION BY customer_id with ORDER BY for cumulative count [OK]

Hint: Partition by customer and order by date for cumulative count [OK]

Common Mistakes:

• Missing PARTITION BY customer_id
• Using GROUP BY instead of window function
• Partitioning by wrong column