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

Practice

1. What does a subquery in the WHERE clause do in MySQL?

easy

A. Updates data in multiple tables at once

B. Filters rows based on the result of another query

C. Creates a new table in the database

D. Deletes rows from a table

Solution

1. Step 1: Understand the role of subqueries in WHERE clause

   A subquery inside a WHERE clause is used to filter rows by comparing values to the result of another query.

2. Step 2: Differentiate from other SQL operations

   Creating tables, updating, or deleting data are not done by subqueries in WHERE; they are separate SQL commands.

3. Final Answer:

   Filters rows based on the result of another query -> Option B

4. Quick Check:

   Subquery in WHERE = filter rows [OK]

Hint: Subqueries in WHERE filter rows using another query's result [OK]

Common Mistakes:

• Thinking subqueries create or modify tables
• Confusing subqueries with JOINs
• Assuming subqueries always return multiple rows

2. Which of the following is the correct syntax for using a subquery in the WHERE clause to find employees with salaries greater than the average salary?

easy

A. SELECT * FROM employees WHERE salary = (SELECT salary FROM employees);

B. SELECT * FROM employees WHERE salary IN SELECT AVG(salary) FROM employees;

C. SELECT * FROM employees WHERE salary > (SELECT AVG(salary) FROM employees);

D. SELECT * FROM employees WHERE salary > ALL SELECT AVG(salary) FROM employees;

Solution

1. Step 1: Check subquery syntax in WHERE clause

   The subquery must be enclosed in parentheses and return a single value for comparison with salary.

2. Step 2: Validate each option's syntax

   Only SELECT * FROM employees WHERE salary > (SELECT AVG(salary) FROM employees); correctly uses parentheses around a single-value subquery. Other options miss parentheses, misuse IN with a single value, use = with a multi-row subquery, or misuse ALL.

3. Final Answer:

   SELECT * FROM employees WHERE salary > (SELECT AVG(salary) FROM employees); -> Option C

4. Quick Check:

   Correct subquery syntax uses parentheses [OK]

Hint: Always enclose subqueries in parentheses in WHERE clause [OK]

Common Mistakes:

• Omitting parentheses around subquery
• Using IN with single-value subquery incorrectly
• Comparing to multiple rows without IN or EXISTS

3. Given the tables orders(order_id, customer_id, amount) and customers(customer_id, city), what will this query return?

SELECT order_id FROM orders WHERE customer_id IN (SELECT customer_id FROM customers WHERE city = 'Paris');

medium

A. All order IDs from customers who live in Paris

B. All order IDs from customers who do not live in Paris

C. All customer IDs from Paris

D. Syntax error due to missing JOIN

Solution

1. Step 1: Understand the subquery result

   The subquery selects customer IDs where city is 'Paris'. This returns a list of customer IDs living in Paris.

2. Step 2: Apply the subquery result in the main query

   The main query selects order IDs where the customer_id is in that list, so orders from Paris customers are returned.

3. Final Answer:

   All order IDs from customers who live in Paris -> Option A

4. Quick Check:

   IN with subquery filters matching customer IDs [OK]

Hint: IN subquery filters rows matching any returned value [OK]

Common Mistakes:

• Confusing orders with customers
• Assuming JOIN is required for this filter
• Thinking it returns customer IDs instead of order IDs

4. Identify the error in this query:

SELECT name FROM employees WHERE department_id = (SELECT department_id FROM departments WHERE location = 'NY' AND active = 1);

Assuming multiple departments can be active in NY.

medium

A. No error, query is correct

B. Missing GROUP BY clause in subquery

C. Incorrect table name 'departments'

D. Subquery returns multiple rows but '=' expects one value

Solution

1. Step 1: Analyze subquery result cardinality

   The subquery may return multiple department_id values because multiple departments can be active in NY.

2. Step 2: Check operator compatibility

   The '=' operator expects a single value, but the subquery returns multiple rows, causing an error.

3. Final Answer:

   Subquery returns multiple rows but '=' expects one value -> Option D

4. Quick Check:

   Use IN for multiple values, '=' for single value [OK]

Hint: Use IN if subquery returns multiple rows, not '=' [OK]

Common Mistakes:

• Using '=' with subquery returning multiple rows
• Assuming subquery always returns one row
• Ignoring error messages about subquery results

5. You want to find all products that have never been ordered. Given tables products(product_id, name) and orders(order_id, product_id), which query correctly uses a subquery in the WHERE clause to achieve this?

hard

A. SELECT name FROM products WHERE product_id NOT IN (SELECT product_id FROM orders);

B. SELECT name FROM products WHERE product_id IN (SELECT product_id FROM orders);

C. SELECT name FROM products WHERE product_id = (SELECT product_id FROM orders);

D. SELECT name FROM products WHERE product_id > (SELECT product_id FROM orders);

Solution

1. Step 1: Understand the goal

   We want products that have no matching product_id in orders, meaning they were never ordered.

2. Step 2: Use NOT IN with subquery

   Using NOT IN with a subquery selecting product_ids from orders filters products not present in orders.

3. Final Answer:

   SELECT name FROM products WHERE product_id NOT IN (SELECT product_id FROM orders); -> Option A

4. Quick Check:

   NOT IN filters out matching values [OK]

Hint: Use NOT IN with subquery to find missing matches [OK]

Common Mistakes:

• Using IN instead of NOT IN for exclusion
• Using '=' with subquery returning multiple rows
• Using comparison operators incorrectly with subqueries