Nested subqueries in SQL - Time & Space Complexity

Time Complexity: Nested subqueries

O(n * m)

Understanding Time Complexity

When using nested subqueries, it is important to understand how the work grows as the data gets bigger.

We want to know how many times the database repeats tasks inside these nested queries.

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_id = 100
);

This query finds employees who work in departments located at a specific location.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The inner subquery scans the departments table once.
• How many times: The outer query scans the employees table once, then checks each employee's department against the subquery result.

How Execution Grows With Input

As the number of employees and departments grows, the database does more work to match employees to departments.

Input Size (n)	Approx. Operations
10 employees, 5 departments	About 10 checks against 5 departments
100 employees, 50 departments	About 100 checks against 50 departments
1000 employees, 500 departments	About 1000 checks against 500 departments

Pattern observation: The work grows roughly by multiplying the number of employees by the number of departments.

Final Time Complexity

Time Complexity: O(n * m)

This means the work grows by multiplying the size of the outer table by the size of the inner table.

Common Mistake

[X] Wrong: "The inner subquery runs only once, so the time is just O(n)."

[OK] Correct: The inner subquery result is used for each row in the outer query, so the total work depends on both tables.

Interview Connect

Understanding how nested subqueries affect performance helps you write better queries and explain your choices clearly.

Self-Check

"What if we replaced the IN subquery with a JOIN? How would the time complexity change?"

Practice

1. What does a nested subquery in SQL do?

easy

A. Runs a query inside another query to filter or compare data

B. Creates a new table from existing data

C. Deletes data from multiple tables at once

D. Updates all rows in a table without conditions

Solution

1. Step 1: Understand the concept of nested subqueries

   A nested subquery is a query inside another query that runs first to provide data for the outer query.

2. Step 2: Identify the correct description

   Runs a query inside another query to filter or compare data correctly describes this behavior as running a query inside another to filter or compare data.

3. Final Answer:

   Runs a query inside another query to filter or compare data -> Option A

4. Quick Check:

   Nested subquery = query inside query [OK]

Hint: Nested means one query inside another [OK]

Common Mistakes:

• Confusing nested subquery with table creation
• Thinking nested subqueries delete data
• Assuming nested subqueries update all rows blindly

2. Which of the following is the correct syntax for a nested subquery in SQL?

easy

A. SELECT * FROM table WHERE id IN SELECT id FROM table2 WHERE value = 10;

B. SELECT * FROM table WHERE id == (SELECT id FROM table2 WHERE value = 10);

C. SELECT * FROM table WHERE id = SELECT id FROM table2 WHERE value = 10;

D. SELECT * FROM table WHERE id = (SELECT id FROM table2 WHERE value = 10);

Solution

1. Step 1: Review correct nested subquery syntax

   The inner query must be enclosed in parentheses and used with operators like = or IN.

2. Step 2: Check each option

   SELECT * FROM table WHERE id = (SELECT id FROM table2 WHERE value = 10); uses parentheses correctly and equals operator, making it valid SQL syntax.

3. Final Answer:

   SELECT * FROM table WHERE id = (SELECT id FROM table2 WHERE value = 10); -> Option D

4. Quick Check:

   Nested subquery syntax uses parentheses [OK]

Hint: Always use parentheses around subqueries [OK]

Common Mistakes:

• Missing parentheses around subquery
• Using double equals (==) instead of single =
• Omitting parentheses causing syntax errors

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

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

medium

A. Names of employees who work in the Sales department

B. All employee names regardless of department

C. Department names where employees work

D. Employee names who do not work in Sales

Solution

1. Step 1: Understand the inner query

   The inner query finds the dept_id for the 'Sales' department from Departments table.

2. Step 2: Apply the outer query condition

   The outer query selects employee names whose dept_id matches the Sales dept_id found by the inner query.

3. Final Answer:

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

4. Quick Check:

   Inner query finds Sales dept_id, outer filters employees [OK]

Hint: Inner query finds filter value, outer applies it [OK]

Common Mistakes:

• Thinking it returns all employees
• Confusing employee names with department names
• Assuming it returns employees not in Sales

4. Identify the error in this SQL query:

SELECT name FROM Employees WHERE dept_id = SELECT dept_id FROM Departments WHERE dept_name = 'HR';

medium

A. Using = instead of IN for subquery

B. Missing parentheses around the subquery

C. Wrong table name used in subquery

D. Subquery returns multiple columns

Solution

1. Step 1: Check subquery syntax

   The subquery must be enclosed in parentheses to be valid inside WHERE clause.

2. Step 2: Identify the missing parentheses

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

3. Final Answer:

   Missing parentheses around the subquery -> Option B

4. Quick Check:

   Subqueries need parentheses [OK]

Hint: Always wrap subqueries in parentheses [OK]

Common Mistakes:

• Forgetting parentheses around subquery
• Using wrong operator without parentheses
• Assuming subquery syntax is optional

5. You want to find all customers who placed orders with amounts greater than the average order amount. Which query correctly uses a nested subquery to achieve this?

hard

A. SELECT customer_id FROM Orders WHERE amount < (SELECT AVG(amount) FROM Orders);

B. SELECT customer_id FROM Orders WHERE amount = (SELECT AVG(amount) FROM Orders);

C. SELECT customer_id FROM Orders WHERE amount > (SELECT AVG(amount) FROM Orders);

D. SELECT customer_id FROM Orders WHERE amount IN (SELECT AVG(amount) FROM Orders);

Solution

1. Step 1: Understand the goal

   We want customers with orders greater than the average order amount.

2. Step 2: Analyze each option's condition

   SELECT customer_id FROM Orders WHERE amount > (SELECT AVG(amount) FROM Orders); uses > with a subquery calculating average amount, correctly filtering orders above average.

3. Final Answer:

   SELECT customer_id FROM Orders WHERE amount > (SELECT AVG(amount) FROM Orders); -> Option C

4. Quick Check:

   Use > with AVG subquery to find above-average orders [OK]

Hint: Compare with (SELECT AVG(...)) using > for above average [OK]

Common Mistakes:

• Using = instead of > to find above average
• Using < which finds below average
• Using IN with a single value subquery incorrectly