Multiple CTEs in one query in SQL - Time & Space Complexity

Time Complexity: Multiple CTEs in one query

O(n * m)

Understanding Time Complexity

When using multiple CTEs (Common Table Expressions) in one SQL query, it's important to understand how the query's work grows as the data grows.

We want to know how the time to run the query changes when the input data gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following SQL query using multiple CTEs.

WITH cte1 AS (
  SELECT id, value FROM table1 WHERE value > 10
),
cte2 AS (
  SELECT id, description FROM table2
),
cte3 AS (
  SELECT cte1.id, cte1.value, cte2.description
  FROM cte1
  JOIN cte2 ON cte1.id = cte2.id
)
SELECT * FROM cte3 WHERE value < 100;
    

This query defines three CTEs: filtering table1, selecting from table2, then joining them before filtering again.

Identify Repeating Operations

Look for repeated work inside the query.

• Primary operation: Scanning and filtering rows in table1 and table2, then joining rows from both.
• How many times: Each table is scanned once, but the join compares rows from both tables, which depends on their sizes.

How Execution Grows With Input

As the number of rows in table1 and table2 grows, the work to scan and join them grows too.

Input Size (rows in each table)	Approx. Operations
10	About 10 scans + 10x10 = 100 join checks
100	About 100 scans + 100x100 = 10,000 join checks
1000	About 1000 scans + 1000x1000 = 1,000,000 join checks

Pattern observation: The join work grows much faster than scanning alone, roughly multiplying the sizes of both tables.

Final Time Complexity

Time Complexity: O(n * m)

This means the time grows roughly by multiplying the number of rows in the two tables being joined.

Common Mistake

[X] Wrong: "Using multiple CTEs means the query runs multiple times, so time multiplies by the number of CTEs."

[OK] Correct: The database usually runs each CTE once and reuses results, so time depends mostly on the size of data and join operations, not the count of CTEs.

Interview Connect

Understanding how multiple CTEs affect query time helps you explain your thought process clearly and shows you know how databases handle complex queries.

Self-Check

"What if we replaced the join with a simple union of the two CTEs? How would the time complexity change?"