Subquery in WHERE clause in SQL - Time & Space Complexity

Time Complexity: Subquery in WHERE clause

O(m * n)

Understanding Time Complexity

We want to understand how the time it takes to run a SQL query with a subquery in the WHERE clause changes as the data grows.

Specifically, we ask: How does the size of the main table and the subquery table affect the total work done?

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

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking each employee against the list of department IDs returned by the subquery.
• How many times: For each employee row, the database checks if their department_id is in the subquery result.

How Execution Grows With Input

As the number of employees grows, the database must check more rows. Also, the subquery result size depends on how many departments are in New York.

Input Size (m)	Approx. Operations
10 employees	Checks 10 employees against subquery results (few departments)
100 employees	Checks 100 employees against subquery results (more departments)
1000 employees	Checks 1000 employees against subquery results (even more departments)

Pattern observation: The work grows roughly in proportion to the number of employees times the size of the subquery result.

Final Time Complexity

Time Complexity: O(m * n)

This means the time grows roughly by multiplying the number of employees (m) by the number of departments in New York (n).

Common Mistake

[X] Wrong: "The subquery runs only once, so the query time depends only on the number of employees."

[OK] Correct: The subquery result size affects how many checks happen for each employee, so both sizes matter.

Interview Connect

Understanding how subqueries affect performance helps you write efficient queries and explain your reasoning clearly in interviews.

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

easy

A. Creates a new table from existing data

B. Filters rows based on the results of another query

C. Deletes rows from a table

D. Updates values in 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 results of another query.

2. Step 2: Compare with other SQL operations

   Creating tables, deleting, or updating rows are different SQL operations and not the purpose of subqueries in WHERE.

3. Final Answer:

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

4. Quick Check:

   Subquery in WHERE = filter rows [OK]

Hint: Subquery in WHERE filters rows using another query's results [OK]

Common Mistakes:

• Thinking subquery creates or modifies tables
• Confusing subquery with JOIN
• Assuming subquery always returns one value

2. Which of the following is the correct syntax to use a subquery in the WHERE clause to find employees in departments with ID 10 or 20?

easy

A. SELECT * FROM employees WHERE department_id IN SELECT department_id FROM departments WHERE department_id IN (10, 20);

B. SELECT * FROM employees WHERE department_id = (SELECT department_id FROM departments WHERE department_id IN (10, 20));

C. SELECT * FROM employees WHERE department_id IN (SELECT department_id FROM departments WHERE department_id = 10 OR 20);

D. SELECT * FROM employees WHERE department_id IN (SELECT department_id FROM departments WHERE department_id IN (10, 20));

Solution

1. Step 1: Identify correct subquery syntax with IN

   The subquery must be enclosed in parentheses and used with IN to match multiple values.

2. Step 2: Check each option's syntax

   SELECT * FROM employees WHERE department_id IN (SELECT department_id FROM departments WHERE department_id IN (10, 20)); correctly uses IN with a subquery in parentheses. SELECT * FROM employees WHERE department_id = (SELECT department_id FROM departments WHERE department_id IN (10, 20)); uses = which expects one value, causing error. SELECT * FROM employees WHERE department_id IN SELECT department_id FROM departments WHERE department_id IN (10, 20); misses parentheses around subquery. SELECT * FROM employees WHERE department_id IN (SELECT department_id FROM departments WHERE department_id = 10 OR 20); has incorrect WHERE clause syntax.

3. Final Answer:

   SELECT * FROM employees WHERE department_id IN (SELECT department_id FROM departments WHERE department_id IN (10, 20)); -> Option D

4. Quick Check:

   Subquery with IN needs parentheses [OK]

Hint: Use IN with parentheses for subqueries returning multiple values [OK]

Common Mistakes:

• Using = instead of IN for multiple values
• Omitting parentheses around subquery
• Incorrect WHERE clause conditions inside subquery

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

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

medium

A. Names of employees who work in the Sales department

B. Names of all employees

C. Names of departments named Sales

D. An error because subquery returns multiple rows

Solution

1. Step 1: Understand the subquery

   The subquery selects department_id from departments where name is 'Sales'. This returns IDs of Sales departments.

2. Step 2: Apply subquery results in main query

   The main query selects employee names where their department_id matches any of those returned by the subquery.

3. Final Answer:

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

4. Quick Check:

   Subquery filters employees by Sales department [OK]

Hint: Subquery filters department IDs, main query filters employees [OK]

Common Mistakes:

• Thinking subquery returns employee names
• Confusing department names with employee names
• Assuming subquery causes error with multiple rows

4. Identify the error in this query:

SELECT * FROM orders WHERE customer_id = (SELECT customer_id FROM customers WHERE city = 'New York');

medium

A. Incorrect table name 'orders'

B. Missing FROM clause in subquery

C. Subquery returns multiple rows causing an error with '=' operator

D. No error, query is correct

Solution

1. Step 1: Analyze subquery result

   The subquery selects customer_id from customers where city is 'New York'. This can return multiple customer IDs.

2. Step 2: Check operator compatibility

   The main query uses '=' which expects a single value, but subquery returns multiple rows, causing an error.

3. Final Answer:

   Subquery returns multiple rows causing an error with '=' operator -> Option C

4. Quick Check:

   Use IN for multiple subquery results [OK]

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

Common Mistakes:

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

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

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 NOT = (SELECT product_id FROM orders);

Solution

1. Step 1: Understand the goal

   We want products that have never been ordered, so their product_id should NOT appear in orders.

2. Step 2: Use NOT IN with subquery

   The subquery selects all product_ids from orders. Using NOT IN filters products not in that list.

3. Step 3: Check other options

   SELECT name FROM products WHERE product_id IN (SELECT product_id FROM orders); finds products that have been ordered (opposite). SELECT name FROM products WHERE product_id = (SELECT product_id FROM orders); uses = which expects one value, causing error. SELECT name FROM products WHERE product_id NOT = (SELECT product_id FROM orders); uses NOT = which is invalid syntax for multiple values.

4. Final Answer:

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

5. Quick Check:

   NOT IN filters products never ordered [OK]

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

Common Mistakes:

• Using = instead of IN for multiple values
• Confusing NOT IN with NOT =
• Selecting wrong table columns in subquery