Subqueries in WHERE with IN in PostgreSQL - Time & Space Complexity

Time Complexity: Subqueries in WHERE with IN

O(n)

Understanding Time Complexity

When using a subquery inside a WHERE clause with IN, the database checks if values match a list from another query.

We want to know how the time to run this query changes as the size of the data grows.

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.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: For each employee, check 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 result.

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

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 and does not affect the total time much."

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

Interview Connect

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

Self-Check

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

Practice

1. What does the IN keyword do in a SQL query when used with a subquery in the WHERE clause?

easy

A. It filters rows where a column's value matches any value returned by the subquery.

B. It joins two tables together based on matching columns.

C. It updates rows in the table with values from the subquery.

D. It deletes rows that do not exist in the subquery.

Solution

1. Step 1: Understand the role of IN with subqueries

   The IN keyword checks if a value exists in a list of values returned by the subquery.

2. Step 2: Identify the filtering effect

   Rows are kept only if their column value matches any value from the subquery's result.

3. Final Answer:

   It filters rows where a column's value matches any value returned by the subquery. -> Option A

4. Quick Check:

   IN filters rows by subquery values [OK]

Hint: Think of IN as 'is in this list' from the subquery [OK]

Common Mistakes:

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

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

easy

A. SELECT * FROM employees WHERE department_id IN (SELECT * 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: Check the correct use of parentheses

   The subquery must be enclosed in parentheses after IN.

2. Step 2: Verify the subquery returns a single column

   The subquery should return one column of values to compare against.

3. Final Answer:

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

4. Quick Check:

   Subquery in parentheses with single column [OK]

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

Common Mistakes:

• Using = IN instead of just IN
• Omitting parentheses around subquery
• Selecting multiple columns in subquery

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 do not work in Sales.

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

Solution

1. Step 1: Understand the subquery filtering departments

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

2. Step 2: Filter employees by matching department IDs

   The main query returns employee names whose department_id matches those IDs.

3. Final Answer:

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

4. Quick Check:

   IN filters employees by Sales department IDs [OK]

Hint: Subquery filters departments, main query filters employees [OK]

Common Mistakes:

• Thinking it returns all employees
• Confusing NOT IN with IN
• Assuming subquery causes error with multiple rows

4. Identify the error in this query:

SELECT * FROM employees WHERE department_id IN SELECT id FROM departments WHERE name = 'HR';

medium

A. Missing parentheses around the subquery after IN.

B. Using IN instead of EXISTS.

C. Subquery returns multiple columns.

D. department_id cannot be compared with id.

Solution

1. Step 1: Check syntax for subquery with IN

   The subquery must be enclosed in parentheses after the IN keyword.

2. Step 2: Identify missing parentheses causing syntax error

   The query lacks parentheses around the subquery, causing invalid syntax.

3. Final Answer:

   Missing parentheses around the subquery after IN. -> Option A

4. Quick Check:

   Subquery must be in parentheses after IN [OK]

Hint: Always wrap subqueries in parentheses after IN [OK]

Common Mistakes:

• Omitting parentheses around subquery
• Confusing IN with EXISTS syntax
• Assuming subquery returns multiple columns

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

hard

A. SELECT name FROM customers WHERE id IN (SELECT id FROM products WHERE category = 'Electronics');

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

C. SELECT name FROM customers WHERE id IN (SELECT customer_id FROM orders WHERE product_id IN (SELECT id FROM products WHERE category = 'Electronics'));

D. SELECT name FROM customers WHERE id IN (SELECT product_id FROM orders WHERE customer_id IN (SELECT id FROM products WHERE category = 'Electronics'));

Solution

1. Step 1: Identify the correct subquery for products in 'Electronics'

   The innermost subquery selects product IDs where category is 'Electronics'.

2. Step 2: Use these product IDs to find matching orders

   The middle subquery selects customer IDs from orders with those product IDs.

3. Step 3: Select customer names whose IDs match those customer IDs

   The main query selects customer names where their ID is in the list from the orders subquery.

4. Final Answer:

   SELECT name FROM customers WHERE id IN (SELECT customer_id FROM orders WHERE product_id IN (SELECT id FROM products WHERE category = 'Electronics')); -> Option C

5. Quick Check:

   Nested IN subqueries filter customers by product category [OK]

Hint: Use nested IN subqueries to filter step-by-step [OK]

Common Mistakes:

• Using = IN instead of IN
• Mixing up customer_id and product_id columns
• Selecting wrong columns in subqueries