ROW_NUMBER, RANK, DENSE_RANK in PostgreSQL - Time & Space Complexity

Time Complexity: ROW_NUMBER, RANK, DENSE_RANK

O(n log n)

Understanding Time Complexity

When using ROW_NUMBER, RANK, or DENSE_RANK in SQL, it's important to understand how the time to get results grows as the data grows.

We want to know how the database handles sorting and numbering rows as 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 row_num,
       RANK() OVER (PARTITION BY department_id ORDER BY salary DESC) AS rank,
       DENSE_RANK() OVER (PARTITION BY department_id ORDER BY salary DESC) AS dense_rank
FROM employees;
    

This query assigns row numbers and ranks to employees within each department based on salary order.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Sorting rows within each department by salary.
• How many times: Once per department group, but overall it processes all rows.

How Execution Grows With Input

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

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

Pattern observation: The work grows a bit faster than the number of rows because sorting takes more time as data grows.

Final Time Complexity

Time Complexity: O(n log n)

This means the time to assign row numbers and ranks grows a little faster than the number of rows because sorting is involved.

Common Mistake

[X] Wrong: "ROW_NUMBER and RANK just scan rows once, so time grows linearly with data size."

[OK] Correct: These functions require sorting rows within groups, which takes more time than a simple scan, so the time grows faster than just the number of rows.

Interview Connect

Understanding how window functions like ROW_NUMBER and RANK 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 PostgreSQL?

easy

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

B. Assigns the same rank to rows with identical values, skipping ranks after ties.

C. Assigns ranks to rows without skipping numbers after ties.

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

Solution

1. Step 1: Understand ROW_NUMBER() purpose

   ROW_NUMBER() gives each row a unique sequential number, starting at 1.

2. Step 2: Compare with RANK() and DENSE_RANK()

   Unlike RANK() or DENSE_RANK(), ROW_NUMBER() never assigns the same number to multiple rows.

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 always gives unique numbers, no ties allowed [OK]

Common Mistakes:

• Confusing ROW_NUMBER with RANK or DENSE_RANK
• Thinking ROW_NUMBER skips numbers after ties
• Assuming ROW_NUMBER counts total rows

2. Which of the following is the correct syntax to assign a rank using RANK() over a column named score ordered descending?

easy

A. SELECT RANK(score) OVER (ORDER BY DESC) FROM table_name;

B. SELECT RANK() ORDER BY score DESC FROM table_name;

C. SELECT RANK() OVER (ORDER BY score DESC) FROM table_name;

D. SELECT RANK() OVER (PARTITION BY score DESC) FROM table_name;

Solution

1. Step 1: Recall correct RANK() syntax

   RANK() is used with OVER() clause specifying ORDER BY column and direction.

2. Step 2: Check each option

   SELECT RANK() OVER (ORDER BY score DESC) FROM table_name; correctly uses RANK() OVER (ORDER BY score DESC). Others misuse syntax or clauses.

3. Final Answer:

   SELECT RANK() OVER (ORDER BY score DESC) FROM table_name; -> Option C

4. Quick Check:

   RANK() OVER (ORDER BY column DESC) syntax [OK]

Hint: RANK() needs OVER with ORDER BY column [OK]

Common Mistakes:

• Putting column inside RANK() function
• Using PARTITION BY incorrectly
• Omitting OVER() clause

3. Given the table players with columns name and score, what will be the output of this query?

SELECT name, score, RANK() OVER (ORDER BY score DESC) AS rank FROM players;

Data:
name | score -----|------ Alice | 100 Bob | 90 Carol | 90 Dave | 80

medium

A. [{"name": "Alice", "score": 100, "rank": 1}, {"name": "Bob", "score": 90, "rank": 1}, {"name": "Carol", "score": 90, "rank": 1}, {"name": "Dave", "score": 80, "rank": 2}]

B. [{"name": "Alice", "score": 100, "rank": 1}, {"name": "Bob", "score": 90, "rank": 2}, {"name": "Carol", "score": 90, "rank": 2}, {"name": "Dave", "score": 80, "rank": 4}]

C. [{"name": "Alice", "score": 100, "rank": 1}, {"name": "Bob", "score": 90, "rank": 2}, {"name": "Carol", "score": 90, "rank": 2}, {"name": "Dave", "score": 80, "rank": 3}]

D. [{"name": "Alice", "score": 100, "rank": 1}, {"name": "Bob", "score": 90, "rank": 2}, {"name": "Carol", "score": 90, "rank": 3}, {"name": "Dave", "score": 80, "rank": 4}]

Solution

1. Step 1: Understand RANK() behavior with ties

   RANK() assigns the same rank to tied scores and skips ranks after ties.

2. Step 2: Apply ranks to scores

   Alice has highest score 100 -> rank 1. Bob and Carol tie at 90 -> both rank 2. Next rank after tie skips to 4 for Dave.

3. Final Answer:

   [{"name": "Alice", "score": 100, "rank": 1}, {"name": "Bob", "score": 90, "rank": 2}, {"name": "Carol", "score": 90, "rank": 2}, {"name": "Dave", "score": 80, "rank": 4}] -> Option B

4. Quick Check:

   RANK() skips ranks after ties [OK]

Hint: RANK() skips numbers after ties, DENSE_RANK() does not [OK]

Common Mistakes:

• Assuming ranks after ties are consecutive
• Confusing RANK() with DENSE_RANK()
• Misordering rows by score

4. Identify the error in this query:

SELECT name, DENSE_RANK(score) OVER (ORDER BY score DESC) FROM players;

medium

A. DENSE_RANK() should not have a column inside the parentheses.

B. DENSE_RANK() cannot be used without PARTITION BY clause.

C. ORDER BY clause is missing in the OVER() clause.

D. The query is correct and will run without errors.

Solution

1. Step 1: Check DENSE_RANK() syntax

   DENSE_RANK() does not take any arguments inside parentheses; it is called as DENSE_RANK() OVER (...).

2. Step 2: Identify the error in the query

   The query incorrectly uses DENSE_RANK(score), which causes a syntax error.

3. Final Answer:

   DENSE_RANK() should not have a column inside the parentheses. -> Option A

4. Quick Check:

   DENSE_RANK() has empty parentheses [OK]

Hint: Window functions have empty parentheses, column goes in ORDER BY [OK]

Common Mistakes:

• Putting column inside DENSE_RANK()
• Thinking PARTITION BY is mandatory
• Omitting OVER() clause

5. You want to assign ranks to employees based on their sales, but you want no gaps in ranking numbers even if some employees have the same sales. Which function should you use and why?

Options:
A) ROW_NUMBER() because it gives unique numbers.
B) RANK() because it skips ranks after ties.
C) DENSE_RANK() because it assigns ranks without gaps after ties.
D) COUNT() because it counts rows.

hard

A. DENSE_RANK() because it assigns ranks without gaps after ties.

B. RANK() because it skips ranks after ties.

C. ROW_NUMBER() because it gives unique numbers.

D. COUNT() because it counts rows.

Solution

1. Step 1: Understand ranking requirements

   The requirement is to assign ranks with no gaps even if employees tie in sales.

2. Step 2: Match functions to behavior

   ROW_NUMBER() gives unique numbers, ignoring ties. RANK() skips ranks after ties causing gaps. DENSE_RANK() assigns ranks without gaps after ties.

3. Step 3: Choose correct function

   DENSE_RANK() fits the requirement perfectly.

4. Final Answer:

   DENSE_RANK() because it assigns ranks without gaps after ties. -> Option A

5. Quick Check:

   DENSE_RANK() = no gaps in ranks [OK]

Hint: Use DENSE_RANK() to avoid gaps in ranking numbers [OK]

Common Mistakes:

• Choosing RANK() and expecting no gaps
• Using ROW_NUMBER() which ignores ties
• Confusing COUNT() with ranking functions