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?"

Practice

1. What does the ROW_NUMBER() function do in SQL?

easy

A. Counts the total number of rows in a table.

B. Filters rows based on a condition.

C. Calculates the sum of values in a column.

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

Solution

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

   The ROW_NUMBER() function assigns a unique sequential integer to rows in the result set, starting at 1.

2. Step 2: Compare with other options

   Counting rows, summing values, or filtering rows are done by other SQL functions like COUNT(), SUM(), or WHERE clause, not ROW_NUMBER().

3. Final Answer:

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

4. Quick Check:

   ROW_NUMBER() = unique row numbers [OK]

Hint: ROW_NUMBER() gives each row a unique number starting at 1 [OK]

Common Mistakes:

• Confusing ROW_NUMBER() with COUNT()
• Thinking ROW_NUMBER() filters rows
• Assuming ROW_NUMBER() sums values

2. Which of the following is the correct syntax to assign row numbers ordered by salary in descending order?

easy

A. SELECT ROW_NUMBER() FROM employees ORDER BY salary DESC;

B. SELECT ROW_NUMBER() OVER (ORDER BY salary DESC) AS rn FROM employees;

C. SELECT ROW_NUMBER() ORDER BY salary DESC FROM employees;

D. SELECT ROW_NUMBER(salary DESC) FROM employees;

Solution

1. Step 1: Identify correct ROW_NUMBER() syntax

   The correct syntax uses ROW_NUMBER() OVER (ORDER BY column) to assign numbers ordered by a column.

2. Step 2: Check each option

   Only SELECT ROW_NUMBER() OVER (ORDER BY salary DESC) AS rn FROM employees; correctly uses OVER (ORDER BY salary DESC). The other options omit the OVER clause, pass arguments directly to ROW_NUMBER(), or misplace the ORDER BY clause.

3. Final Answer:

   SELECT ROW_NUMBER() OVER (ORDER BY salary DESC) AS rn FROM employees; -> Option B

4. Quick Check:

   ROW_NUMBER() needs OVER with ORDER BY [OK]

Hint: ROW_NUMBER() must use OVER() with ORDER BY inside [OK]

Common Mistakes:

• Omitting OVER() clause
• Placing ORDER BY outside OVER()
• Passing column directly to ROW_NUMBER()

3. Given the table sales with columns region and amount, what will this query return?

SELECT region, amount, ROW_NUMBER() OVER (PARTITION BY region ORDER BY amount DESC) AS rn FROM sales;

medium

A. The total count of sales per region.

B. A unique row number for all sales ignoring region, ordered by amount ascending.

C. A unique row number for each sale, restarting at 1 for each region, ordered by highest amount first.

D. The sum of amounts per region.

Solution

1. Step 1: Understand PARTITION BY effect

   Using PARTITION BY region restarts the row numbering for each region group separately.

2. Step 2: Understand ORDER BY inside ROW_NUMBER()

   Ordering by amount DESC means the highest amount in each region gets row number 1, next highest 2, and so on.

3. Final Answer:

   A unique row number for each sale, restarting at 1 for each region, ordered by highest amount first. -> Option C

4. Quick Check:

   ROW_NUMBER() with PARTITION BY = numbering per group [OK]

Hint: PARTITION BY restarts numbering per group [OK]

Common Mistakes:

• Ignoring PARTITION BY and numbering all rows globally
• Confusing ORDER BY direction
• Thinking ROW_NUMBER() counts rows

4. Identify the error in this query:

SELECT name, ROW_NUMBER() ORDER BY salary FROM employees;

medium

A. Missing OVER() clause after ROW_NUMBER().

B. ORDER BY cannot be used in SELECT clause.

C. ROW_NUMBER() cannot be used without GROUP BY.

D. salary column does not exist.

Solution

1. Step 1: Check ROW_NUMBER() syntax

   The ROW_NUMBER() function requires an OVER() clause specifying ordering or partitioning.

2. Step 2: Analyze the query

   The query uses ROW_NUMBER() without OVER(), which causes a syntax error. ORDER BY inside SELECT is invalid without OVER().

3. Final Answer:

   Missing OVER() clause after ROW_NUMBER(). -> Option A

4. Quick Check:

   ROW_NUMBER() must have OVER() [OK]

Hint: ROW_NUMBER() always needs OVER() clause [OK]

Common Mistakes:

• Forgetting OVER() after ROW_NUMBER()
• Placing ORDER BY outside OVER()
• Assuming ROW_NUMBER() works without ordering

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 * FROM (SELECT *, ROW_NUMBER() OVER (PARTITION BY department ORDER BY salary DESC) AS rn FROM employees) sub WHERE rn <= 2;

B. SELECT *, ROW_NUMBER() FROM employees WHERE salary IN (SELECT MAX(salary) FROM employees GROUP BY department);

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

D. SELECT department, salary FROM employees ORDER BY salary DESC LIMIT 2;

Solution

1. Step 1: Use ROW_NUMBER() with PARTITION BY department

   To get top 2 per department, assign row numbers restarting for each department ordered by salary descending.

2. Step 2: Filter rows with row number less than or equal to 2

   Wrap the query as a subquery and filter where rn <= 2 to get top 2 employees per department.

3. Final Answer:

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

4. Quick Check:

   ROW_NUMBER() + PARTITION + filter = top N per group [OK]

Hint: Use ROW_NUMBER() with PARTITION BY and filter rn <= N [OK]

Common Mistakes:

• Not using PARTITION BY to group by department
• Filtering on rn in the same SELECT without subquery
• Using LIMIT without partitioning