Subqueries with EXISTS in MySQL - Time & Space Complexity

Time Complexity: Subqueries with EXISTS

O(n * m)

Understanding Time Complexity

When using subqueries with EXISTS, we want to know how the time to run the query changes as the data grows.

We ask: How many checks does the database do as the tables get bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT customer_id, customer_name
FROM customers c
WHERE EXISTS (
  SELECT 1
  FROM orders o
  WHERE o.customer_id = c.customer_id
);
    

This query finds all customers who have at least one order by checking if an order exists for each customer.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: For each customer, the database checks the orders table to find a matching order.
• How many times: This check happens once per customer, so as many times as there are customers.

How Execution Grows With Input

As the number of customers grows, the database does more checks in the orders table for each customer.

Input Size (n customers)	Approx. Operations
10	Checks orders for 10 customers
100	Checks orders for 100 customers
1000	Checks orders for 1000 customers

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

Final Time Complexity

Time Complexity: O(n * m)

This means the time to run the query grows linearly with the number of customers and the number of orders per customer.

Common Mistake

[X] Wrong: "The EXISTS subquery runs once and then applies to all customers."

[OK] Correct: The subquery runs separately for each customer to check if an order exists, so it repeats many times.

Interview Connect

Understanding how EXISTS works helps you explain query performance clearly and shows you can think about how databases handle data step by step.

Self-Check

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