OVER clause with PARTITION BY in SQL - Time & Space Complexity

Time Complexity: OVER clause with PARTITION BY

O(n log n)

Understanding Time Complexity

We want to understand how the time to run a query with the OVER clause and PARTITION BY grows as the data gets bigger.

Specifically, how does dividing data into groups affect the work done?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT employee_id, department_id, salary,
       RANK() OVER (PARTITION BY department_id ORDER BY salary DESC) AS dept_rank
FROM employees;
    

This query ranks employees by salary within each department.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Sorting employees within each department to assign ranks.
• How many times: Once per department group, sorting all employees in that group.

How Execution Grows With Input

As the number of employees grows, the query sorts each department's employees separately.

Input Size (n)	Approx. Operations
10	About 10 log 10 operations (sorting small groups)
100	About 100 log 100 operations (sorting larger groups)
1000	About 1000 log 1000 operations (sorting even larger groups)

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

Final Time Complexity

Time Complexity: O(n log n)

This means the time to run the query grows a bit faster than the number of rows because sorting is needed within each group.

Common Mistake

[X] Wrong: "The PARTITION BY makes the query run in linear time because it splits the data."

[OK] Correct: Even though data is split, each group still needs sorting, which takes more than just looking at each row once.

Interview Connect

Understanding how window functions like OVER with PARTITION BY affect performance shows you know how databases handle grouped data efficiently.

Self-Check

"What if we removed the PARTITION BY clause and ranked all employees together? How would the time complexity change?"

Practice

1. What does the PARTITION BY clause do when used with the OVER clause in SQL?

easy

A. It divides the result set into groups to perform calculations within each group.

B. It filters rows before aggregation happens.

C. It sorts the entire result set globally.

D. It removes duplicate rows from the result.

Solution

1. Step 1: Understand the role of PARTITION BY

   The PARTITION BY clause groups rows based on column values, similar to grouping in real life like sorting students by class.

2. Step 2: See how OVER uses PARTITION BY

   The OVER clause applies functions like SUM or ROW_NUMBER within each group separately, not on the whole table.

3. Final Answer:

   It divides the result set into groups to perform calculations within each group. -> Option A

4. Quick Check:

   PARTITION BY = group rows for calculations [OK]

Hint: Think of PARTITION BY as grouping rows inside a window function [OK]

Common Mistakes:

• Confusing PARTITION BY with WHERE filtering
• Thinking PARTITION BY sorts all rows globally
• Assuming PARTITION BY removes duplicates

2. Which of the following is the correct syntax to calculate a running total of sales per department using OVER with PARTITION BY?

easy

A. SELECT department, sales, SUM(sales) OVER ORDER BY date PARTITION BY department AS running_total FROM sales_data;

B. SELECT department, sales, SUM(sales) OVER (PARTITION BY department ORDER BY date) AS running_total FROM sales_data;

C. SELECT department, sales, SUM(sales) PARTITION BY department OVER ORDER BY date AS running_total FROM sales_data;

D. SELECT department, sales, SUM(sales) OVER (ORDER BY date PARTITION BY department) AS running_total FROM sales_data;

Solution

1. Step 1: Identify correct OVER clause order

   The correct syntax places PARTITION BY before ORDER BY inside the parentheses after OVER.

2. Step 2: Check each option's syntax

   SELECT department, sales, SUM(sales) OVER (PARTITION BY department ORDER BY date) AS running_total FROM sales_data; correctly uses SUM(sales) OVER (PARTITION BY department ORDER BY date). Others misplace PARTITION BY or OVER keywords.

3. Final Answer:

   SELECT department, sales, SUM(sales) OVER (PARTITION BY department ORDER BY date) AS running_total FROM sales_data; -> Option B

4. Quick Check:

   PARTITION BY before ORDER BY inside OVER [OK]

Hint: Remember: OVER (PARTITION BY ... ORDER BY ...) is the correct order [OK]

Common Mistakes:

• Swapping PARTITION BY and ORDER BY order
• Placing PARTITION BY outside OVER parentheses
• Using PARTITION BY without OVER

3. Given the table Employees with columns Department and Salary, what will the following query return?

SELECT Department, Salary, RANK() OVER (PARTITION BY Department ORDER BY Salary DESC) AS SalaryRank FROM Employees;

medium

A. Returns the salary and department without any ranking.

B. Ranks salaries across all employees ignoring departments.

C. Calculates the total salary per department.

D. Ranks salaries within each department from highest to lowest, starting at 1 for the highest salary.

Solution

1. Step 1: Understand RANK() with PARTITION BY

   The RANK() function assigns ranks starting at 1 within each partition (department), ordered by salary descending.

2. Step 2: Analyze the query output

   Each employee gets a rank based on salary within their department, highest salary ranked 1, ties get same rank.

3. Final Answer:

   Ranks salaries within each department from highest to lowest, starting at 1 for the highest salary. -> Option D

4. Quick Check:

   RANK() OVER PARTITION BY groups and ranks rows [OK]

Hint: RANK() with PARTITION BY ranks within groups, not whole table [OK]

Common Mistakes:

• Thinking RANK() ignores PARTITION BY
• Confusing RANK() with SUM()
• Assuming ranking is global, not per group

4. Identify the error in this SQL query:

SELECT employee_id, department, SUM(salary) OVER PARTITION BY department FROM employees;

medium

A. department column cannot be used in PARTITION BY.

B. SUM() cannot be used with OVER clause.

C. Missing parentheses around PARTITION BY clause inside OVER.

D. employee_id must be included in PARTITION BY.

Solution

1. Step 1: Check OVER clause syntax

   The OVER clause must have parentheses enclosing PARTITION BY and other clauses.

2. Step 2: Identify missing parentheses

   The query misses parentheses after OVER, it should be OVER (PARTITION BY department).

3. Final Answer:

   Missing parentheses around PARTITION BY clause inside OVER. -> Option C

4. Quick Check:

   OVER requires parentheses around PARTITION BY [OK]

Hint: Always put parentheses after OVER, even if only PARTITION BY used [OK]

Common Mistakes:

• Omitting parentheses after OVER
• Using aggregate without OVER for window function
• Including wrong columns in PARTITION BY

5. You want to find each student's score rank within their class and also show the average score of their class. Which SQL query correctly uses OVER with PARTITION BY to achieve this?

hard

A. SELECT student_id, class, score, RANK() OVER (PARTITION BY class ORDER BY score DESC) AS rank_in_class, AVG(score) OVER (PARTITION BY class) AS avg_class_score FROM student_scores;

B. SELECT student_id, class, score, RANK() OVER (ORDER BY score DESC PARTITION BY class) AS rank_in_class, AVG(score) OVER (PARTITION BY class) AS avg_class_score FROM student_scores;

C. SELECT student_id, class, score, RANK() PARTITION BY class ORDER BY score DESC AS rank_in_class, AVG(score) OVER (class) AS avg_class_score FROM student_scores;

D. SELECT student_id, class, score, RANK() OVER (PARTITION BY class ORDER BY score) AS rank_in_class, AVG(score) OVER (PARTITION BY class ORDER BY score) AS avg_class_score FROM student_scores;

Solution

1. Step 1: Use correct syntax for RANK() and AVG() with PARTITION BY

   Both functions must have OVER (PARTITION BY class ...). RANK() orders descending for highest score first; AVG() just partitions by class.

2. Step 2: Check each option's correctness

   SELECT student_id, class, score, RANK() OVER (PARTITION BY class ORDER BY score DESC) AS rank_in_class, AVG(score) OVER (PARTITION BY class) AS avg_class_score FROM student_scores; correctly uses RANK() OVER (PARTITION BY class ORDER BY score DESC) and AVG(score) OVER (PARTITION BY class). Others have syntax errors or wrong order.

3. Final Answer:

   SELECT student_id, class, score, RANK() OVER (PARTITION BY class ORDER BY score DESC) AS rank_in_class, AVG(score) OVER (PARTITION BY class) AS avg_class_score FROM student_scores; -> Option A

4. Quick Check:

   Use OVER (PARTITION BY ...) with correct order and parentheses [OK]

Hint: Use separate OVER clauses with PARTITION BY for each window function [OK]

Common Mistakes:

• Mixing ORDER BY and PARTITION BY order inside OVER
• Missing parentheses around PARTITION BY
• Using PARTITION BY without OVER