Moving averages with window frames in SQL - Time & Space Complexity

Time Complexity: Moving averages with window frames

O(n)

Understanding Time Complexity

We want to understand how the time to calculate moving averages changes as the data grows.

Specifically, how does the size of the data affect the work done by window frame queries?

Scenario Under Consideration

Analyze the time complexity of the following SQL query using window frames.

SELECT
  date,
  sales,
  AVG(sales) OVER (
    ORDER BY date
    ROWS BETWEEN 2 PRECEDING AND CURRENT ROW
  ) AS moving_avg
FROM sales_data;
    

This query calculates a 3-day moving average of sales ordered by date.

Identify Repeating Operations

Look for repeated work done for each row in the data.

• Primary operation: Calculating average over a window of 3 rows for each row.
• How many times: Once per row in the table.

How Execution Grows With Input

As the number of rows grows, the query calculates the average for each row's window.

Input Size (n)	Approx. Operations
10	About 10 averages of 3 rows each (around 30 operations)
100	About 100 averages of 3 rows each (around 300 operations)
1000	About 1000 averages of 3 rows each (around 3000 operations)

Pattern observation: The total work grows roughly in direct proportion to the number of rows.

Final Time Complexity

Time Complexity: O(n)

This means the time to compute moving averages grows linearly with the number of rows.

Common Mistake

[X] Wrong: "Calculating moving averages with window frames takes quadratic time because it looks at multiple rows for each row."

[OK] Correct: The window size is fixed and small, so each row only does a constant amount of work, making the total time linear, not quadratic.

Interview Connect

Understanding how window functions scale helps you explain query performance clearly and shows you can reason about data processing efficiently.

Self-Check

"What if we changed the window frame to include all previous rows instead of just 2 preceding? How would the time complexity change?"

Practice

1. What does the SQL clause ROWS BETWEEN 2 PRECEDING AND CURRENT ROW do in a window function?

easy

A. It calculates the function over the current row and the two rows before it.

B. It calculates the function over the current row and the next two rows.

C. It calculates the function over all rows in the table.

D. It calculates the function only on the current row.

Solution

1. Step 1: Understand the window frame boundaries

   The clause ROWS BETWEEN 2 PRECEDING AND CURRENT ROW means the frame includes the current row and the two rows before it.

2. Step 2: Apply to window function calculation

   The window function (like AVG) will compute its result using values from these three rows.

3. Final Answer:

   It calculates the function over the current row and the two rows before it. -> Option A

4. Quick Check:

   Window frame includes current + 2 preceding rows = C [OK]

Hint: Preceding means rows before current, including current [OK]

Common Mistakes:

• Confusing PRECEDING with FOLLOWING
• Thinking it includes future rows
• Assuming it covers entire table

2. Which of the following is the correct syntax to calculate a 3-row moving average of the column sales ordered by date?

easy

A. SELECT date, AVG(sales) OVER (ROWS BETWEEN 2 PRECEDING AND CURRENT ROW) AS moving_avg FROM sales_data;

B. SELECT date, AVG(sales) OVER (PARTITION BY date ROWS BETWEEN 2 PRECEDING AND CURRENT ROW) AS moving_avg FROM sales_data;

C. SELECT date, AVG(sales) OVER (ORDER BY date ROWS BETWEEN CURRENT ROW AND 2 FOLLOWING) AS moving_avg FROM sales_data;

D. SELECT date, AVG(sales) OVER (ORDER BY date ROWS BETWEEN 2 PRECEDING AND CURRENT ROW) AS moving_avg FROM sales_data;

Solution

1. Step 1: Identify correct window function syntax

   The correct syntax requires OVER (ORDER BY date ROWS BETWEEN 2 PRECEDING AND CURRENT ROW) to define ordering and frame.

2. Step 2: Check each option

   SELECT date, AVG(sales) OVER (ORDER BY date ROWS BETWEEN 2 PRECEDING AND CURRENT ROW) AS moving_avg FROM sales_data; uses ORDER BY with correct frame. SELECT date, AVG(sales) OVER (PARTITION BY date ROWS BETWEEN 2 PRECEDING AND CURRENT ROW) AS moving_avg FROM sales_data; wrongly uses PARTITION BY instead of ORDER BY. SELECT date, AVG(sales) OVER (ORDER BY date ROWS BETWEEN CURRENT ROW AND 2 FOLLOWING) AS moving_avg FROM sales_data; uses FOLLOWING which looks ahead, not behind. SELECT date, AVG(sales) OVER (ROWS BETWEEN 2 PRECEDING AND CURRENT ROW) AS moving_avg FROM sales_data; misses ORDER BY clause.

3. Final Answer:

   SELECT date, AVG(sales) OVER (ORDER BY date ROWS BETWEEN 2 PRECEDING AND CURRENT ROW) AS moving_avg FROM sales_data; -> Option D

4. Quick Check:

   ORDER BY + ROWS BETWEEN 2 PRECEDING AND CURRENT ROW = D [OK]

Hint: Use ORDER BY with ROWS BETWEEN for moving averages [OK]

Common Mistakes:

• Using PARTITION BY instead of ORDER BY for moving average
• Omitting ORDER BY clause
• Using FOLLOWING instead of PRECEDING

3. Given the table sales_data with columns date and amount, what is the output of this query?

SELECT date, amount, AVG(amount) OVER (ORDER BY date ROWS BETWEEN 1 PRECEDING AND CURRENT ROW) AS moving_avg FROM sales_data ORDER BY date;

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

medium

A. [{"date": "2024-01-01", "amount": 100, "moving_avg": 150}, {"date": "2024-01-02", "amount": 200, "moving_avg": 200}, {"date": "2024-01-03", "amount": 300, "moving_avg": 300}]

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

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

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

Solution

1. Step 1: Understand the window frame

   The frame includes the current row and 1 preceding row, so for each row, average the amount of that row and the previous one.

2. Step 2: Calculate moving averages row by row

   Row 1 (2024-01-01): only itself, avg = 100.
   Row 2 (2024-01-02): rows 1 and 2, avg = (100+200)/2 = 150.
   Row 3 (2024-01-03): rows 2 and 3, avg = (200+300)/2 = 250.

3. Final Answer:

   [{"date": "2024-01-01", "amount": 100, "moving_avg": 100}, {"date": "2024-01-02", "amount": 200, "moving_avg": 150}, {"date": "2024-01-03", "amount": 300, "moving_avg": 250}] -> Option B

4. Quick Check:

   Moving average includes current + 1 preceding row = A [OK]

Hint: Average current and previous row amounts for moving average [OK]

Common Mistakes:

• Including future rows instead of preceding
• Calculating average without window frame
• Assuming null for first row moving average

4. Identify the error in this SQL query for calculating a moving average:

SELECT date, amount, AVG(amount) OVER (ORDER BY date ROWS BETWEEN CURRENT ROW AND 2 PRECEDING) AS moving_avg FROM sales_data;

medium

A. AVG() cannot be used as a window function.

B. The ORDER BY clause is missing.

C. The window frame boundaries are in the wrong order; PRECEDING must come before CURRENT ROW.

D. The query is correct and will run without errors.

Solution

1. Step 1: Check window frame syntax

   The frame clause ROWS BETWEEN CURRENT ROW AND 2 PRECEDING is invalid because the start boundary must be before the end boundary.

2. Step 2: Correct the order of boundaries

   The correct syntax is ROWS BETWEEN 2 PRECEDING AND CURRENT ROW, with the smaller offset first.

3. Final Answer:

   The window frame boundaries are in the wrong order; PRECEDING must come before CURRENT ROW. -> Option C

4. Quick Check:

   Window frame start must be before end = A [OK]

Hint: Start frame boundary must be before end boundary [OK]

Common Mistakes:

• Reversing PRECEDING and CURRENT ROW order
• Thinking AVG() can't be window function
• Ignoring window frame syntax rules

5. You want to calculate a 5-day moving average of daily sales, but only include days where sales were above 100. Which SQL query correctly applies this condition inside the moving average calculation?

hard

A. SELECT date, sales, AVG(CASE WHEN sales > 100 THEN sales ELSE NULL END) OVER (ORDER BY date ROWS BETWEEN 4 PRECEDING AND CURRENT ROW) AS moving_avg FROM sales_data;

B. SELECT date, sales, AVG(sales) OVER (ORDER BY date ROWS BETWEEN 4 PRECEDING AND CURRENT ROW) WHERE sales > 100 FROM sales_data;

C. SELECT date, sales, AVG(sales) FILTER (WHERE sales > 100) OVER (ORDER BY date ROWS BETWEEN 4 PRECEDING AND CURRENT ROW) AS moving_avg FROM sales_data;

D. SELECT date, sales, AVG(sales) OVER (PARTITION BY sales > 100 ORDER BY date ROWS BETWEEN 4 PRECEDING AND CURRENT ROW) AS moving_avg FROM sales_data;

Solution

1. Step 1: Understand filtering inside window functions

   To include only sales > 100 in the average, use a CASE expression inside AVG to nullify unwanted rows.

2. Step 2: Evaluate each option

   SELECT date, sales, AVG(CASE WHEN sales > 100 THEN sales ELSE NULL END) OVER (ORDER BY date ROWS BETWEEN 4 PRECEDING AND CURRENT ROW) AS moving_avg FROM sales_data; uses CASE to include sales > 100, replacing others with NULL (ignored by AVG). SELECT date, sales, AVG(sales) OVER (ORDER BY date ROWS BETWEEN 4 PRECEDING AND CURRENT ROW) WHERE sales > 100 FROM sales_data; filters rows after window function (invalid syntax). SELECT date, sales, AVG(sales) FILTER (WHERE sales > 100) OVER (ORDER BY date ROWS BETWEEN 4 PRECEDING AND CURRENT ROW) AS moving_avg FROM sales_data; uses FILTER clause which is not standard in all SQL versions. SELECT date, sales, AVG(sales) OVER (PARTITION BY sales > 100 ORDER BY date ROWS BETWEEN 4 PRECEDING AND CURRENT ROW) AS moving_avg FROM sales_data; partitions by boolean condition, which changes grouping incorrectly.

3. Final Answer:

   SELECT date, sales, AVG(CASE WHEN sales > 100 THEN sales ELSE NULL END) OVER (ORDER BY date ROWS BETWEEN 4 PRECEDING AND CURRENT ROW) AS moving_avg FROM sales_data; -> Option A

4. Quick Check:

   Use CASE inside AVG to filter rows in window [OK]

Hint: Use CASE inside AVG to filter values in window frame [OK]

Common Mistakes:

• Filtering rows outside window function
• Using PARTITION BY for filtering condition
• Assuming FILTER clause always works