CTE as readable subquery replacement in SQL - Time & Space Complexity

Time Complexity: CTE as readable subquery replacement

O(n + m)

Understanding Time Complexity

When we use a CTE (Common Table Expression) instead of a subquery, we want to know how it affects the work the database does.

We ask: Does using a CTE change how long the query takes as data grows?

Scenario Under Consideration

Analyze the time complexity of the following SQL query using a CTE.

WITH RecentOrders AS (
  SELECT customer_id, order_date
  FROM orders
  WHERE order_date > CURRENT_DATE - INTERVAL '30 days'
)
SELECT c.customer_name, COUNT(r.order_date) AS recent_order_count
FROM customers c
LEFT JOIN RecentOrders r ON c.customer_id = r.customer_id
GROUP BY c.customer_name;
    

This query finds customers and counts their orders from the last 30 days using a CTE instead of a subquery.

Identify Repeating Operations

Look for repeated steps that take time as data grows.

• Primary operation: Scanning the orders table to find recent orders.
• How many times: Once for the CTE, then joining results to customers.

How Execution Grows With Input

As the number of orders and customers grows, the work grows too.

Input Size (n)	Approx. Operations
10 orders, 5 customers	About 15 operations (scanning + joining)
100 orders, 50 customers	About 150 operations
1000 orders, 500 customers	About 1500 operations

Pattern observation: The work grows roughly in proportion to the number of orders and customers combined.

Final Time Complexity

Time Complexity: O(n + m)

This means the time grows roughly with the size of the orders (n) plus the size of the customers (m).

Common Mistake

[X] Wrong: "Using a CTE always makes the query slower because it adds extra steps."

[OK] Correct: A CTE is just a way to organize the query. The database usually runs it like a subquery, so the time depends on the data size, not the syntax style.

Interview Connect

Understanding how query structure affects performance helps you write clear and efficient SQL, a skill valuable in many real-world projects.

Self-Check

What if we replaced the CTE with a nested subquery inside the main SELECT? How would the time complexity change?