Why window functions are powerful in PostgreSQL - Performance Analysis

Time Complexity: Why window functions are powerful

O(n log n)

Understanding Time Complexity

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

How does using window functions affect the work the database does?

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

Look for repeated work done by the query.

• Primary operation: Sorting employees within each department to assign ranks.
• How many times: Once per department group, but overall it processes all rows.

How Execution Grows With Input

As the number of employees grows, the database must sort more data within each department.

Input Size (n)	Approx. Operations
10	About 10 sorting steps
100	About 100 sorting steps
1000	About 1000 sorting steps

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

Final Time Complexity

Time Complexity: O(n log n)

This means the time grows a bit faster than the number of rows because sorting is involved.

Common Mistake

[X] Wrong: "Window functions just scan the data once, so they are always very fast."

[OK] Correct: Window functions often require sorting or partitioning, which can take more time as data grows.

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 removed the PARTITION BY clause? How would the time complexity change?"

Practice

1. What is the main advantage of using window functions in PostgreSQL?

easy

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

B. They allow calculations across rows without collapsing the result into fewer rows.

C. They replace the need for JOIN operations.

D. They automatically create new tables for grouped data.

Solution

1. Step 1: Understand window function behavior

   Window functions perform calculations across a set of rows related to the current row but keep all original rows in the output.

2. Step 2: Compare with aggregation

   Unlike aggregation functions that reduce rows, window functions keep row details while adding calculated columns.

3. Final Answer:

   They allow calculations across rows without collapsing the result into fewer rows. -> Option B

4. Quick Check:

   Window functions keep rows and add calculations [OK]

Hint: Window functions keep all rows and add calculations [OK]

Common Mistakes:

• Thinking window functions reduce rows like GROUP BY
• Confusing window functions with JOINs
• Believing 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 sales, SUM(sales) FROM sales_table WHERE ORDER BY date;

B. SELECT sales, SUM(sales) GROUP BY date FROM sales_table;

C. SELECT sales, SUM(sales) OVER (ORDER BY date) FROM sales_table;

D. SELECT sales, SUM(sales) PARTITION BY date FROM sales_table;

Solution

1. Step 1: Identify window function syntax

   The correct syntax uses SUM() OVER() with ORDER BY inside OVER() to calculate running totals.

2. Step 2: Check each option

   SELECT sales, SUM(sales) OVER (ORDER BY date) FROM sales_table; correctly uses SUM(sales) OVER (ORDER BY date). Options A, B, and D misuse GROUP BY, WHERE, or PARTITION BY without OVER().

3. Final Answer:

   SELECT sales, SUM(sales) OVER (ORDER BY date) FROM sales_table; -> Option C

4. Quick Check:

   Running total uses SUM() OVER (ORDER BY ...) [OK]

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

Common Mistakes:

• Using GROUP BY instead of OVER()
• Placing ORDER BY outside OVER()
• Using PARTITION BY without OVER()

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

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

medium

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

B. Ranks all employees together ignoring department, highest salary gets rank 1.

C. Calculates total salary per department.

D. Returns an error because RANK() cannot be used with PARTITION BY.

Solution

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

   RANK() assigns ranks within each partition (department) ordered by salary descending.

2. Step 2: Analyze query output

   Each employee gets a rank starting at 1 for highest salary in their department, ties get same rank.

3. Final Answer:

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

4. Quick Check:

   RANK() with PARTITION BY ranks within groups [OK]

Hint: RANK() with PARTITION BY ranks within groups [OK]

Common Mistakes:

• Thinking RANK() ignores PARTITION BY
• Confusing RANK() with aggregation
• Assuming RANK() causes errors with PARTITION BY

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

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

medium

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

B. Missing parentheses around PARTITION BY clause.

C. ORDER BY cannot be used inside OVER().

D. PARTITION keyword should be PARTITION BY.

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, and SUM() is allowed as a window function.

3. Final Answer:

   PARTITION keyword should be PARTITION BY. -> Option D

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 OVER()
• Believing SUM() can't be a window function

5. You want to find each employee's salary difference from the average salary in their department using window functions. Which query correctly achieves this?

hard

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

B. SELECT employee, salary, salary - AVG(salary) FROM employees GROUP BY department;

C. SELECT employee, salary, salary - AVG(salary) OVER () AS diff FROM employees;

D. SELECT employee, salary, salary - AVG(salary) PARTITION BY department FROM employees;

Solution

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

   AVG(salary) OVER (PARTITION BY department) calculates average salary per department without grouping rows.

2. Step 2: Subtract average from each employee's salary

   Subtracting this average from salary gives the difference per employee.

3. Final Answer:

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

4. Quick Check:

   Window AVG() with PARTITION BY calculates group average per row [OK]

Hint: Use AVG() OVER (PARTITION BY ...) for group averages per row [OK]

Common Mistakes:

• Using GROUP BY which collapses rows
• Omitting PARTITION BY causing overall average
• Incorrect syntax without OVER()