Subqueries with IN operator in MySQL - Time & Space Complexity

Time Complexity: Subqueries with IN operator

O(n)

Understanding Time Complexity

When using subqueries with the IN operator, it is important to understand how the query's running time changes as the data grows.

We want to know how the number of operations increases when the tables get bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT employee_name
FROM employees
WHERE department_id IN (
  SELECT department_id
  FROM departments
  WHERE location = 'New York'
);
    

This query finds all employees who work in departments located in New York.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: For each employee, the database checks if their department_id is in the list returned by the subquery.
• How many times: This check happens once for every employee row.

How Execution Grows With Input

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

Input Size (n employees)	Approx. Operations
10	About 10 checks against the subquery result
100	About 100 checks against the subquery result
1000	About 1000 checks against the subquery result

Pattern observation: The number of operations 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.

Common Mistake

[X] Wrong: "The subquery runs once for each employee, so the time grows much faster than the number of employees."

[OK] Correct: The database usually runs the subquery once and reuses its results, so the main cost depends mostly on checking each employee against that list.

Interview Connect

Understanding how subqueries with IN work helps you explain query performance clearly and shows you can think about how data size affects speed.

Self-Check

"What if we changed the subquery to use EXISTS instead of IN? How would the time complexity change?"

Practice

1. What does the IN operator do when used with a subquery in MySQL?

easy

A. Checks if a value matches any value returned by the subquery

B. Joins two tables based on a common column

C. Updates values in the main table using subquery results

D. Deletes rows that match the subquery results

Solution

1. Step 1: Understand the IN operator

   The IN operator checks if a value exists within a list of values.

2. Step 2: Role of subquery with IN

   The subquery returns a list of values, and IN checks if the main query's value matches any of these.

3. Final Answer:

   Checks if a value matches any value returned by the subquery -> Option A

4. Quick Check:

   IN with subquery = value match list [OK]

Hint: IN checks if value is in subquery result list [OK]

Common Mistakes:

• Confusing IN with JOIN
• Thinking IN updates or deletes rows
• Assuming IN returns a single value

2. Which of the following is the correct syntax to use a subquery with the IN operator in MySQL?

easy

A. SELECT * FROM employees WHERE department_id = IN (SELECT id FROM departments);

B. SELECT * FROM employees WHERE department_id IN (SELECT id FROM departments);

C. SELECT * FROM employees WHERE IN department_id (SELECT id FROM departments);

D. SELECT * FROM employees WHERE department_id IN SELECT id FROM departments;

Solution

1. Step 1: Review correct IN syntax

   The IN operator must be followed by parentheses enclosing the subquery.

2. Step 2: Check each option

   SELECT * FROM employees WHERE department_id IN (SELECT id FROM departments); correctly uses IN with parentheses and a subquery. Others have syntax errors.

3. Final Answer:

   SELECT * FROM employees WHERE department_id IN (SELECT id FROM departments); -> Option B

4. Quick Check:

   IN + (subquery) = correct syntax [OK]

Hint: Use IN followed by parentheses around subquery [OK]

Common Mistakes:

• Adding = before IN
• Missing parentheses around subquery
• Placing IN before column name

3. Given the tables:
employees(id, name, department_id)
departments(id, name)
What will this query return?

SELECT name FROM employees WHERE department_id IN (SELECT id FROM departments WHERE name = 'Sales');

medium

A. An error because subquery returns multiple rows

B. Names of all employees regardless of department

C. Names of employees who work in the Sales department

D. Names of employees who do not work in Sales

Solution

1. Step 1: Analyze subquery

   The subquery selects department IDs where the department name is 'Sales'.

2. Step 2: Main query filters employees

   The main query selects employee names whose department_id matches any ID from the subquery.

3. Final Answer:

   Names of employees who work in the Sales department -> Option C

4. Quick Check:

   IN filters employees by Sales department IDs [OK]

Hint: Subquery filters IDs; IN matches employees with those IDs [OK]

Common Mistakes:

• Thinking IN causes error with multiple rows
• Ignoring subquery filter condition
• Assuming it returns all employees

4. Identify the error in this query:

SELECT * FROM orders WHERE customer_id IN SELECT id FROM customers WHERE city = 'New York';

medium

A. Subquery returns no rows

B. Incorrect table name 'orders'

C. Using IN instead of EXISTS

D. Missing parentheses around the subquery after IN

Solution

1. Step 1: Check IN operator syntax

   The IN operator requires the subquery to be enclosed in parentheses.

2. Step 2: Identify missing parentheses

   The query lacks parentheses around the subquery after IN, causing syntax error.

3. Final Answer:

   Missing parentheses around the subquery after IN -> Option D

4. Quick Check:

   IN needs (subquery) [OK]

Hint: Always put subquery inside parentheses after IN [OK]

Common Mistakes:

• Omitting parentheses around subquery
• Confusing IN with EXISTS
• Assuming table names cause error

5. You want to find all products that have been ordered by customers from the city 'Chicago'.
Given tables:
products(id, name)
orders(id, product_id, customer_id)
customers(id, city)
Which query correctly uses a subquery with IN to get the product names?

hard

A. SELECT name FROM products WHERE id IN (SELECT product_id FROM orders WHERE customer_id IN (SELECT id FROM customers WHERE city = 'Chicago'));

B. SELECT name FROM products WHERE id = IN (SELECT product_id FROM orders WHERE customer_id = IN (SELECT id FROM customers WHERE city = 'Chicago'));

C. SELECT name FROM products WHERE id IN SELECT product_id FROM orders WHERE customer_id IN SELECT id FROM customers WHERE city = 'Chicago';

D. SELECT name FROM products WHERE id IN (SELECT id FROM customers WHERE city = 'Chicago');

Solution

1. Step 1: Understand the relationships

   Products link to orders by product_id; orders link to customers by customer_id.

2. Step 2: Build nested subqueries

   Inner subquery gets customer IDs from Chicago; middle subquery gets product_ids from orders by those customers; outer query selects product names with those IDs.

3. Final Answer:

   SELECT name FROM products WHERE id IN (SELECT product_id FROM orders WHERE customer_id IN (SELECT id FROM customers WHERE city = 'Chicago')); -> Option A

4. Quick Check:

   Nested IN subqueries correctly filter products [OK]

Hint: Use nested IN subqueries to filter related tables stepwise [OK]

Common Mistakes:

• Adding = before IN
• Missing parentheses around subqueries
• Using wrong columns in subqueries