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?

Practice

1. What does the ROW_NUMBER() function do in MySQL window functions?

easy

A. Assigns a unique sequential number to each row in the result set.

B. Calculates the sum of values in a column.

C. Filters rows based on a condition.

D. Joins two tables based on a key.

Solution

1. Step 1: Understand the purpose of ROW_NUMBER()

   ROW_NUMBER() assigns a unique number to each row in the order specified by ORDER BY.

2. Step 2: Differentiate from other functions

   It does not sum, filter, or join; it only numbers rows uniquely.

3. Final Answer:

   Assigns a unique sequential number to each row in the result set. -> Option A

4. Quick Check:

   ROW_NUMBER() = unique row numbering [OK]

Hint: ROW_NUMBER() gives each row a unique number in order [OK]

Common Mistakes:

• Confusing ROW_NUMBER() with aggregate functions like SUM()
• Thinking ROW_NUMBER() filters rows
• Assuming ROW_NUMBER() joins tables

2. Which of the following is the correct syntax to assign row numbers partitioned by department and ordered by salary DESC?

easy

A. ROW_NUMBER(PARTITION BY department ORDER BY salary DESC)

B. ROW_NUMBER() PARTITION BY department ORDER BY salary DESC

C. ROW_NUMBER() OVER (PARTITION BY department ORDER BY salary DESC)

D. ROW_NUMBER() BY department ORDER BY salary DESC

Solution

1. Step 1: Recall correct ROW_NUMBER() syntax

   The correct syntax uses OVER() with PARTITION BY and ORDER BY inside parentheses.

2. Step 2: Identify correct option

   ROW_NUMBER() OVER (PARTITION BY department ORDER BY salary DESC) correctly uses ROW_NUMBER() OVER (PARTITION BY department ORDER BY salary DESC).

3. Final Answer:

   ROW_NUMBER() OVER (PARTITION BY department ORDER BY salary DESC) -> Option C

4. Quick Check:

   Correct syntax includes OVER() with PARTITION BY and ORDER BY [OK]

Hint: ROW_NUMBER() always needs OVER() with clauses inside [OK]

Common Mistakes:

• Omitting OVER() keyword
• Placing PARTITION BY outside parentheses
• Using incorrect keywords order

3. Given the table Employees with columns id, department, salary, what will be the output of this query?

SELECT id, department, salary, ROW_NUMBER() OVER (PARTITION BY department ORDER BY salary DESC) AS rn FROM Employees;

Assuming data:
id | department | salary
1 | Sales | 5000
2 | Sales | 7000
3 | HR | 6000
4 | HR | 5500

medium

A. [{id:2, department:'Sales', salary:7000, rn:2}, {id:1, department:'Sales', salary:5000, rn:1}, {id:3, department:'HR', salary:6000, rn:2}, {id:4, department:'HR', salary:5500, rn:1}]

B. [{id:1, department:'Sales', salary:5000, rn:2}, {id:2, department:'Sales', salary:7000, rn:1}, {id:3, department:'HR', salary:6000, rn:1}, {id:4, department:'HR', salary:5500, rn:2}]

C. [{id:1, department:'Sales', salary:5000, rn:1}, {id:2, department:'Sales', salary:7000, rn:2}, {id:4, department:'HR', salary:5500, rn:1}, {id:3, department:'HR', salary:6000, rn:2}]

D. [{id:1, department:'Sales', salary:5000, rn:1}, {id:2, department:'Sales', salary:7000, rn:1}, {id:3, department:'HR', salary:6000, rn:1}, {id:4, department:'HR', salary:5500, rn:1}]

Solution

1. Step 1: Partition rows by department

   Rows are grouped into Sales and HR departments separately.

2. Step 2: Order each partition by salary descending and assign row numbers

   Within Sales: id 2 (7000) gets rn=1, id 1 (5000) rn=2; Within HR: id 3 (6000) rn=1, id 4 (5500) rn=2.

3. Final Answer:

   [{id:1, department:'Sales', salary:5000, rn:2}, {id:2, department:'Sales', salary:7000, rn:1}, {id:3, department:'HR', salary:6000, rn:1}, {id:4, department:'HR', salary:5500, rn:2}] -> Option B

4. Quick Check:

   Partition by department + order by salary DESC = correct row numbers [OK]

Hint: Partition groups restart numbering; order controls row number sequence [OK]

Common Mistakes:

• Ignoring PARTITION BY and numbering globally
• Ordering ascending instead of descending
• Assigning same row number to multiple rows

4. Identify the error in this query:

SELECT id, ROW_NUMBER() PARTITION BY department ORDER BY salary FROM Employees;

medium

A. Missing OVER() keyword before PARTITION BY clause.

B. ORDER BY cannot be used inside ROW_NUMBER().

C. PARTITION BY should be after ORDER BY.

D. ROW_NUMBER() cannot be used with SELECT.

Solution

1. Step 1: Check ROW_NUMBER() syntax

   ROW_NUMBER() requires OVER() before PARTITION BY and ORDER BY clauses.

2. Step 2: Identify missing OVER()

   The query misses OVER(), causing syntax error.

3. Final Answer:

   Missing OVER() keyword before PARTITION BY clause. -> Option A

4. Quick Check:

   ROW_NUMBER() must have OVER() [OK]

Hint: Always use OVER() with ROW_NUMBER() [OK]

Common Mistakes:

• Omitting OVER() keyword
• Placing PARTITION BY outside OVER()
• Misordering clauses inside OVER()

5. You want to select the top 2 highest paid employees per department from the Employees table. Which query correctly uses ROW_NUMBER() to achieve this?

hard

A. SELECT id, department, salary, ROW_NUMBER() OVER (ORDER BY salary DESC) AS rn FROM Employees WHERE rn <= 2;

B. SELECT *, ROW_NUMBER() FROM Employees WHERE rn <= 2 PARTITION BY department ORDER BY salary DESC;

C. SELECT id, department, salary FROM Employees ORDER BY salary DESC LIMIT 2 PARTITION BY department;

D. SELECT * FROM (SELECT *, ROW_NUMBER() OVER (PARTITION BY department ORDER BY salary DESC) AS rn FROM Employees) AS t WHERE rn <= 2;

Solution

1. Step 1: Use ROW_NUMBER() with PARTITION BY department and ORDER BY salary DESC

   This assigns row numbers restarting at 1 for each department, ordered by salary descending.

2. Step 2: Filter rows where row number is 2 or less

   Wrap the window function query as a subquery and filter with WHERE rn <= 2 to get top 2 per department.

3. Final Answer:

   SELECT * FROM (SELECT *, ROW_NUMBER() OVER (PARTITION BY department ORDER BY salary DESC) AS rn FROM Employees) AS t WHERE rn <= 2; -> Option D

4. Quick Check:

   Use subquery with ROW_NUMBER() and filter rn <= 2 [OK]

Hint: Use subquery with ROW_NUMBER() and filter rn <= 2 [OK]

Common Mistakes:

• Filtering rn in outer query without subquery
• Using LIMIT with PARTITION BY incorrectly
• Omitting PARTITION BY causing global numbering