Why advanced window functions matter in SQL - Performance Analysis

Time Complexity: Why advanced window functions matter

O(n log n)

Understanding Time Complexity

We want to understand how the time it takes to run advanced window functions changes as the data grows.

How does the work needed grow when we use these functions on bigger tables?

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 salary_rank
FROM employees;
    

This query ranks employees by salary within each department using a window function.

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, over all employees in that group.

How Execution Grows With Input

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

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 is involved.

Final Time Complexity

Time Complexity: O(n log n)

This means the time to run the query grows a little faster than the number of rows because it sorts data within groups.

Common Mistake

[X] Wrong: "Window functions just scan data once, so time grows linearly with rows."

[OK] Correct: Window functions often sort or partition data, which takes extra work beyond a simple scan.

Interview Connect

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

Self-Check

"What if we replaced RANK() with a simple aggregate like SUM()? How would the time complexity change?"

Practice

1. What is the main advantage of using advanced window functions in SQL compared to simple aggregate functions?

easy

A. They only work on single rows without considering others.

B. They automatically create indexes for faster queries.

C. They allow calculations across rows without collapsing the result into groups.

D. They replace the need for JOIN operations.

Solution

1. Step 1: Understand aggregate functions behavior

   Aggregate functions like SUM or AVG group rows and return one result per group, collapsing data.

2. Step 2: Understand window functions behavior

   Window functions perform calculations across rows but keep each row visible, without grouping them.

3. Final Answer:

   They allow calculations across rows without collapsing the result into groups. -> Option C

4. Quick Check:

   Window functions = calculations without grouping [OK]

Hint: Window functions keep rows, aggregates collapse them [OK]

Common Mistakes:

• Thinking window functions group rows like aggregates
• Confusing window functions with JOINs
• Assuming window functions only work on single rows

2. Which of the following is the correct syntax to calculate a running total of sales using a window function?

easy

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

B. SELECT SUM(sales) GROUP BY date ORDER BY running_total FROM sales_data;

C. SELECT RUNNING_TOTAL(sales) FROM sales_data ORDER BY date;

D. SELECT sales + PREVIOUS(sales) FROM sales_data;

Solution

1. Step 1: Identify correct window function syntax

   SUM() OVER (ORDER BY column) computes running total ordered by that column.

2. Step 2: Check other options for syntax errors

   The other options use invalid SQL syntax or functions that don't exist.

3. Final Answer:

   SELECT SUM(sales) OVER (ORDER BY date) AS running_total FROM sales_data; -> Option A

4. Quick Check:

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

Hint: Use SUM() OVER (ORDER BY ...) for running totals [OK]

Common Mistakes:

• Using GROUP BY instead of OVER()
• Trying non-existent functions like RUNNING_TOTAL()
• Adding values manually without window syntax

3. Given the table employees with columns department, salary, and name, what will the following query return?

SELECT name, department, salary, RANK() OVER (PARTITION BY department ORDER BY salary DESC) AS rank FROM employees;

medium

A. Calculates total salary per department.

B. Ranks employees by salary across all departments combined.

C. Returns employees sorted by name with no ranking.

D. Ranks employees by salary within each department, highest salary gets rank 1.

Solution

1. Step 1: Understand PARTITION BY usage

   PARTITION BY department groups rows by department for the window function.

2. Step 2: Understand RANK() OVER (ORDER BY salary DESC)

   Ranks salaries in descending order within each department, highest salary gets rank 1.

3. Final Answer:

   Ranks employees by salary within each department, highest salary gets rank 1. -> Option D

4. Quick Check:

   RANK() + PARTITION BY = rank within groups [OK]

Hint: PARTITION BY groups, ORDER BY sets rank order [OK]

Common Mistakes:

• Thinking RANK() ignores PARTITION BY
• Confusing RANK() with total aggregation
• Assuming sorting by name affects rank

4. Identify the error in this SQL query that tries to calculate a cumulative sum of sales per region:

SELECT region, sales, SUM(sales) OVER (PARTITION region ORDER BY date) AS cumulative_sales FROM sales_data;

medium

A. Missing parentheses around PARTITION BY clause.

B. Incorrect keyword; should be PARTITION BY instead of PARTITION.

C. ORDER BY cannot be used inside window functions.

D. SUM() cannot be used as a window function.

Solution

1. Step 1: Check window function syntax

   The correct syntax requires PARTITION BY, not just PARTITION.

2. Step 2: Validate other parts

   ORDER BY inside OVER() is valid for running totals; SUM() is valid as window function.

3. Final Answer:

   Incorrect keyword; should be PARTITION BY instead of PARTITION. -> Option B

4. Quick Check:

   Use PARTITION BY, not PARTITION alone [OK]

Hint: Use PARTITION BY, not just PARTITION [OK]

Common Mistakes:

• Omitting BY after PARTITION
• Thinking ORDER BY is invalid in window functions
• Believing SUM() can't be a window function

5. You want to find the difference in salary between each employee and the highest salary in their department using window functions. Which query correctly achieves this?

hard

A. SELECT name, department, salary, MAX(salary) OVER (PARTITION BY department) - salary AS diff FROM employees;

B. SELECT name, department, salary, salary - MAX(salary) OVER (PARTITION BY department) AS diff FROM employees;

C. SELECT name, department, salary, salary - MAX(salary) FROM employees GROUP BY department;

D. SELECT name, department, salary, salary - MAX(salary) FROM employees;

Solution

1. Step 1: Use MAX() as window function partitioned by department

   MAX(salary) OVER (PARTITION BY department) gives highest salary per department for each row.

2. Step 2: Calculate difference as highest salary minus employee salary

   Subtract employee salary from max salary to get positive difference.

3. Step 3: Check options for correct calculation and syntax

   SELECT name, department, salary, MAX(salary) OVER (PARTITION BY department) - salary AS diff FROM employees; correctly subtracts salary from max salary per department; SELECT name, department, salary, salary - MAX(salary) OVER (PARTITION BY department) AS diff FROM employees; reverses subtraction; The remaining options misuse GROUP BY or lack window function.

4. Final Answer:

   SELECT name, department, salary, MAX(salary) OVER (PARTITION BY department) - salary AS diff FROM employees; -> Option A

5. Quick Check:

   MAX() OVER PARTITION BY + subtraction = difference [OK]

Hint: Subtract salary from MAX() OVER partition for difference [OK]

Common Mistakes:

• Reversing subtraction order
• Using GROUP BY instead of window functions
• Omitting PARTITION BY in MAX()