Subqueries in WHERE clause in MySQL - Time & Space Complexity

Time Complexity: Subqueries in WHERE clause

O(n)

Understanding Time Complexity

When using subqueries inside a WHERE clause, the database runs extra checks for each row. We want to understand how this affects the time it takes to get results.

How does the work grow as the data gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT employee_id, name
FROM employees
WHERE department_id IN (
  SELECT department_id
  FROM departments
  WHERE location = 'New York'
);
    

This query finds employees who work in departments located in New York by using a subquery inside the WHERE clause.

Identify Repeating Operations

• Primary operation: For each employee row, the database checks if their department_id matches one from the subquery result.
• How many times: The subquery runs once or is optimized to run fewer times depending on the database engine.

How Execution Grows With Input

As the number of employees grows, the database must check more rows against the subquery results.

Input Size (n)	Approx. Operations
10	About 10 checks of the subquery
100	About 100 checks of the subquery
1000	About 1000 checks of the subquery

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

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "The subquery runs only once, so it doesn't affect performance much."

[OK] Correct: Often the subquery runs for each row checked, so its cost multiplies with the number of rows, increasing total work.

Interview Connect

Understanding how subqueries affect query time helps you write efficient database queries and shows you can think about performance in real projects.

Self-Check

"What if we replaced the IN subquery with a JOIN? How would the time complexity change?"