Why subqueries nest queries in MySQL - Performance Analysis

Time Complexity: Why subqueries nest queries

O(m + n)

Understanding Time Complexity

When we use subqueries in MySQL, one query runs inside another. This nesting can affect how long the database takes to get results.

We want to understand how the time to run the whole query changes as the data grows.

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 WHERE clause.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The database scans the departments table to find matching department IDs, then scans the employees table to find matching employees.
• How many times: The subquery runs once, and its result is used to filter the employees table, which is scanned once.

How Execution Grows With Input

Explain the growth pattern intuitively.

Input Size (n)	Approx. Operations
10 departments, 100 employees	Scan 10 departments + scan 100 employees
100 departments, 1,000 employees	Scan 100 departments + scan 1,000 employees
1,000 departments, 10,000 employees	Scan 1,000 departments + scan 10,000 employees

Pattern observation: The total work grows roughly with the sum of the sizes of both tables scanned.

Final Time Complexity

Time Complexity: O(m + n)

This means the time grows roughly in a straight line with the number of departments (m) plus the number of employees (n).

Common Mistake

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

[OK] Correct: Even though the subquery runs once, its result affects how many employees are checked, so both parts add up to the total time.

Interview Connect

Understanding how nested queries affect performance helps you write better database queries and explain your thinking clearly in interviews.

Self-Check

What if the subquery returned a very large list of department IDs? How would that change the time complexity?

Practice

1. Why do we use subqueries in MySQL?
SELECT * FROM employees WHERE department_id IN (SELECT id FROM departments WHERE location = 'NY');

easy

A. To nest one query inside another and use its results

B. To speed up the database server hardware

C. To create new tables automatically

D. To change the database schema

Solution

1. Step 1: Understand subquery usage

   The inner query SELECT id FROM departments WHERE location = 'NY' finds department IDs in New York.

2. Step 2: Use subquery results in outer query

   The outer query selects employees whose department_id matches those IDs from the subquery.

3. Final Answer:

   To nest one query inside another and use its results -> Option A

4. Quick Check:

   Subqueries = nested queries using results [OK]

Hint: Subqueries let you use one query's results inside another [OK]

Common Mistakes:

• Thinking subqueries change database structure
• Confusing subqueries with hardware upgrades
• Believing subqueries create tables automatically

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

easy

A. SELECT * FROM table1 WHERE id = SELECT id FROM table2 WHERE condition;

B. SELECT * FROM table1 WHERE id == (SELECT id FROM table2 WHERE condition);

C. SELECT * FROM table1 WHERE id IN SELECT id FROM table2 WHERE condition;

D. SELECT * FROM table1 WHERE id = (SELECT id FROM table2 WHERE condition);

Solution

1. Step 1: Check subquery syntax

   Subqueries must be enclosed in parentheses and used with operators like = or IN.

2. Step 2: Identify correct syntax

   SELECT * FROM table1 WHERE id = (SELECT id FROM table2 WHERE condition); uses parentheses correctly and the = operator, which is valid syntax.

3. Final Answer:

   SELECT * FROM table1 WHERE id = (SELECT id FROM table2 WHERE condition); -> Option D

4. Quick Check:

   Subquery syntax requires parentheses [OK]

Hint: Always put subqueries inside parentheses [OK]

Common Mistakes:

• Using double equals (==) instead of single equals (=)
• Omitting parentheses around subquery
• Using IN without parentheses

3. What will be the output of this query?

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

Given:
- departments table has ids 1,2,3 with locations NY, LA, LA respectively
- employees table has:
(name: Alice, department_id: 1),
(name: Bob, department_id: 2),
(name: Carol, department_id: 3),
(name: Dave, department_id: 4)

medium

A. Bob, Carol

B. Alice, Bob, Carol

C. Alice, Dave

D. Dave only

Solution

1. Step 1: Identify department IDs in LA

   From departments, IDs with location 'LA' are 2 and 3.

2. Step 2: Find employees in those departments

   Employees with department_id 2 and 3 are Bob and Carol.

3. Final Answer:

   Bob, Carol -> Option A

4. Quick Check:

   Subquery filters departments = Bob, Carol [OK]

Hint: Match outer query filter with subquery results [OK]

Common Mistakes:

• Including employees from other departments
• Ignoring subquery filtering
• Assuming all employees are returned

4. Identify the error in this query:

SELECT name FROM employees WHERE department_id = SELECT id FROM departments WHERE location = 'NY';

medium

A. Missing WHERE clause in outer query

B. Using = instead of IN for multiple results

C. Missing parentheses around the subquery

D. Wrong table name 'employees'

Solution

1. Step 1: Check subquery syntax

   The subquery must be enclosed in parentheses to be valid.

2. Step 2: Identify missing parentheses

   The query lacks parentheses around SELECT id FROM departments WHERE location = 'NY'.

3. Final Answer:

   Missing parentheses around the subquery -> Option C

4. Quick Check:

   Subqueries need parentheses [OK]

Hint: Always wrap subqueries in parentheses [OK]

Common Mistakes:

• Forgetting parentheses causes syntax error
• Confusing = and IN without checking subquery results
• Assuming table names are incorrect without checking

5. You want to find all employees who earn more than the average salary in their department. Which query correctly uses a subquery to achieve this?

hard

A. SELECT name, salary FROM employees WHERE salary > AVG(salary);

B. SELECT name, salary FROM employees e WHERE salary > (SELECT AVG(salary) FROM employees WHERE department_id = e.department_id);

C. SELECT name, salary FROM employees WHERE salary > (SELECT salary FROM employees);

D. SELECT name, salary FROM employees WHERE salary > ALL (SELECT AVG(salary) FROM employees GROUP BY department_id);

Solution

1. Step 1: Understand the problem

   We want employees earning more than their department's average salary.

2. Step 2: Analyze subquery usage

   SELECT name, salary FROM employees e WHERE salary > (SELECT AVG(salary) FROM employees WHERE department_id = e.department_id); uses a correlated subquery that calculates average salary per employee's department.

3. Step 3: Check other options

   SELECT name, salary FROM employees WHERE salary > AVG(salary); lacks grouping, C compares salary to all salaries, D compares to all averages without correlation.

4. Final Answer:

   SELECT name, salary FROM employees e WHERE salary > (SELECT AVG(salary) FROM employees WHERE department_id = e.department_id); -> Option B

5. Quick Check:

   Correlated subquery per department = SELECT name, salary FROM employees e WHERE salary > (SELECT AVG(salary) FROM employees WHERE department_id = e.department_id); [OK]

Hint: Use correlated subqueries to compare per group [OK]

Common Mistakes:

• Using aggregate functions without grouping
• Not correlating subquery with outer query
• Comparing salary to unrelated values