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?

Practice

1. What is the main benefit of using a WITH clause (CTE) instead of a nested subquery in SQL?

easy

A. It always runs faster than nested subqueries.

B. It makes the query easier to read and maintain by naming parts of the query.

C. It removes the need for any JOIN operations.

D. It automatically indexes the tables used in the query.

Solution

1. Step 1: Understand the purpose of CTEs

   CTEs (Common Table Expressions) allow you to name a subquery, making the SQL easier to read and organize.

2. Step 2: Compare with nested subqueries

   Nested subqueries can be hard to read because they are embedded inside other queries without a clear name.

3. Final Answer:

   It makes the query easier to read and maintain by naming parts of the query. -> Option B

4. Quick Check:

   CTEs improve readability = A [OK]

Hint: CTEs name subqueries for clarity and maintenance [OK]

Common Mistakes:

• Thinking CTEs always improve performance
• Believing CTEs remove the need for JOINs
• Assuming CTEs create indexes automatically

2. Which of the following is the correct syntax to start a CTE in SQL?

easy

A. WITH cte_name AS (SELECT ...) SELECT * FROM cte_name;

B. DEFINE cte_name AS (SELECT ...) SELECT * FROM cte_name;

C. CREATE CTE cte_name AS SELECT ...;

D. SELECT * FROM WITH cte_name AS (SELECT ...)

Solution

1. Step 1: Recall the standard CTE syntax

   The correct syntax starts with WITH cte_name AS (subquery), followed by the main query.

2. Step 2: Check each option

   WITH cte_name AS (SELECT ...) SELECT * FROM cte_name; correctly shows the CTE definition and usage. Options A, B, and C use invalid keywords or order.

3. Final Answer:

   WITH cte_name AS (SELECT ...) SELECT * FROM cte_name; -> Option A

4. Quick Check:

   CTE syntax starts with WITH = D [OK]

Hint: CTE always starts with WITH keyword followed by AS [OK]

Common Mistakes:

• Placing WITH after SELECT
• Using CREATE or DEFINE keywords for CTE
• Missing AS keyword after CTE name

3. Given the tables orders(order_id, customer_id, amount) and customers(customer_id, name), what will this query return?

WITH high_orders AS (
  SELECT customer_id, SUM(amount) AS total
  FROM orders
  GROUP BY customer_id
  HAVING SUM(amount) > 100
)
SELECT c.name, h.total
FROM high_orders h
JOIN customers c ON h.customer_id = c.customer_id;

medium

A. Names and total order amounts for customers with orders over 100 in total.

B. All customers with their total order amounts, regardless of amount.

C. Only customers with a single order over 100.

D. An error because CTEs cannot use GROUP BY.

Solution

1. Step 1: Analyze the CTE definition

   The CTE high_orders groups orders by customer and filters those with total amount > 100.

2. Step 2: Understand the main query

   The main query joins high_orders with customers to get customer names and their total order amounts.

3. Final Answer:

   Names and total order amounts for customers with orders over 100 in total. -> Option A

4. Quick Check:

   CTE filters totals > 100, join adds names = C [OK]

Hint: CTE filters first, main query joins for details [OK]

Common Mistakes:

• Confusing HAVING with WHERE
• Thinking it returns all customers
• Believing CTEs cannot use GROUP BY

4. Identify the error in this SQL query using a CTE:

WITH recent_orders AS (
  SELECT order_id, order_date
  FROM orders
  WHERE order_date > '2023-01-01'
)
SELECT *
FROM recent_orders
WHERE order_date < '2023-01-01';

medium

A. CTEs cannot be used with WHERE clauses inside them.

B. The CTE name cannot be used in the main query.

C. The query is missing a semicolon after the CTE definition.

D. The CTE filters orders after 2023-01-01 but main query filters before, resulting in no rows.

Solution

1. Step 1: Check the CTE filter condition

   The CTE selects orders with order_date > '2023-01-01'.

2. Step 2: Check the main query filter

   The main query filters order_date < '2023-01-01', which contradicts the CTE filter, so no rows match.

3. Final Answer:

   The CTE filters orders after 2023-01-01 but main query filters before, resulting in no rows. -> Option D

4. Quick Check:

   Conflicting filters cause empty result = B [OK]

Hint: Check filter conditions inside and outside CTE for conflicts [OK]

Common Mistakes:

• Thinking WHERE is not allowed in CTE
• Expecting semicolon after WITH clause
• Believing CTE names are invalid in main query

5. You want to find customers who placed orders totaling more than 500, but only include those customers who have placed at least 3 orders. Which CTE-based query correctly achieves this?

hard

A. WITH order_summary AS (
SELECT customer_id, COUNT(order_id) AS order_count
FROM orders
GROUP BY customer_id
HAVING COUNT(order_id) >= 3
)
SELECT * FROM order_summary WHERE total_amount > 500;

B. WITH order_summary AS (
SELECT customer_id, SUM(amount) AS total_amount
FROM orders
GROUP BY customer_id
HAVING SUM(amount) > 500
)
SELECT * FROM order_summary WHERE order_count >= 3;

C. WITH order_summary AS (
SELECT customer_id, COUNT(order_id) AS order_count, SUM(amount) AS total_amount
FROM orders
GROUP BY customer_id
HAVING SUM(amount) > 500 AND COUNT(order_id) >= 3
)
SELECT * FROM order_summary;

D. WITH order_summary AS (
SELECT customer_id, SUM(amount) AS total_amount
FROM orders
GROUP BY customer_id
)
SELECT * FROM order_summary WHERE total_amount > 500 AND order_count >= 3;

Solution

1. Step 1: Understand the requirements

   We need customers with total order amount > 500 and at least 3 orders.

2. Step 2: Check each option's logic

   WITH order_summary AS ( SELECT customer_id, COUNT(order_id) AS order_count, SUM(amount) AS total_amount FROM orders GROUP BY customer_id HAVING SUM(amount) > 500 AND COUNT(order_id) >= 3 ) SELECT * FROM order_summary; calculates both count and sum in the CTE and filters with HAVING both conditions, which is correct. Options B, C, and D try to filter outside the CTE on columns not selected or missing.

3. Final Answer:

   WITH order_summary AS ( SELECT customer_id, COUNT(order_id) AS order_count, SUM(amount) AS total_amount FROM orders GROUP BY customer_id HAVING SUM(amount) > 500 AND COUNT(order_id) >= 3 ) SELECT * FROM order_summary; -> Option C

4. Quick Check:

   Filter both conditions inside CTE HAVING = A [OK]

Hint: Use HAVING to filter grouped results inside CTE [OK]

Common Mistakes:

• Filtering aggregated columns outside CTE
• Missing COUNT or SUM in CTE select
• Using WHERE instead of HAVING for aggregates