Window functions (ROW_NUMBER) in MySQL - Time & Space Complexity

Time Complexity: Window functions (ROW_NUMBER)

O(n log n)

Understanding Time Complexity

We want to understand how the time needed to run a query with ROW_NUMBER grows as the data gets bigger.

How does the number of rows affect the work done by the database?

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.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The database groups rows by department and sorts each group by salary.
• How many times: It processes every row once, but sorting happens within each department group.

How Execution Grows With Input

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

Input Size (n)	Approx. Operations
10	About 10 rows sorted in small groups
100	More rows sorted, groups get bigger
1000	Much more sorting work inside groups

Pattern observation: The sorting work grows a bit faster than the number of rows because sorting is more than just looking at each row once.

Final Time Complexity

Time Complexity: O(n log n)

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

Common Mistake

[X] Wrong: "ROW_NUMBER just looks at each row once, so it must be O(n)."

[OK] Correct: The function needs to sort rows within each group, and sorting takes more work than just one pass.

Interview Connect

Understanding how window functions like ROW_NUMBER scale helps you explain query performance clearly and shows you know how databases handle sorting and grouping.

Self-Check

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