Practical window function patterns in PostgreSQL - Time & Space Complexity

Time Complexity: Practical window function patterns

O(n log n)

Understanding Time Complexity

When using window functions in PostgreSQL, it's important to understand how the time to run your query changes as your data grows.

We want to know how the query's work increases when the number of rows gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following window function 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 inside the query.

• Primary operation: Sorting rows within each department to assign ranks.
• How many times: Once per department, sorting 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 (sorting 10 rows)
100	About 100 log 100 (sorting 100 rows)
1000	About 1000 log 1000 (sorting 1000 rows)

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 query grows a little faster than the number of rows because sorting is involved.

Common Mistake

[X] Wrong: "Window functions always run in linear time because they just add a column."

[OK] Correct: Window functions often require sorting or partitioning, which can take more time than just scanning rows.

Interview Connect

Understanding how window functions scale helps you write efficient queries and explain your reasoning clearly in real-world situations.

Self-Check

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

Practice

1. What does the ROW_NUMBER() OVER (PARTITION BY department ORDER BY salary DESC) window function do in a query?

easy

A. Counts the number of employees in each department.

B. Assigns a unique rank to each employee within their department based on salary, starting at 1 for the highest salary.

C. Calculates the total salary for each department.

D. Returns the average salary of all employees.

Solution

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

   The function assigns a unique sequential number to rows within each department group.

2. Step 2: ORDER BY salary DESC ranks highest salary first

   Ordering by salary descending means the highest salary gets row number 1 in each department.

3. Final Answer:

   Assigns a unique rank to each employee within their department based on salary, starting at 1 for the highest salary. -> Option B

4. Quick Check:

   ROW_NUMBER() with PARTITION BY and ORDER BY = ranked rows [OK]

Hint: ROW_NUMBER() numbers rows per group ordered by criteria [OK]

Common Mistakes:

• Confusing ROW_NUMBER() with COUNT() or SUM()
• Ignoring PARTITION BY and thinking it ranks globally
• Assuming it calculates totals or averages

2. Which of the following is the correct syntax to calculate a running total of sales ordered by date using window functions in PostgreSQL?

easy

A. SELECT date, sales, SUM(sales) PARTITION BY date FROM sales_data;

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

C. SELECT date, sales, SUM(sales) WHERE ORDER BY date FROM sales_data;

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

Solution

1. Step 1: Identify correct window function syntax

   SUM(sales) OVER (ORDER BY date) calculates running total by ordering rows by date.

2. Step 2: Check other options for syntax errors

   The incorrect options misuse PARTITION BY without OVER(), use WHERE incorrectly, or confuse GROUP BY with window functions.

3. Final Answer:

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

4. Quick Check:

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

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

Common Mistakes:

• Using PARTITION BY without OVER()
• Trying to use WHERE inside window function
• Confusing GROUP BY with window functions

3. Given the table sales(date, amount) with rows:
('2024-01-01', 100), ('2024-01-02', 150), ('2024-01-03', 200)
What is the output of this query?

SELECT date, amount, SUM(amount) OVER (ORDER BY date ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS running_total FROM sales ORDER BY date;

medium

A. [('2024-01-01', 100, 450), ('2024-01-02', 150, 350), ('2024-01-03', 200, 200)]

B. [('2024-01-01', 100, 100), ('2024-01-02', 150, 150), ('2024-01-03', 200, 200)]

C. [('2024-01-01', 100, 100), ('2024-01-02', 150, 250), ('2024-01-03', 200, 450)]

D. [('2024-01-01', 100, NULL), ('2024-01-02', 150, NULL), ('2024-01-03', 200, NULL)]

Solution

1. Step 1: Understand SUM() OVER with frame

   The frame includes all rows from the start up to current row ordered by date, so it sums cumulatively.

2. Step 2: Calculate running totals row by row

   Row 1: 100; Row 2: 100+150=250; Row 3: 250+200=450.

3. Final Answer:

   [('2024-01-01', 100, 100), ('2024-01-02', 150, 250), ('2024-01-03', 200, 450)] -> Option C

4. Quick Check:

   Running total sums up to current row [OK]

Hint: ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW sums cumulatively [OK]

Common Mistakes:

• Ignoring frame clause and expecting total sum on all rows
• Confusing running total with simple SUM() aggregation
• Assuming NULLs appear without reason

4. You wrote this query to rank employees by salary within each department:

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

But the query returns the same rank for all employees regardless of department. What is the likely mistake?

medium

A. Missing PARTITION BY clause inside OVER()

B. ORDER BY salary ASC instead of DESC

C. Using RANK() instead of ROW_NUMBER()

D. Not ordering the final result by department

Solution

1. Step 1: Check PARTITION BY usage

   If PARTITION BY is missing or incorrect, ranking happens over entire table, ignoring departments.

2. Step 2: Confirm ORDER BY and function choice

   ORDER BY DESC is correct for highest salary first; RANK() is appropriate for ties; ordering final result doesn't affect ranking.

3. Final Answer:

   Missing PARTITION BY clause inside OVER() -> Option A

4. Quick Check:

   PARTITION BY groups rows for ranking [OK]

Hint: Always include PARTITION BY to rank within groups [OK]

Common Mistakes:

• Forgetting PARTITION BY causes global ranking
• Confusing RANK() and ROW_NUMBER() effects
• Thinking ORDER BY outside OVER() affects ranking

5. You want to find each employee's salary difference compared to the previous employee in the same department ordered by salary descending. Which query correctly uses window functions to achieve this?

hard

A. SELECT employee_id, department, salary, salary - LAG(salary) OVER (PARTITION BY department ORDER BY salary DESC) AS salary_diff FROM employees;

B. SELECT employee_id, department, salary, salary - LEAD(salary) OVER (ORDER BY salary) AS salary_diff FROM employees;

C. SELECT employee_id, department, salary, salary - LAG(salary) FROM employees GROUP BY department ORDER BY salary DESC;

D. SELECT employee_id, department, salary, salary - FIRST_VALUE(salary) OVER (PARTITION BY department) AS salary_diff FROM employees;

Solution

1. Step 1: Use LAG() to get previous row's salary per department

   LAG(salary) OVER (PARTITION BY department ORDER BY salary DESC) gets previous salary in descending order within department.

2. Step 2: Subtract previous salary from current salary

   salary - LAG(salary) calculates difference compared to previous employee.

3. Final Answer:

   SELECT employee_id, department, salary, salary - LAG(salary) OVER (PARTITION BY department ORDER BY salary DESC) AS salary_diff FROM employees; -> Option A

4. Quick Check:

   LAG() gets previous row value for difference [OK]

Hint: Use LAG() with PARTITION BY and ORDER BY for previous row values [OK]

Common Mistakes:

• Using LEAD() instead of LAG() for previous row
• Omitting PARTITION BY causing wrong grouping
• Trying to use aggregate functions without OVER()