OVER clause with ORDER BY in SQL - Time & Space Complexity

Time Complexity: OVER clause with ORDER BY

O(n log n)

Understanding Time Complexity

When using the OVER clause with ORDER BY in SQL, the database sorts data before applying functions like ranking or running totals.

We want to understand how the time needed grows as the data size increases.

Scenario Under Consideration

Analyze the time complexity of the following SQL query.

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 salaries within each department.
• How many times: Once per department group, sorting all employees in that group.

How Execution Grows With Input

As the number of employees grows, sorting takes more time.

Input Size (n)	Approx. Operations
10	About 10 log 10 (small sorting cost)
100	About 100 log 100 (larger sorting cost)
1000	About 1000 log 1000 (much larger sorting cost)

Pattern observation: Sorting cost grows a bit faster than the number of rows because sorting is more work than just scanning.

Final Time Complexity

Time Complexity: O(n log n)

This means the time grows a little faster than the number of rows because sorting takes extra steps.

Common Mistake

[X] Wrong: "The OVER clause with ORDER BY just scans the data once, so it is O(n)."

[OK] Correct: Sorting inside the OVER clause requires extra work, so it takes more time than a simple scan.

Interview Connect

Understanding how sorting affects query time helps you explain performance and write better SQL in real projects.

Self-Check

What if we removed the ORDER BY inside the OVER clause? How would the time complexity change?