Subquery with IN operator in SQL - Time & Space Complexity

Time Complexity: Subquery with IN operator

O(n * m)

Understanding Time Complexity

When using a subquery with the IN operator, we want to know how the time to run the query changes as the data grows.

We ask: How does the database handle checking many values inside the IN list?

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 employees who work in departments located in New York by using a subquery inside the IN operator.

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 per employee row, so it repeats as many times as there are employees.

How Execution Grows With Input

Explain the growth pattern intuitively.

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

Pattern observation: The number of checks grows directly with the number of employees.

Final Time Complexity

Time Complexity: O(n * m)

This means the time to run the query grows roughly in proportion to the number of employees times the number of departments in New York.

Common Mistake

[X] Wrong: "The subquery runs once and does not affect the total time much."

[OK] Correct: The subquery result is checked for each employee, so its size and how the database handles it impact the total time.

Interview Connect

Understanding how subqueries with IN work helps you explain query performance clearly and shows you can think about how databases handle data behind the scenes.

Self-Check

"What if we replaced the IN operator with an EXISTS clause? How would the time complexity change?"

Practice

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

easy

A. It checks if a value matches any value returned by the subquery.

B. It updates values in the main query based on the subquery.

C. It deletes rows that are returned by the subquery.

D. It creates a new table from the subquery results.

Solution

1. Step 1: Understand the role of IN operator

   The IN operator compares a value to a list of values and returns true if it matches any of them.

2. Step 2: Understand subquery usage

   The subquery returns a list of values that the main query uses to filter rows with the IN operator.

3. Final Answer:

   It checks if a value matches any value returned by the subquery. -> Option A

4. Quick Check:

   IN with subquery = match any value [OK]

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

Common Mistakes:

• Thinking IN updates or deletes rows
• Confusing IN with JOIN
• Assuming IN creates new tables

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

easy

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

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

C. SELECT * FROM employees WHERE department_id IN (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. Options A, B, and D have syntax errors.

3. Final Answer:

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

4. Quick Check:

   IN syntax = IN (subquery) [OK]

Hint: Use parentheses around subquery after IN [OK]

Common Mistakes:

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

3. Given the tables:
Employees(emp_id, name, dept_id)
Departments(dept_id, dept_name)
What will this query return?

SELECT name FROM Employees WHERE dept_id IN (SELECT dept_id FROM Departments WHERE dept_name = 'Sales');

medium

A. Names of employees who do not work in the Sales department.

B. Names of employees who work in the Sales department.

C. All employee names regardless of department.

D. An error because subquery returns multiple rows.

Solution

1. Step 1: Understand subquery filtering

   The subquery selects dept_id values where dept_name is 'Sales'.

2. Step 2: Main query filters employees

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

3. Final Answer:

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

4. Quick Check:

   IN filters employees by Sales dept_id [OK]

Hint: IN filters rows matching subquery values [OK]

Common Mistakes:

• Thinking it returns employees outside Sales
• Assuming subquery causes error with multiple rows
• Ignoring subquery filtering condition

4. Identify the error in this query:

SELECT emp_id FROM Employees WHERE dept_id IN SELECT dept_id FROM Departments;

medium

A. Subquery should be in the FROM clause.

B. Using IN instead of EXISTS.

C. dept_id should be compared with = not IN.

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, causing a 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
• Using = instead of IN for multiple values

5. You want to find all customers who have placed orders for products in the 'Electronics' category. Given tables:
Customers(customer_id, name)
Orders(order_id, customer_id, product_id)
Products(product_id, category)
Which query correctly uses a subquery with IN to get these customers?

hard

A. SELECT name FROM Customers WHERE customer_id IN (SELECT customer_id FROM Orders WHERE product_id IN (SELECT product_id FROM Products WHERE category = 'Electronics'));

B. SELECT name FROM Customers WHERE customer_id = (SELECT customer_id FROM Orders WHERE product_id IN (SELECT product_id FROM Products WHERE category = 'Electronics'));

C. SELECT name FROM Customers WHERE customer_id IN (SELECT product_id FROM Products WHERE category = 'Electronics');

D. SELECT name FROM Customers WHERE customer_id IN (SELECT order_id FROM Orders WHERE product_id IN (SELECT product_id FROM Products WHERE category = 'Electronics'));

Solution

1. Step 1: Understand the relationships

   Customers link to Orders by customer_id; Orders link to Products by product_id.

2. Step 2: Analyze the nested subqueries

   The innermost subquery selects product_ids in 'Electronics'. The middle subquery selects customer_ids from Orders with those product_ids. The outer query selects customer names with those customer_ids.

3. Final Answer:

   SELECT name FROM Customers WHERE customer_id IN (SELECT customer_id FROM Orders WHERE product_id IN (SELECT product_id FROM Products WHERE category = 'Electronics')); -> Option A

4. Quick Check:

   Nested IN filters customers by Electronics orders [OK]

Hint: Use nested IN for multi-level filtering [OK]

Common Mistakes:

• Using = instead of IN for multiple customer_ids
• Comparing customer_id with product_id or order_id
• Missing nested subquery for product filtering