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

Time Complexity: OVER clause with ORDER BY

O(n log n)

Understanding Time Complexity

When using the OVER clause with ORDER BY in SQL, the database sorts data before applying functions like ranking or running totals.

We want to understand how the time needed grows as the data size increases.

Scenario Under Consideration

Analyze the time complexity of the following SQL query.

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

This query ranks employees by salary within each department.

Identify Repeating Operations

Look for repeated work done by the query.

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

How Execution Grows With Input

As the number of employees grows, sorting takes more time.

Input Size (n)	Approx. Operations
10	About 10 log 10 (small sorting cost)
100	About 100 log 100 (larger sorting cost)
1000	About 1000 log 1000 (much larger sorting cost)

Pattern observation: Sorting cost grows a bit faster than the number of rows because sorting is more work than just scanning.

Final Time Complexity

Time Complexity: O(n log n)

This means the time grows a little faster than the number of rows because sorting takes extra steps.

Common Mistake

[X] Wrong: "The OVER clause with ORDER BY just scans the data once, so it is O(n)."

[OK] Correct: Sorting inside the OVER clause requires extra work, so it takes more time than a simple scan.

Interview Connect

Understanding how sorting affects query time helps you explain performance and write better SQL in real projects.

Self-Check

What if we removed the ORDER BY inside the OVER clause? How would the time complexity change?

Practice

1. What does the OVER clause with ORDER BY do in SQL?

easy

A. It creates a new table sorted by the specified column.

B. It performs calculations on rows in a specific order without grouping them.

C. It filters rows based on order conditions.

D. It groups rows and then orders the groups.

Solution

1. Step 1: Understand the OVER clause

   The OVER clause allows window functions to work on a set of rows related to the current row without grouping them.

2. Step 2: Role of ORDER BY inside OVER

   ORDER BY inside OVER defines the order in which rows are processed for functions like ROW_NUMBER() or SUM() running totals.

3. Final Answer:

   It performs calculations on rows in a specific order without grouping them. -> Option B

4. Quick Check:

   OVER with ORDER BY = ordered calculations without grouping [OK]

Hint: OVER with ORDER BY orders rows for calculations, no grouping needed [OK]

Common Mistakes:

• Thinking OVER groups rows like GROUP BY
• Confusing ORDER BY inside OVER with filtering
• Assuming it creates a new sorted table

2. Which of the following is the correct syntax to assign row numbers ordered by salary using the OVER clause?

easy

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

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

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

D. SELECT ROW_NUMBER() OVER (ORDER BY salary) AS rank FROM employees;

Solution

1. Step 1: Identify correct ROW_NUMBER() syntax

   ROW_NUMBER() requires OVER() with ORDER BY inside parentheses to define ordering.

2. Step 2: Check each option

   SELECT ROW_NUMBER() OVER (ORDER BY salary) AS rank FROM employees; correctly uses ROW_NUMBER() OVER (ORDER BY salary). Others miss parentheses or misplace clauses.

3. Final Answer:

   SELECT ROW_NUMBER() OVER (ORDER BY salary) AS rank FROM employees; -> Option D

4. Quick Check:

   ROW_NUMBER() needs OVER(ORDER BY ...) [OK]

Hint: ROW_NUMBER() must be followed by OVER(ORDER BY column) [OK]

Common Mistakes:

• Omitting OVER() parentheses
• Placing ORDER BY outside OVER()
• Using ROW_NUMBER() without OVER

3. Given the table sales with columns id, amount, what is the output of this query?

SELECT id, amount, SUM(amount) OVER (ORDER BY id) AS running_total FROM sales ORDER BY id;

medium

A. The query returns an error due to missing GROUP BY.

B. Each row shows id, amount, and total sum of all amounts repeated.

C. Each row shows id, amount, and a running total of amounts ordered by id.

D. Rows are grouped by id with sum of amounts per group.

Solution

1. Step 1: Understand SUM() OVER (ORDER BY id)

   This calculates a running total of amount, adding amounts in order of id for each row.

2. Step 2: Analyze output per row

   Each row shows its id, amount, and the sum of amounts from first id up to current id.

3. Final Answer:

   Each row shows id, amount, and a running total of amounts ordered by id. -> Option C

4. Quick Check:

   SUM() OVER with ORDER BY = running total [OK]

Hint: SUM() OVER(ORDER BY) gives running totals, not grouped sums [OK]

Common Mistakes:

• Thinking it sums all rows for each row
• Expecting GROUP BY to be required
• Confusing running total with grouped sum

4. Identify the error in this query:

SELECT id, RANK() OVER ORDER BY score FROM players;

medium

A. Missing parentheses after OVER and ORDER BY inside them.

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

C. ORDER BY should be outside the OVER clause.

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

Solution

1. Step 1: Check syntax of RANK() with OVER

   RANK() requires OVER() with parentheses enclosing ORDER BY clause.

2. Step 2: Identify missing parentheses

   The query misses parentheses after OVER and does not put ORDER BY inside them, causing syntax error.

3. Final Answer:

   Missing parentheses after OVER and ORDER BY inside them. -> Option A

4. Quick Check:

   OVER() must have parentheses with ORDER BY inside [OK]

Hint: Always use OVER(...) with parentheses enclosing ORDER BY [OK]

Common Mistakes:

• Writing OVER without parentheses
• Placing ORDER BY outside OVER()
• Assuming RANK() works without OVER

5. You want to assign a rank to employees based on their salary, but if two employees have the same salary, they should get the same rank and the next rank should skip accordingly. Which query correctly uses the OVER clause with ORDER BY to achieve this?

hard

A. SELECT employee_id, salary, RANK() OVER (ORDER BY salary DESC) AS salary_rank FROM employees;

B. SELECT employee_id, salary, ROW_NUMBER() OVER (ORDER BY salary DESC) AS salary_rank FROM employees;

C. SELECT employee_id, salary, DENSE_RANK() OVER (ORDER BY salary DESC) AS salary_rank FROM employees;

D. SELECT employee_id, salary, RANK() OVER ORDER BY salary DESC AS salary_rank FROM employees;

Solution

1. Step 1: Understand ranking functions

   RANK() assigns same rank to ties and skips ranks after ties; DENSE_RANK() assigns same rank but no skips; ROW_NUMBER() assigns unique numbers.

2. Step 2: Check syntax and behavior

   SELECT employee_id, salary, RANK() OVER (ORDER BY salary DESC) AS salary_rank FROM employees; uses RANK() with correct OVER(ORDER BY salary DESC) syntax, matching requirement. SELECT employee_id, salary, RANK() OVER ORDER BY salary DESC AS salary_rank FROM employees; has syntax error. ROW_NUMBER() and DENSE_RANK() do not skip ranks after ties.

3. Final Answer:

   SELECT employee_id, salary, RANK() OVER (ORDER BY salary DESC) AS salary_rank FROM employees; -> Option A

4. Quick Check:

   RANK() with OVER(ORDER BY) skips ranks after ties [OK]

Hint: Use RANK() OVER(ORDER BY) for ranks with gaps on ties [OK]

Common Mistakes:

• Using ROW_NUMBER() which never skips ranks
• Using DENSE_RANK() which does not skip ranks
• Missing parentheses in OVER clause