Correlated subqueries in MySQL - Time & Space Complexity

Time Complexity: Correlated subqueries

O(n * m)

Understanding Time Complexity

When using correlated subqueries, the database runs a small query for each row of the main query.

We want to understand how the total work grows as the number of rows increases.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT e1.employee_id, e1.salary
FROM employees e1
WHERE e1.salary > (
  SELECT AVG(e2.salary)
  FROM employees e2
  WHERE e2.department_id = e1.department_id
);
    

This query finds employees whose salary is above the average salary in their department.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: For each employee row, the subquery calculates the average salary of that employee's department.
• How many times: The subquery runs once for every employee in the main query.

How Execution Grows With Input

As the number of employees grows, the subquery runs more times, each time scanning employees in a department.

Input Size (n)	Approx. Operations
10	About 10 times scanning small groups
100	About 100 times scanning department groups
1000	About 1000 times scanning department groups

Pattern observation: The total work grows roughly proportional to the number of employees times the average department size.

Final Time Complexity

Time Complexity: O(n * m)

This means the work grows with the number of employees (n) times the average number of employees per department (m).

Common Mistake

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

[OK] Correct: The subquery depends on each row of the main query, so it runs repeatedly, increasing total work.

Interview Connect

Understanding how correlated subqueries scale helps you write efficient queries and explain their performance clearly.

Self-Check

"What if the subquery was replaced by a join with grouping? How would the time complexity change?"

Practice

1. What is a correlated subquery in MySQL?

easy

A. A subquery that uses values from the outer query for each row.

B. A subquery that runs only once before the outer query.

C. A query that joins two tables without any subqueries.

D. A subquery that returns a fixed constant value.

Solution

1. Step 1: Understand subquery behavior

   A correlated subquery depends on the outer query's current row values to execute.

2. Step 2: Compare options

   The option describing a subquery that uses values from the outer query for each row correctly defines a correlated subquery.

3. Final Answer:

   A subquery that uses values from the outer query for each row. -> Option A

4. Quick Check:

   Correlated subquery = uses outer row values [OK]

Hint: Correlated subqueries depend on outer query row values [OK]

Common Mistakes:

• Thinking subqueries always run once
• Confusing joins with subqueries
• Assuming subqueries return constants only

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

easy

A. SELECT * FROM employees WHERE salary > (SELECT AVG(salary) FROM employees e2 WHERE e2.department_id = employees.department_id);

B. SELECT * FROM employees WHERE salary IN (SELECT salary FROM employees);

C. SELECT * FROM employees WHERE salary > (SELECT AVG(salary) FROM employees);

D. SELECT * FROM employees WHERE salary = 50000;

Solution

1. Step 1: Identify correlated subquery syntax

   A correlated subquery references a column from the outer query inside the subquery, like e2.department_id = employees.department_id.

2. Step 2: Check each option

   SELECT * FROM employees WHERE salary > (SELECT AVG(salary) FROM employees e2 WHERE e2.department_id = employees.department_id); uses the outer table's column inside the subquery condition, making it a correlated subquery.

3. Final Answer:

   SELECT * FROM employees WHERE salary > (SELECT AVG(salary) FROM employees e2 WHERE e2.department_id = employees.department_id); -> Option A

4. Quick Check:

   Correlated subquery syntax = SELECT * FROM employees WHERE salary > (SELECT AVG(salary) FROM employees e2 WHERE e2.department_id = employees.department_id); [OK]

Hint: Look for subquery referencing outer query table alias [OK]

Common Mistakes:

• Missing outer table reference in subquery
• Using subquery without WHERE clause for correlation
• Confusing correlated with simple subqueries

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

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

medium

A. Employees whose salary is above the average salary of all departments combined.

B. Employees whose salary is above the average salary of all employees.

C. Employees whose salary is above the average salary of their department.

D. Syntax error due to subquery referencing outer query.

Solution

1. Step 1: Understand the subquery condition

   The subquery calculates the average salary for the department of the current employee (using e.department_id).

2. Step 2: Compare employee salary with department average

   The outer query selects employees whose salary is greater than their department's average salary.

3. Final Answer:

   Employees whose salary is above the average salary of their department. -> Option C

4. Quick Check:

   Correlated subquery filters by department average salary [OK]

Hint: Check if subquery filters by outer row's department_id [OK]

Common Mistakes:

• Thinking subquery calculates overall average salary
• Assuming syntax error due to correlation
• Confusing department and employee averages

4. Identify the error in this correlated subquery:

SELECT e1.name FROM employees e1 WHERE salary > (SELECT AVG(salary) FROM employees e2 WHERE e2.department = e1.department_id);

medium

A. Subquery cannot reference outer query columns.

B. Alias 'e1' is not allowed in subquery.

C. Missing GROUP BY clause in subquery.

D. Column 'department' does not exist in employees table.

Solution

1. Step 1: Check column names in subquery condition

   The subquery compares e2.department to e1.department_id, but 'department' column does not exist in employees table.

2. Step 2: Confirm correct column usage

   The correct column should be e2.department_id to match e1.department_id for correlation.

3. Final Answer:

   Column 'department' does not exist in employees table. -> Option D

4. Quick Check:

   Invalid column name causes error [OK]

Hint: Verify column names match exactly in both queries [OK]

Common Mistakes:

• Using wrong column names for correlation
• Assuming alias usage causes error
• Thinking GROUP BY is required in subquery

5. You want to find all departments where every employee earns more than the average salary of all employees in the company. Which query correctly uses a correlated subquery to achieve this?

hard

A. SELECT d.name FROM departments d WHERE ALL (SELECT salary FROM employees WHERE department_id = d.id) > (SELECT AVG(salary) FROM employees);

B. SELECT d.name FROM departments d WHERE NOT EXISTS (SELECT 1 FROM employees e WHERE e.department_id = d.id AND e.salary <= (SELECT AVG(salary) FROM employees));

C. SELECT d.name FROM departments d WHERE EXISTS (SELECT 1 FROM employees e WHERE e.department_id = d.id AND e.salary > (SELECT AVG(salary) FROM employees));

D. SELECT d.name FROM departments d WHERE EXISTS (SELECT 1 FROM employees e WHERE e.department_id = d.id AND e.salary > (SELECT AVG(salary) FROM employees WHERE department_id = d.id));

Solution

1. Step 1: Understand the requirement

   We want departments where every employee earns more than the company-wide average salary.

2. Step 2: Analyze the NOT EXISTS query

   SELECT d.name FROM departments d WHERE NOT EXISTS (SELECT 1 FROM employees e WHERE e.department_id = d.id AND e.salary <= (SELECT AVG(salary) FROM employees)); uses NOT EXISTS to ensure no employee in the department earns less or equal to the company average, meaning all earn more.

3. Step 3: Check other options

   The options using EXISTS check for the existence of at least one qualifying employee, not all. The option attempting to use ALL with a subquery on the left side uses invalid syntax in MySQL.

4. Final Answer:

   SELECT d.name FROM departments d WHERE NOT EXISTS (SELECT 1 FROM employees e WHERE e.department_id = d.id AND e.salary <= (SELECT AVG(salary) FROM employees)); -> Option B

5. Quick Check:

   NOT EXISTS ensures all employees earn above average [OK]

Hint: Use NOT EXISTS to check all employees meet condition [OK]

Common Mistakes:

• Using EXISTS instead of NOT EXISTS for 'all' condition
• Misusing ALL keyword in MySQL
• Comparing with department average instead of company average