Top-N per group query in SQL - Time & Space Complexity

Time Complexity: Top-N per group query

O(n log n)

Understanding Time Complexity

When we ask for the top N items in each group from a database, we want to know how the work grows as the data grows.

How does the time to get these top items change when there are more groups or more rows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT department, employee, salary
FROM (
  SELECT department, employee, salary,
         ROW_NUMBER() OVER (PARTITION BY department ORDER BY salary DESC) AS rn
  FROM employees
) sub
WHERE rn <= 3;
    

This query finds the top 3 highest salaries in each department from the employees table.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The window function scans all rows and assigns a rank within each department group.
• How many times: It processes every row once, but internally it sorts each group to assign ranks.

How Execution Grows With Input

Explain the growth pattern intuitively.

Input Size (n)	Approx. Operations
10	About 10 rows processed, sorting small groups quickly
100	About 100 rows processed, sorting groups takes more time
1000	About 1000 rows processed, sorting each group grows with group size

Pattern observation: The work grows roughly in proportion to the total number of rows, with extra cost for sorting within each group.

Final Time Complexity

Time Complexity: O(n log n)

This means the time grows a bit faster than the number of rows because sorting happens inside each group.

Common Mistake

[X] Wrong: "The query only looks at the top 3 rows per group, so it runs in constant time per group."

[OK] Correct: The database must first sort all rows in each group to find the top 3, so it processes all rows, not just 3.

Interview Connect

Understanding how grouping and sorting affect query time helps you explain your approach clearly and shows you know how databases handle data efficiently.

Self-Check

"What if we changed ROW_NUMBER() to RANK() or DENSE_RANK()? How would the time complexity change?"

Practice

1. What does the ROW_NUMBER() OVER (PARTITION BY column ORDER BY column) clause do in a SQL query?

easy

A. Assigns a unique rank number to each row within each group defined by the partition column.

B. Counts the total number of rows in the entire table.

C. Filters rows to only include those with the highest value in the column.

D. Joins two tables based on the partition column.

Solution

1. Step 1: Understand ROW_NUMBER() function

   ROW_NUMBER() assigns a unique sequential number to rows in the result set.

2. Step 2: Understand PARTITION BY usage

   PARTITION BY divides rows into groups, and ROW_NUMBER() restarts numbering for each group.

3. Final Answer:

   Assigns a unique rank number to each row within each group defined by the partition column. -> Option A

4. Quick Check:

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

Hint: ROW_NUMBER() with PARTITION BY ranks rows per group [OK]

Common Mistakes:

• Thinking ROW_NUMBER() counts total rows
• Confusing PARTITION BY with filtering
• Assuming it filters rows automatically

2. Which of the following SQL queries correctly selects the top 2 highest salaries per department from an employees table?

easy

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

B. SELECT * FROM employees ORDER BY salary DESC LIMIT 2 PARTITION BY department;

C. SELECT * FROM employees WHERE ROW_NUMBER() OVER (PARTITION BY department ORDER BY salary DESC) <= 2;

D. SELECT TOP 2 * FROM employees PARTITION BY department ORDER BY salary DESC;

Solution

1. Step 1: Understand ROW_NUMBER() usage in subquery

   ROW_NUMBER() must be used in a subquery or CTE to assign ranks before filtering.

2. Step 2: Filter rows by rank in outer query

   The outer query filters rows where the rank (rn) is 2 or less 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:

   Use subquery with ROW_NUMBER() and filter by rank [OK]

Hint: Use subquery with ROW_NUMBER() then filter by rank [OK]

Common Mistakes:

• Trying to filter ROW_NUMBER() directly in WHERE clause
• Using LIMIT with PARTITION BY (not valid syntax)
• Using TOP without proper partitioning

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

SELECT region, salesperson, amount FROM (SELECT region, salesperson, amount, ROW_NUMBER() OVER (PARTITION BY region ORDER BY amount DESC) AS rn FROM sales) AS ranked WHERE rn = 1;

medium

A. All sales records sorted by amount descending.

B. All sales records where amount equals 1.

C. The highest sale amount record for each region.

D. The lowest sale amount record for each region.

Solution

1. Step 1: Analyze ROW_NUMBER() with PARTITION BY region

   Rows are grouped by region and ranked by amount descending, so rn=1 is highest amount per region.

2. Step 2: Filter WHERE rn = 1

   This keeps only the top-ranked row per region, i.e., the highest sale amount record.

3. Final Answer:

   The highest sale amount record for each region. -> Option C

4. Quick Check:

   ROW_NUMBER() = 1 per group returns top record [OK]

Hint: Filter WHERE rn=1 to get top record per group [OK]

Common Mistakes:

• Thinking it returns all rows sorted
• Confusing rn=1 with lowest amount
• Assuming amount = 1 filters rows

4. Identify the error in this SQL query that tries to get the top 3 recent orders per customer from orders table:

SELECT customer_id, order_id, order_date, ROW_NUMBER() OVER (PARTITION BY customer_id ORDER BY order_date DESC) AS rank FROM orders WHERE rank <= 3;

medium

A. Missing GROUP BY clause for customer_id.

B. ROW_NUMBER() cannot be used with PARTITION BY.

C. ORDER BY must be ascending, not descending.

D. You cannot filter on an alias in the WHERE clause directly.

Solution

1. Step 1: Understand alias usage in WHERE clause

   Aliases like 'rank' defined in SELECT cannot be used in WHERE clause directly because WHERE is evaluated before SELECT.

2. Step 2: Correct approach using subquery or CTE

   Use a subquery or CTE to assign ROW_NUMBER(), then filter on 'rank' in outer query.

3. Final Answer:

   You cannot filter on an alias in the WHERE clause directly. -> Option D

4. Quick Check:

   Filter on ROW_NUMBER() alias in outer query, not WHERE [OK]

Hint: Filter ROW_NUMBER() in outer query, not WHERE clause [OK]

Common Mistakes:

• Using alias in WHERE clause directly
• Thinking ORDER BY DESC is invalid
• Adding unnecessary GROUP BY

5. You have a products table with columns category, product_id, and price. You want to find the top 2 most expensive products per category, but if two products have the same price, include both even if it means more than 2 per category. Which query achieves this?

hard

A. Use ROW_NUMBER() partitioned by category ordered by price DESC and filter WHERE rn <= 2.

B. Use RANK() partitioned by category ordered by price DESC and filter WHERE rank <= 2.

C. Use DENSE_RANK() partitioned by category ordered by price ASC and filter WHERE dense_rank <= 2.

D. Use COUNT() partitioned by category ordered by price DESC and filter WHERE count <= 2.

Solution

1. Step 1: Understand difference between ROW_NUMBER(), RANK(), and DENSE_RANK()

   ROW_NUMBER() assigns unique ranks, so ties get different numbers. RANK() assigns same rank to ties and skips ranks after. DENSE_RANK() assigns same rank to ties but no gaps.

2. Step 2: Choose RANK() to include ties at second place

   RANK() allows including all products tied at rank 2, possibly more than 2 rows per category.

3. Final Answer:

   Use RANK() partitioned by category ordered by price DESC and filter WHERE rank <= 2. -> Option B

4. Quick Check:

   RANK() includes ties with same rank [OK]

Hint: Use RANK() to include ties in top N per group [OK]

Common Mistakes:

• Using ROW_NUMBER() excludes ties
• Using DENSE_RANK() includes ties but no gaps
• Using COUNT() is invalid for ranking