Window function vs GROUP BY mental model in SQL - Performance Comparison

Time Complexity: Window function vs GROUP BY mental model

O(n)

Understanding Time Complexity

We want to understand how the time it takes to run queries with window functions compares to those using GROUP BY.

How does the work grow as the data gets bigger for each method?

Scenario Under Consideration

Analyze the time complexity of these two queries.

-- Using GROUP BY
SELECT department, COUNT(*) AS emp_count
FROM employees
GROUP BY department;

-- Using Window Function
SELECT employee_id, department, COUNT(*) OVER (PARTITION BY department) AS emp_count
FROM employees;
    

The first query groups rows by department and counts employees per group. The second counts employees per department but keeps all rows.

Identify Repeating Operations

Look at what repeats in each query.

• Primary operation: Scanning all rows once to count employees.
• How many times: Each row is processed once; window function adds a step to assign counts back to each row.

How Execution Grows With Input

As the number of employees (rows) grows, the work changes like this:

Input Size (n)	Approx. Operations
10	About 10 row scans and counts
100	About 100 row scans and counts
1000	About 1000 row scans and counts

Both queries scan all rows once, but the window function also assigns counts back to each row, so it does a bit more work per row.

Final Time Complexity

Time Complexity: O(n)

This means the time grows roughly in direct proportion to the number of rows in the table.

Common Mistake

[X] Wrong: "Window functions always take much longer than GROUP BY because they do more work."

[OK] Correct: Both scan all rows once; window functions add some extra steps but still scale linearly, so the difference is usually small.

Interview Connect

Understanding how these queries scale helps you explain your choices clearly and shows you know how databases handle data efficiently.

Self-Check

"What if we added an ORDER BY clause inside the window function? How would that affect the time complexity?"