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

Time Complexity: Multiple CTEs in one query

O(n)

Understanding Time Complexity

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

We want to know how the total steps needed change when the input data gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following query with multiple CTEs.

WITH cte1 AS (
  SELECT * FROM orders WHERE order_date > '2023-01-01'
),
cte2 AS (
  SELECT customer_id, COUNT(*) AS order_count FROM cte1 GROUP BY customer_id
),
cte3 AS (
  SELECT customer_id FROM cte2 WHERE order_count > 5
)
SELECT * FROM customers WHERE id IN (SELECT customer_id FROM cte3);
    

This query filters recent orders, counts orders per customer, then selects customers with more than 5 orders.

Identify Repeating Operations

Look for repeated work inside the query.

• Primary operation: Scanning and grouping rows in the orders table.
• How many times: Each CTE runs once in sequence, but the grouping scans all filtered orders.

How Execution Grows With Input

As the number of orders grows, the work to scan and group them grows too.

Input Size (n)	Approx. Operations
10	About 10 scans and groups
100	About 100 scans and groups
1000	About 1000 scans and groups

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

Final Time Complexity

Time Complexity: O(n)

This means the query's work grows linearly with the number of orders processed.

Common Mistake

[X] Wrong: "Using multiple CTEs means the query runs multiple times and multiplies the work."

[OK] Correct: Each CTE runs once in order, and the total work depends mostly on the largest data scanned, not on the number of CTEs.

Interview Connect

Understanding how multiple CTEs affect query time helps you write clear and efficient queries, a useful skill in real projects and interviews.

Self-Check

What if we added a join inside one of the CTEs? How would that change the time complexity?