Subqueries in FROM clause (derived tables) in MySQL - Time & Space Complexity

Time Complexity: Subqueries in FROM clause (derived tables)

O(n)

Understanding Time Complexity

When using subqueries inside the FROM clause, it's important to understand how the database processes them.

We want to know how the work grows as the data size increases.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT d.customer_id, d.total_orders
FROM (
  SELECT customer_id, COUNT(*) AS total_orders
  FROM orders
  GROUP BY customer_id
) AS d
WHERE d.total_orders > 5;
    

This query counts orders per customer in a subquery, then filters customers with more than 5 orders.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning all rows in the orders table to count orders per customer.
• How many times: Once over all orders, then grouping by customer to aggregate counts.

How Execution Grows With Input

As the number of orders grows, the database must look at each order once to count them.

Input Size (n)	Approx. Operations
10	About 10 row reads and counts
100	About 100 row reads and counts
1000	About 1000 row reads and counts

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

Final Time Complexity

Time Complexity: O(n)

This means the time to run the query grows linearly with the number of orders.

Common Mistake

[X] Wrong: "The subquery runs multiple times for each outer row, making it slower than it really is."

[OK] Correct: The subquery in the FROM clause runs once, creating a temporary result before filtering, so it does not repeat per outer row.

Interview Connect

Understanding how subqueries in the FROM clause work helps you explain query performance clearly and shows you know how databases process data step-by-step.

Self-Check

"What if we added an index on customer_id in the orders table? How would the time complexity change?"