Why window functions are needed in SQL - Performance Analysis

Time Complexity: Why window functions are needed

O(n log n)

Understanding Time Complexity

We want to understand how the cost of using window functions grows as the data size increases.

Specifically, we ask: How does the work done by window functions scale with more rows?

Scenario Under Consideration

Analyze the time complexity of this SQL query using a window function.

SELECT employee_id, department_id, salary,
       RANK() OVER (PARTITION BY department_id ORDER BY salary DESC) AS salary_rank
FROM employees;
    

This query ranks employees by salary within each department.

Identify Repeating Operations

Look for repeated work done by the query.

• Primary operation: Sorting employees within each department to assign ranks.
• How many times: Once per department, over all employees in that department.

How Execution Grows With Input

As the number of employees grows, the sorting work grows too.

Input Size (n)	Approx. Operations
10	About 10 log 10 operations
100	About 100 log 100 operations
1000	About 1000 log 1000 operations

Pattern observation: The work grows a bit faster than the number of rows because sorting takes more effort as data grows.

Final Time Complexity

Time Complexity: O(n log n)

This means the time to run the window function grows a bit faster than the number of rows, mainly due to sorting.

Common Mistake

[X] Wrong: "Window functions just scan rows once, so they always run in linear time."

[OK] Correct: Window functions often sort or group data internally, which takes more than just scanning once, increasing the time needed.

Interview Connect

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

Self-Check

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