PARTITION BY for grouping windows in PostgreSQL - Time & Space Complexity

Time Complexity: PARTITION BY for grouping windows

O(n log n)

Understanding Time Complexity

We want to understand how the time needed to run a query with PARTITION BY grows as the data gets bigger.

Specifically, how does grouping rows into partitions 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 with PARTITION BY.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The database groups rows by department_id, then sorts each group by salary.
• How many times: It does this for each partition (each department), processing all rows once.

How Execution Grows With Input

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

Input Size (n)	Approx. Operations
10	About 10 log 10 operations (sorting small groups)
100	About 100 log 100 operations (sorting larger groups)
1000	About 1000 log 1000 operations (sorting even larger groups)

Pattern observation: The work grows a bit faster than the number of rows because sorting inside each partition takes more time 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 happens within each group.

Common Mistake

[X] Wrong: "PARTITION BY just groups rows and doesn't add any extra work."

[OK] Correct: Grouping means the database must sort or organize rows inside each group, which takes extra time especially as data grows.

Interview Connect

Understanding how PARTITION BY affects query time helps you explain how databases handle grouped data efficiently, a useful skill for real projects and interviews.

Self-Check

"What if we removed ORDER BY inside the window function? How would the time complexity change?"

Practice

1. What does the PARTITION BY clause do in a window function in PostgreSQL?

easy

A. It filters rows before the window function is applied.

B. It divides the rows into groups to perform calculations within each group.

C. It sorts the entire table before applying the window function.

D. It removes duplicate rows from the result set.

Solution

1. Step 1: Understand the role of PARTITION BY

   PARTITION BY groups rows so window functions calculate results within each group separately.

2. Step 2: Differentiate from filtering and sorting

   Filtering removes rows, sorting orders rows, but PARTITION BY only groups rows without removing or sorting them globally.

3. Final Answer:

   It divides the rows into groups to perform calculations within each group. -> Option B

4. Quick Check:

   PARTITION BY = grouping rows for window functions [OK]

Hint: Remember: PARTITION BY groups rows, it does not filter or sort [OK]

Common Mistakes:

• Confusing PARTITION BY with WHERE filtering
• Thinking PARTITION BY sorts all rows
• Assuming PARTITION BY removes duplicates

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

easy

A. SELECT col, SUM(value) OVER (PARTITION BY col ORDER BY date) FROM table;

B. SELECT col, SUM(value) PARTITION BY col FROM table;

C. SELECT col, SUM(value) OVER PARTITION BY col FROM table;

D. SELECT col, SUM(value) WHERE PARTITION BY col FROM table;

Solution

1. Step 1: Identify correct window function syntax

   The correct syntax uses OVER() with PARTITION BY inside parentheses.

2. Step 2: Check each option

   SELECT col, SUM(value) OVER (PARTITION BY col ORDER BY date) FROM table; correctly uses SUM(value) OVER (PARTITION BY col ORDER BY date). Others misuse PARTITION BY outside OVER or with WHERE.

3. Final Answer:

   SELECT col, SUM(value) OVER (PARTITION BY col ORDER BY date) FROM table; -> Option A

4. Quick Check:

   Window functions use OVER() with PARTITION BY inside [OK]

Hint: PARTITION BY must be inside OVER() parentheses [OK]

Common Mistakes:

• Placing PARTITION BY outside OVER()
• Using WHERE instead of PARTITION BY
• Omitting OVER() entirely

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

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

medium

A. Monthly sales amount without any cumulative calculation.

B. Total sales amount for all regions combined.

C. An error because PARTITION BY cannot be combined with ORDER BY.

D. A running total of sales amount per region ordered by month.

Solution

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

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

2. Step 2: Analyze the output

   Each row shows the cumulative sum of amount for that region up to the current month.

3. Final Answer:

   A running total of sales amount per region ordered by month. -> Option D

4. Quick Check:

   PARTITION BY groups, ORDER BY defines running total order [OK]

Hint: Running totals use PARTITION BY with ORDER BY inside OVER() [OK]

Common Mistakes:

• Thinking it sums all regions together
• Ignoring ORDER BY for running total
• Assuming syntax error with ORDER BY in window

4. Identify the error in this query:

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

medium

A. Missing parentheses around PARTITION BY and ORDER BY clauses.

B. RANK() cannot be used with PARTITION BY.

C. ORDER BY cannot be used inside window functions.

D. employee_id must be included in PARTITION BY.

Solution

1. Step 1: Check window function syntax

   Window functions require OVER() with parentheses enclosing PARTITION BY and ORDER BY.

2. Step 2: Identify missing parentheses

   The query misses parentheses after OVER, causing syntax error.

3. Final Answer:

   Missing parentheses around PARTITION BY and ORDER BY clauses. -> Option A

4. Quick Check:

   OVER() must enclose PARTITION BY and ORDER BY [OK]

Hint: Always use parentheses after OVER() for window clauses [OK]

Common Mistakes:

• Omitting parentheses after OVER
• Thinking ORDER BY is not allowed in window functions
• Assuming all columns must be in PARTITION BY

5. You want to calculate the average sales per product category and also show each sale's rank within its category by sale date. Which query correctly uses PARTITION BY to achieve this?

hard

A. SELECT product, category, sale_date, amount, AVG(amount) OVER (PARTITION BY sale_date), RANK() OVER (PARTITION BY product ORDER BY category) FROM sales;

B. SELECT product, category, sale_date, amount, AVG(amount) PARTITION BY category, RANK() PARTITION BY category ORDER BY sale_date FROM sales;

C. SELECT product, category, sale_date, amount, AVG(amount) OVER (PARTITION BY category), RANK() OVER (PARTITION BY category ORDER BY sale_date) FROM sales;

D. SELECT product, category, sale_date, amount, AVG(amount) OVER (ORDER BY category), RANK() OVER (ORDER BY sale_date) FROM sales;

Solution

1. Step 1: Use AVG() with PARTITION BY category

   AVG(amount) OVER (PARTITION BY category) calculates average sales per category.

2. Step 2: Use RANK() with PARTITION BY category ordered by sale_date

   RANK() OVER (PARTITION BY category ORDER BY sale_date) ranks sales within each category by date.

3. Step 3: Verify syntax correctness

   SELECT product, category, sale_date, amount, AVG(amount) OVER (PARTITION BY category), RANK() OVER (PARTITION BY category ORDER BY sale_date) FROM sales; uses correct OVER() syntax with PARTITION BY and ORDER BY clauses for both functions.

4. Final Answer:

   SELECT product, category, sale_date, amount, AVG(amount) OVER (PARTITION BY category), RANK() OVER (PARTITION BY category ORDER BY sale_date) FROM sales; -> Option C

5. Quick Check:

   Use PARTITION BY category inside OVER() for grouping [OK]

Hint: Use OVER(PARTITION BY category) for grouping in window functions [OK]

Common Mistakes:

• Omitting OVER() or PARTITION BY
• Mixing PARTITION BY columns incorrectly
• Using PARTITION BY without parentheses