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?"

Practice

1. What is the main purpose of referencing one CTE inside another CTE in SQL?

easy

A. To create permanent tables in the database

B. To speed up the database server automatically

C. To avoid using SELECT statements

D. To break down complex queries into smaller, easier steps

Solution

1. Step 1: Understand what CTEs do

   CTEs (Common Table Expressions) let you write parts of a query separately for clarity.

2. Step 2: See why referencing one CTE inside another helps

   Referencing one CTE inside another breaks complex logic into smaller, readable steps without repeating code.

3. Final Answer:

   To break down complex queries into smaller, easier steps -> Option D

4. Quick Check:

   CTEs help simplify queries = C [OK]

Hint: Think of CTEs as building blocks for queries [OK]

Common Mistakes:

• Confusing CTEs with permanent tables
• Believing CTEs speed up queries automatically
• Thinking CTEs replace SELECT statements

2. Which of the following is the correct syntax to reference one CTE inside another in SQL?

easy

A. WITH cte1 AS (SELECT * FROM table1), cte2 AS (SELECT * FROM cte1 WHERE id > 10) SELECT * FROM cte2;

B. WITH cte1 AS (SELECT * FROM table1) SELECT * FROM cte1; WITH cte2 AS (SELECT * FROM cte1 WHERE id > 10);

C. CREATE CTE cte1 AS SELECT * FROM table1; CREATE CTE cte2 AS SELECT * FROM cte1 WHERE id > 10;

D. SELECT * FROM cte1; WITH cte2 AS (SELECT * FROM cte1 WHERE id > 10);

Solution

1. Step 1: Review correct CTE syntax

   Multiple CTEs are defined together after WITH, separated by commas, and can reference each other.

2. Step 2: Check each option

   WITH cte1 AS (SELECT * FROM table1), cte2 AS (SELECT * FROM cte1 WHERE id > 10) SELECT * FROM cte2; correctly defines cte1, then cte2 referencing cte1, then selects from cte2. Others misuse WITH or CREATE keywords.

3. Final Answer:

   WITH cte1 AS (SELECT * FROM table1), cte2 AS (SELECT * FROM cte1 WHERE id > 10) SELECT * FROM cte2; -> Option A

4. Quick Check:

   Multiple CTEs separated by commas = A [OK]

Hint: Use one WITH clause for all CTEs, separated by commas [OK]

Common Mistakes:

• Using multiple WITH clauses separately
• Trying to CREATE CTEs like tables
• Placing SELECT before WITH

3. Given the following SQL query, what will be the output?

WITH first_cte AS (
  SELECT 1 AS num UNION ALL SELECT 2 UNION ALL SELECT 3
), second_cte AS (
  SELECT num * 10 AS val FROM first_cte WHERE num > 1
)
SELECT * FROM second_cte ORDER BY val;

medium

A. [20, 30]

B. Syntax error

C. [1, 2, 3]

D. [10, 20, 30]

Solution

1. Step 1: Analyze first_cte output

   first_cte returns rows with num = 1, 2, 3.

2. Step 2: Analyze second_cte filtering and calculation

   second_cte selects num * 10 as val where num > 1, so num=2 and 3, val=20 and 30.

3. Final Answer:

   [20, 30] -> Option A

4. Quick Check:

   Filter num > 1, multiply by 10 = [20, 30] [OK]

Hint: Trace each CTE step by step to find final output [OK]

Common Mistakes:

• Including num=1 in second_cte output
• Confusing num and val columns
• Assuming syntax error due to multiple CTEs

4. Identify the error in this SQL query using CTEs:

WITH cte1 AS (
  SELECT id, name FROM users
),
cte2 AS (
  SELECT id, name FROM cte3 WHERE id > 5
)
SELECT * FROM cte2;

medium

A. SELECT statement missing after CTEs

B. Missing comma between CTE definitions

C. cte2 references cte3 which is not defined

D. CTEs cannot reference other CTEs

Solution

1. Step 1: Check CTE definitions

   cte1 is defined, but cte2 references cte3 which is not defined anywhere.

2. Step 2: Confirm syntax correctness

   Comma between cte1 and cte2 is present, and SELECT after CTEs is correct, so no syntax error there.

3. Final Answer:

   cte2 references cte3 which is not defined -> Option C

4. Quick Check:

   Undefined CTE reference = A [OK]

Hint: Check all referenced CTE names are defined above [OK]

Common Mistakes:

• Assuming missing comma error
• Thinking CTEs can't reference others
• Overlooking undefined CTE names

5. You have two CTEs: sales_cte with columns (product_id, total_sales) and products_cte with columns (product_id, product_name). How do you write a query using CTE referencing another CTE to get product names with sales over 1000?

hard

A. WITH sales_cte AS (SELECT product_id, SUM(amount) AS total_sales FROM sales GROUP BY product_id) SELECT product_name FROM products WHERE product_id IN (SELECT product_id FROM sales_cte WHERE total_sales > 1000);

B. WITH sales_cte AS (SELECT product_id, SUM(amount) AS total_sales FROM sales GROUP BY product_id), products_cte AS (SELECT product_id, product_name FROM products), final_cte AS (SELECT p.product_name FROM products_cte p JOIN sales_cte s ON p.product_id = s.product_id WHERE s.total_sales > 1000) SELECT * FROM final_cte;

C. WITH products_cte AS (SELECT product_id, product_name FROM products), sales_cte AS (SELECT product_id, SUM(amount) AS total_sales FROM sales GROUP BY product_id) SELECT product_name FROM products_cte WHERE total_sales > 1000;

D. WITH final_cte AS (SELECT product_name FROM products JOIN sales ON products.product_id = sales.product_id WHERE sales.amount > 1000) SELECT * FROM final_cte;

Solution

1. Step 1: Define sales_cte and products_cte correctly

   sales_cte sums sales per product_id; products_cte selects product info.

2. Step 2: Create final_cte referencing both CTEs

   Join products_cte and sales_cte on product_id, filter total_sales > 1000, select product_name.

3. Step 3: Select from final_cte

   Final SELECT returns product names with sales over 1000.

4. Final Answer:

   WITH sales_cte AS (SELECT product_id, SUM(amount) AS total_sales FROM sales GROUP BY product_id), products_cte AS (SELECT product_id, product_name FROM products), final_cte AS (SELECT p.product_name FROM products_cte p JOIN sales_cte s ON p.product_id = s.product_id WHERE s.total_sales > 1000) SELECT * FROM final_cte; -> Option B

5. Quick Check:

   Layered CTEs with join and filter = B [OK]

Hint: Build CTEs stepwise, join in last CTE for filtering [OK]

Common Mistakes:

• Referencing columns not in CTEs
• Filtering before joining CTEs
• Not joining CTEs properly