ROW_NUMBER function in SQL - Time & Space Complexity

Time Complexity: ROW_NUMBER function

O(n log n)

Understanding Time Complexity

We want to understand how the time to run a query using the ROW_NUMBER function changes as the data grows.

Specifically, how does numbering rows in order affect performance when the table gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This query assigns a rank number to each employee within their department based on salary, ordering from highest to lowest.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Sorting each department's employees by salary.
• How many times: Once per department, sorting all employees in that department.

How Execution Grows With Input

As the number of employees grows, the database must sort more rows within each department.

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

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 assign row numbers grows a little faster than the number of rows because sorting is involved.

Common Mistake

[X] Wrong: "ROW_NUMBER just counts rows one by one, so it must be very fast and linear."

[OK] Correct: The function needs to sort rows within each group first, which takes more time than just counting.

Interview Connect

Understanding how window functions like ROW_NUMBER scale helps you explain query performance clearly and shows you know what happens behind the scenes.

Self-Check

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