Common Table Expressions (WITH) in MySQL - Time & Space Complexity

Time Complexity: Common Table Expressions (WITH)

O(n)

Understanding Time Complexity

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

We want to know how the number of operations changes when the input data gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

WITH recent_orders AS (
  SELECT * FROM orders WHERE order_date >= '2024-01-01'
)
SELECT customer_id, COUNT(*) AS order_count
FROM recent_orders
GROUP BY customer_id;
    

This code first selects recent orders using a CTE, then counts orders per customer.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

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

How Execution Grows With Input

As the number of orders grows, the database must scan more rows to find recent orders and then group them.

Input Size (n)	Approx. Operations
10	About 10 rows scanned and grouped
100	About 100 rows scanned and grouped
1000	About 1000 rows scanned and grouped

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

Final Time Complexity

Time Complexity: O(n)

This means the time to run the query grows roughly in a straight line as the number of orders increases.

Common Mistake

[X] Wrong: "Using a CTE makes the query run faster because it stores results."

[OK] Correct: The CTE is just a temporary result used during the query. It does not automatically speed up the scan or grouping steps.

Interview Connect

Understanding how CTEs affect query time helps you explain your choices clearly and shows you know how databases handle data behind the scenes.

Self-Check

"What if we added an index on order_date? How would the time complexity change?"