CTE referencing another CTE in SQL - Time & Space Complexity

Time Complexity: CTE referencing another CTE

O(n)

Understanding Time Complexity

When using one CTE (Common Table Expression) that refers to another, it's important to see how the work grows as data grows.

We want to know how the total steps change when the input size increases.

Scenario Under Consideration

Analyze the time complexity of the following SQL snippet with two CTEs.

WITH FirstCTE AS (
  SELECT id, value FROM items WHERE value > 10
),
SecondCTE AS (
  SELECT id, value FROM FirstCTE WHERE value < 100
)
SELECT * FROM SecondCTE;

This code first filters rows with value > 10, then filters those results further for value < 100.

Identify Repeating Operations

Look for repeated work or loops in the query.

• Primary operation: Scanning and filtering rows in the table and intermediate results.
• How many times: Each CTE processes rows once, but the second CTE works on the output of the first.

How Execution Grows With Input

As the number of rows (n) grows, each CTE filters through its input once.

Input Size (n)	Approx. Operations
10	About 20 (10 for each CTE)
100	About 200 (100 for each CTE)
1000	About 2000 (1000 for each CTE)

Pattern observation: The total work grows roughly in direct proportion to the input size.

Final Time Complexity

Time Complexity: O(n)

This means the total work grows linearly with the number of rows processed.

Common Mistake

[X] Wrong: "Because one CTE references another, the work doubles or multiplies exponentially."

[OK] Correct: Each CTE processes its input once in sequence, so the total work adds up linearly, not exponentially.

Interview Connect

Understanding how queries with multiple CTEs scale helps you write efficient database code and explain your reasoning clearly in interviews.

Self-Check

"What if the second CTE referenced the original table again instead of the first CTE? How would the time complexity change?"