Window frame (ROWS BETWEEN, RANGE BETWEEN) in PostgreSQL - Time & Space Complexity

Time Complexity: Window frame (ROWS BETWEEN, RANGE BETWEEN)

O(n)

Understanding Time Complexity

When using window frames like ROWS BETWEEN or RANGE BETWEEN in SQL, it is important to understand how the query's work grows as the data size increases.

We want to know how the number of rows processed affects the time it takes to compute the window functions.

Scenario Under Consideration

Analyze the time complexity of the following PostgreSQL query using a window frame.

SELECT employee_id, department_id, salary,
       AVG(salary) OVER (
         PARTITION BY department_id
         ORDER BY employee_id
         ROWS BETWEEN 2 PRECEDING AND CURRENT ROW
       ) AS avg_salary
FROM employees;
    

This query calculates the average salary for each employee considering the current row and the two previous rows within the same department.

Identify Repeating Operations

Look for repeated work done for each row in the window frame.

• Primary operation: Calculating the average over a sliding window of up to 3 rows per employee.
• How many times: For each row, the database processes up to 3 rows to compute the average.

How Execution Grows With Input

As the number of rows grows, the work per row depends on the window frame size.

Input Size (n)	Approx. Operations
10	About 10 x 3 = 30 operations
100	About 100 x 3 = 300 operations
1000	About 1000 x 3 = 3000 operations

Pattern observation: The total work grows roughly in a straight line with the number of rows, multiplied by the fixed window size.

Final Time Complexity

Time Complexity: O(n)

This means the time to compute the window function grows linearly with the number of rows, assuming the window frame size is fixed.

Common Mistake

[X] Wrong: "The window frame always causes the query to do work on all rows for each row, so it's quadratic."

[OK] Correct: When the window frame size is fixed (like 2 preceding rows), the database only looks at a small, constant number of rows per row, so the work grows linearly, not quadratically.

Interview Connect

Understanding how window frames affect query performance helps you write efficient SQL and explain your reasoning clearly in interviews.

Self-Check

What if we changed the window frame from ROWS BETWEEN 2 PRECEDING AND CURRENT ROW to RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW? How would the time complexity change?

Practice

1. What does the ROWS BETWEEN clause specify in a window function?

easy

A. It defines the frame by counting rows relative to the current row position.

B. It defines the frame by counting rows based on the value range in the ORDER BY column.

C. It filters rows before applying the window function.

D. It sorts the rows before applying the window function.

Solution

1. Step 1: Understand window frame types

   Window frames can be defined by position (ROWS) or by value range (RANGE).

2. Step 2: Identify what ROWS BETWEEN does

   ROWS BETWEEN counts rows relative to the current row's position, not by values.

3. Final Answer:

   It defines the frame by counting rows relative to the current row position. -> Option A

4. Quick Check:

   ROWS BETWEEN = position-based frame [OK]

Hint: ROWS counts rows by position, RANGE counts by value range [OK]

Common Mistakes:

• Confusing ROWS with RANGE
• Thinking ROWS filters rows
• Assuming ROWS sorts data

2. Which of the following is the correct syntax to specify a window frame using RANGE BETWEEN from 5 preceding to current row?

easy

A. RANGE BETWEEN 5 PRECEDING AND CURRENT ROW

B. RANGE BETWEEN CURRENT ROW AND 5 PRECEDING

C. ROWS BETWEEN 5 PRECEDING AND CURRENT ROW

D. ROWS BETWEEN CURRENT ROW AND 5 PRECEDING

Solution

1. Step 1: Recall RANGE BETWEEN syntax

   The syntax is: RANGE BETWEEN <start> AND <end>, where start must be before end logically.

2. Step 2: Check order of frame boundaries

   5 PRECEDING comes before CURRENT ROW, so 'RANGE BETWEEN 5 PRECEDING AND CURRENT ROW' is correct.

3. Final Answer:

   RANGE BETWEEN 5 PRECEDING AND CURRENT ROW -> Option A

4. Quick Check:

   Correct RANGE syntax = RANGE BETWEEN 5 PRECEDING AND CURRENT ROW [OK]

Hint: Frame boundaries go from earlier to later, e.g., 5 PRECEDING to CURRENT ROW [OK]

Common Mistakes:

• Reversing frame boundaries order
• Using ROWS syntax with RANGE
• Omitting BETWEEN keyword

3. Given the table sales(date, amount) ordered by date, what will the following query return?

SELECT date, amount, SUM(amount) OVER (ORDER BY date RANGE BETWEEN INTERVAL '1 day' PRECEDING AND CURRENT ROW) AS running_sum FROM sales;

medium

A. Sum of amounts for the current row and 1 row before

B. Sum of all amounts up to the current row

C. Sum of amounts for the current date and the previous day

D. Sum of amounts for the current date only

Solution

1. Step 1: Understand RANGE BETWEEN with INTERVAL

   RANGE BETWEEN INTERVAL '1 day' PRECEDING AND CURRENT ROW includes rows with date values within 1 day before current row's date.

2. Step 2: Interpret the SUM window function

   SUM(amount) will add amounts for rows dated from 1 day before up to current date.

3. Final Answer:

   Sum of amounts for the current date and the previous day -> Option C

4. Quick Check:

   RANGE with INTERVAL sums by date range [OK]

Hint: RANGE with INTERVAL sums values in date/time range [OK]

Common Mistakes:

• Confusing RANGE with ROWS counting
• Assuming ROWS behavior for RANGE
• Ignoring INTERVAL meaning

4. Identify the error in this window frame clause:

SUM(amount) OVER (ORDER BY date ROWS BETWEEN CURRENT ROW AND 3 PRECEDING)

medium

A. The clause is syntactically correct.

B. ROWS cannot be used with ORDER BY date.

C. SUM cannot be used as a window function.

D. The frame boundaries are reversed; '3 PRECEDING' should come before 'CURRENT ROW'.

Solution

1. Step 1: Check frame boundary order

   Frame boundaries must go from earlier to later, so '3 PRECEDING' should be before 'CURRENT ROW'.

2. Step 2: Validate syntax correctness

   Using ROWS with ORDER BY date and SUM is valid, so no other syntax errors.

3. Final Answer:

   The frame boundaries are reversed; '3 PRECEDING' should come before 'CURRENT ROW'. -> Option D

4. Quick Check:

   Frame boundaries order matters [OK]

Hint: Frame start must be before frame end [OK]

Common Mistakes:

• Reversing frame boundaries
• Thinking ROWS can't use ORDER BY
• Misunderstanding window function usage

5. You want to calculate a moving average of sales amounts over the last 7 days including the current day, but your sales table has multiple sales per day. Which window frame clause correctly computes this using RANGE?

hard

A. RANGE BETWEEN INTERVAL '7 days' PRECEDING AND CURRENT ROW

B. RANGE BETWEEN INTERVAL '6 days' PRECEDING AND CURRENT ROW

C. ROWS BETWEEN 6 PRECEDING AND CURRENT ROW

D. ROWS BETWEEN 7 PRECEDING AND CURRENT ROW

Solution

1. Step 1: Understand the requirement

   We want a 7-day moving average including current day, so the frame covers 6 days before plus current day (total 7 days).

2. Step 2: Choose correct frame type

   Since multiple sales per day exist, using RANGE with INTERVAL ensures all rows within date range are included.

3. Step 3: Select correct interval

   INTERVAL '6 days' PRECEDING to CURRENT ROW covers 7 days total (6 before + current).

4. Final Answer:

   RANGE BETWEEN INTERVAL '6 days' PRECEDING AND CURRENT ROW -> Option B

5. Quick Check:

   Use RANGE with 6 days preceding for 7-day window [OK]

Hint: RANGE with INTERVAL covers value ranges, perfect for dates [OK]

Common Mistakes:

• Using ROWS which counts rows, not days
• Choosing wrong interval length
• Confusing 6 days preceding with 7 days