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?"