Window frame specification (ROWS BETWEEN) in SQL - Time & Space Complexity

Time Complexity: Window frame specification (ROWS BETWEEN)

O(n)

Understanding Time Complexity

When using window functions with a frame like ROWS BETWEEN, the database processes rows relative to the current one.

We want to understand how the work grows as the number of rows increases.

Scenario Under Consideration

Analyze the time complexity of this SQL query using a window frame:

SELECT employee_id, salary,
       AVG(salary) OVER (
         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 and two previous rows.

Identify Repeating Operations

Look at what repeats as the query runs:

• Primary operation: For each row, calculate average over a small window of up to 3 rows.
• How many times: Once per row in the table.

How Execution Grows With Input

As the number of rows grows, the work per row stays about the same because the window size is fixed.

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

Pattern observation: The total work grows linearly with the number of rows because the window size is fixed.

Final Time Complexity

Time Complexity: O(n)

This means the total work grows in direct proportion to the number of rows in the table.

Common Mistake

[X] Wrong: "Because the window looks at multiple rows, the time must grow much faster than the number of rows."

[OK] Correct: The window size is fixed and small, so each row only does a small, constant amount of work regardless of total rows.

Interview Connect

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

Self-Check

"What if the window frame changed to ROWS 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. The range of rows to include relative to the current row for calculation

B. The order in which rows are sorted before aggregation

C. The columns to group by in the query

D. The filter condition for rows in the table

Solution

1. Step 1: Understand window function frame

   The window frame defines which rows are considered for each calculation in a window function.

2. Step 2: Role of ROWS BETWEEN

   The ROWS BETWEEN clause specifies the exact range of rows relative to the current row to include in the calculation.

3. Final Answer:

   The range of rows to include relative to the current row for calculation -> Option A

4. Quick Check:

   ROWS BETWEEN controls row range = D [OK]

Hint: ROWS BETWEEN defines which rows to include around current row [OK]

Common Mistakes:

• Confusing ROWS BETWEEN with ORDER BY
• Thinking it filters rows from the table
• Mixing it up with GROUP BY

2. Which of the following is the correct syntax to specify a window frame from 2 rows before to current row using ROWS BETWEEN?

easy

A. ROWS BETWEEN 2 PRECEDING AND CURRENT ROW

B. ROWS BETWEEN CURRENT ROW AND 2 PRECEDING

C. ROWS BETWEEN 2 FOLLOWING AND CURRENT ROW

D. ROWS BETWEEN CURRENT ROW AND 2 FOLLOWING

Solution

1. Step 1: Understand frame boundaries order

   The syntax is ROWS BETWEEN X AND Y where X is the start and Y is the end of the frame.

2. Step 2: Identify correct order for 2 rows before to current

   Since 2 rows before is the start and current row is the end, it must be ROWS BETWEEN 2 PRECEDING AND CURRENT ROW.

3. Final Answer:

   ROWS BETWEEN 2 PRECEDING AND CURRENT ROW -> Option A

4. Quick Check:

   Start to end order matters = A [OK]

Hint: Start boundary comes first, then end boundary in ROWS BETWEEN [OK]

Common Mistakes:

• Reversing the order of boundaries
• Using FOLLOWING instead of PRECEDING incorrectly
• Omitting CURRENT ROW keyword

3. Given the table sales(date, amount) ordered by date, what is the output of this query?

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

Assuming data:
date | amount
2024-01-01 | 100
2024-01-02 | 200
2024-01-03 | 300

medium

A. [{"date": "2024-01-01", "amount": 100, "running_sum": 300}, {"date": "2024-01-02", "amount": 200, "running_sum": 500}, {"date": "2024-01-03", "amount": 300, "running_sum": 600}]

B. [{"date": "2024-01-01", "amount": 100, "running_sum": 100}, {"date": "2024-01-02", "amount": 200, "running_sum": 200}, {"date": "2024-01-03", "amount": 300, "running_sum": 300}]

C. [{"date": "2024-01-01", "amount": 100, "running_sum": 100}, {"date": "2024-01-02", "amount": 200, "running_sum": 300}, {"date": "2024-01-03", "amount": 300, "running_sum": 500}]

D. [{"date": "2024-01-01", "amount": 100, "running_sum": null}, {"date": "2024-01-02", "amount": 200, "running_sum": 300}, {"date": "2024-01-03", "amount": 300, "running_sum": 500}]

Solution

1. Step 1: Understand frame range

   The frame includes the current row and 1 row before it, so for each row sum amounts of current and previous row.

2. Step 2: Calculate running sums

   Row 1: only 100 (no previous row), Row 2: 100+200=300, Row 3: 200+300=500.

3. Final Answer:

   [{"date": "2024-01-01", "amount": 100, "running_sum": 100}, {"date": "2024-01-02", "amount": 200, "running_sum": 300}, {"date": "2024-01-03", "amount": 300, "running_sum": 500}] -> Option C

4. Quick Check:

   Sum current + 1 preceding = A [OK]

Hint: Sum includes current and 1 previous row amounts [OK]

Common Mistakes:

• Including 2 rows before instead of 1
• Ignoring the order of rows
• Assuming NULL for first row sum

4. Identify the error in this SQL window function:

SELECT id, value, AVG(value) OVER (ORDER BY id ROWS BETWEEN CURRENT ROW AND 2 PRECEDING) AS avg_val FROM data;

medium

A. ORDER BY cannot be used with ROWS BETWEEN

B. The frame boundaries are reversed; start must be before end

C. Missing PARTITION BY clause

D. AVG cannot be used as a window function

Solution

1. Step 1: Check frame boundaries order

   The frame must start with the earlier row and end with the later row. Here, CURRENT ROW is after 2 PRECEDING, so order is reversed.

2. Step 2: Identify correct syntax

   The correct syntax is ROWS BETWEEN 2 PRECEDING AND CURRENT ROW, not the other way around.

3. Final Answer:

   The frame boundaries are reversed; start must be before end -> Option B

4. Quick Check:

   Frame start must be before end = C [OK]

Hint: Start boundary must be earlier than end boundary [OK]

Common Mistakes:

• Swapping start and end boundaries
• Assuming PARTITION BY is mandatory
• Thinking ORDER BY disallows ROWS BETWEEN

5. You want to calculate a moving average of the last 3 sales amounts including the current row, but your data has gaps in dates. Which window frame specification ensures exactly 3 rows are included regardless of date gaps?

hard

A. RANGE BETWEEN INTERVAL '2' DAY PRECEDING AND CURRENT ROW

B. RANGE BETWEEN 2 PRECEDING AND CURRENT ROW

C. ROWS BETWEEN CURRENT ROW AND 2 FOLLOWING

D. ROWS BETWEEN 2 PRECEDING AND CURRENT ROW

Solution

1. Step 1: Understand difference between ROWS and RANGE

   ROWS counts physical rows, while RANGE counts logical values like dates, which can skip rows if dates have gaps.

2. Step 2: Choose frame to include 3 rows

   Using ROWS BETWEEN 2 PRECEDING AND CURRENT ROW always includes exactly 3 rows regardless of date gaps.

3. Final Answer:

   ROWS BETWEEN 2 PRECEDING AND CURRENT ROW -> Option D

4. Quick Check:

   ROWS counts rows, RANGE counts values = B [OK]

Hint: Use ROWS to count exact rows, not RANGE for gaps [OK]

Common Mistakes:

• Using RANGE which depends on value gaps
• Confusing FOLLOWING with PRECEDING
• Assuming RANGE counts rows