Why window functions are needed in SQL - Performance Analysis

Time Complexity: Why window functions are needed

O(n log n)

Understanding Time Complexity

We want to understand how the cost of using window functions grows as the data size increases.

Specifically, we ask: How does the work done by window functions scale with more rows?

Scenario Under Consideration

Analyze the time complexity of this SQL query using a window function.

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 employees within each department to assign ranks.
• How many times: Once per department, over all employees in that department.

How Execution Grows With Input

As the number of employees grows, the sorting work grows too.

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

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 run the window function grows a bit faster than the number of rows, mainly due to sorting.

Common Mistake

[X] Wrong: "Window functions just scan rows once, so they always run in linear time."

[OK] Correct: Window functions often sort or group data internally, which takes more than just scanning once, increasing the time needed.

Interview Connect

Understanding how window functions scale helps you explain query performance clearly and shows you know how databases handle complex operations efficiently.

Self-Check

"What if we removed the PARTITION BY clause? How would the time complexity change?"

Practice

1. Why are window functions needed in SQL?
SELECT with window functions can do what that regular aggregation cannot?

easy

A. They speed up query execution by skipping indexes.

B. They allow calculations across rows without hiding individual rows.

C. They automatically create new tables for results.

D. They replace the need for JOIN operations.

Solution

1. Step 1: Understand aggregation vs window functions

   Regular aggregation groups rows and returns fewer rows, hiding details.

2. Step 2: Identify window function behavior

   Window functions calculate values across rows but keep all original rows visible.

3. Final Answer:

   They allow calculations across rows without hiding individual rows. -> Option B

4. Quick Check:

   Window functions keep rows visible = A [OK]

Hint: Window functions keep all rows, aggregations reduce rows [OK]

Common Mistakes:

• Thinking window functions create new tables
• Confusing window functions with JOINs
• Believing window functions speed up queries

2. Which of the following is the correct syntax to use a window function in SQL?

easy

A. SELECT name, RANK() OVER (ORDER BY score) FROM players;

B. SELECT name, RANK(score) FROM players ORDER BY score;

C. SELECT name, RANK() FROM players GROUP BY score;

D. SELECT name, RANK OVER (ORDER BY score) FROM players;

Solution

1. Step 1: Recall window function syntax

   Window functions use function() OVER (PARTITION BY ... ORDER BY ...).

2. Step 2: Check each option

   SELECT name, RANK() OVER (ORDER BY score) FROM players; correctly uses RANK() OVER (ORDER BY score). Others miss parentheses or OVER keyword.

3. Final Answer:

   SELECT name, RANK() OVER (ORDER BY score) FROM players; -> Option A

4. Quick Check:

   Window function syntax = function() OVER (...) [OK]

Hint: Window functions always use OVER() clause [OK]

Common Mistakes:

• Omitting parentheses after function name
• Forgetting the OVER keyword
• Using GROUP BY instead of window functions

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

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

medium

A. A running total of sales amount per region, ordered by id, showing all rows.

B. Total sales amount per region, one row per region only.

C. Sum of all sales amounts ignoring region, one total value.

D. Syntax error due to missing GROUP BY clause.

Solution

1. Step 1: Understand SUM() OVER with PARTITION and ORDER

   SUM() OVER (PARTITION BY region ORDER BY id) calculates a running total per region ordered by id.

2. Step 2: Check output rows

   Window functions keep all rows, so all sales rows appear with running totals.

3. Final Answer:

   A running total of sales amount per region, ordered by id, showing all rows. -> Option A

4. Quick Check:

   Running total per group = A [OK]

Hint: SUM() OVER with PARTITION BY gives running totals per group [OK]

Common Mistakes:

• Thinking it returns one row per group
• Confusing window function with GROUP BY aggregation
• Expecting syntax error without GROUP BY

4. Identify the error in this SQL query using a window function:

SELECT employee_id, department, ROW_NUMBER() ORDER BY salary FROM employees;

medium

A. ORDER BY cannot be used inside ROW_NUMBER().

B. employee_id must be inside ROW_NUMBER() function.

C. ROW_NUMBER() requires GROUP BY clause.

D. Missing OVER() clause after ROW_NUMBER() function.

Solution

1. Step 1: Check window function syntax

   ROW_NUMBER() must be followed by OVER() with optional ORDER BY inside it.

2. Step 2: Identify missing OVER()

   The query uses ROW_NUMBER() ORDER BY salary without OVER(), causing syntax error.

3. Final Answer:

   Missing OVER() clause after ROW_NUMBER() function. -> Option D

4. Quick Check:

   Window functions need OVER() [OK]

Hint: Always add OVER() after window functions [OK]

Common Mistakes:

• Placing ORDER BY outside OVER()
• Thinking GROUP BY is needed for ROW_NUMBER()
• Misunderstanding function arguments

5. You want to find each employee's salary rank within their department, but also show all employees with their salaries and ranks. Which SQL approach best achieves this?

hard

A. Use a subquery to calculate ranks and join back to employees table.

B. Use GROUP BY department, salary with RANK() to get ranks per department.

C. Use RANK() OVER (PARTITION BY department ORDER BY salary DESC) to rank salaries per department while keeping all rows.

D. Use ORDER BY salary DESC with LIMIT to get top salaries per department.

Solution

1. Step 1: Understand the requirement

   We want ranks per department and all employees listed with their ranks.

2. Step 2: Evaluate options

   Use RANK() OVER (PARTITION BY department ORDER BY salary DESC) to rank salaries per department while keeping all rows. uses RANK() OVER (PARTITION BY department ORDER BY salary DESC) which ranks salaries per department and keeps all rows visible.

3. Final Answer:

   Use RANK() OVER (PARTITION BY department ORDER BY salary DESC) to rank salaries per department while keeping all rows. -> Option C

4. Quick Check:

   Window function with PARTITION keeps all rows and ranks [OK]

Hint: Use RANK() OVER PARTITION BY to rank within groups [OK]

Common Mistakes:

• Using GROUP BY loses individual rows
• Using subqueries unnecessarily complicates query
• LIMIT filters rows, not ranks all