Self JOIN in MySQL - Time & Space Complexity

Time Complexity: Self JOIN

O(n²)

Understanding Time Complexity

When we use a self join in SQL, we combine a table with itself to compare rows. Understanding how the time it takes grows as the table gets bigger helps us write better queries.

We want to know: how does the work increase when the number of rows grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT e1.employee_id, e2.employee_id
FROM employees e1
JOIN employees e2 ON e1.manager_id = e2.employee_id;
    

This query finds pairs of employees and their managers by joining the employees table to itself.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Comparing each row in the employees table to rows in the same table to find matching manager relationships.
• How many times: For each employee row, the database checks multiple rows in the same table to find matches.

How Execution Grows With Input

As the number of employees grows, the number of comparisons grows quickly because each employee is checked against many others.

Input Size (n)	Approx. Operations
10	About 10 checks
100	About 100 checks
1000	About 1000 checks

Pattern observation: The work grows much faster than the number of rows; doubling rows roughly quadruples the work.

Final Time Complexity

Time Complexity: O(n²)

This means if the table size doubles, the work to join it with itself grows about four times as much.

Common Mistake

[X] Wrong: "Joining a table to itself only doubles the work, so it's O(n)."

[OK] Correct: Because each row is compared to many others, the total checks multiply, making the work grow much faster than just doubling.

Interview Connect

Understanding how self joins scale helps you explain query performance clearly. This skill shows you can think about how data size affects work, which is valuable in real projects.

Self-Check

"What if we added an index on the manager_id column? How would the time complexity change?"

Practice

1. What is the main purpose of using a SELF JOIN in SQL?

easy

A. To combine rows from two tables without any condition

B. To join two different tables based on a common column

C. To join a table to itself to compare rows within the same table

D. To delete duplicate rows from a table

Solution

1. Step 1: Understand what a SELF JOIN does

   A SELF JOIN connects a table to itself using aliases to compare rows within the same table.

2. Step 2: Compare with other JOIN types

   Other joins combine different tables or rows but SELF JOIN specifically works on one table to find relationships inside it.

3. Final Answer:

   To join a table to itself to compare rows within the same table -> Option C

4. Quick Check:

   SELF JOIN = join table to itself [OK]

Hint: SELF JOIN means joining table to itself using aliases [OK]

Common Mistakes:

• Confusing SELF JOIN with JOIN between two different tables
• Thinking SELF JOIN deletes duplicates
• Assuming SELF JOIN combines unrelated tables

2. Which of the following is the correct syntax to perform a SELF JOIN on a table named employees with aliases e1 and e2 to find employees and their managers?

easy

A. SELECT * FROM employees e1 JOIN employees e2 ON e1.manager_id = e2.id;

B. SELECT * FROM employees JOIN employees ON employees.manager_id = employees.id;

C. SELECT * FROM employees e1 JOIN employees e2 WHERE e1.id = e2.manager_id;

D. SELECT * FROM employees e1 LEFT JOIN employees e2 ON e1.id = e2.id;

Solution

1. Step 1: Identify correct alias usage

   Using aliases e1 and e2 for the same table is required for SELF JOIN to distinguish rows.

2. Step 2: Check JOIN condition syntax

   The condition e1.manager_id = e2.id correctly links employees to their managers.

3. Final Answer:

   SELECT * FROM employees e1 JOIN employees e2 ON e1.manager_id = e2.id; -> Option A

4. Quick Check:

   Correct alias and ON condition = SELECT * FROM employees e1 JOIN employees e2 ON e1.manager_id = e2.id; [OK]

Hint: Use aliases and ON clause for SELF JOIN syntax [OK]

Common Mistakes:

• Not using aliases for the same table
• Missing ON clause or wrong condition
• Using comma join without condition

3. Given the table employees with columns id, name, and manager_id, what will this query return?

SELECT e1.name AS Employee, e2.name AS Manager FROM employees e1 LEFT JOIN employees e2 ON e1.manager_id = e2.id;

medium

A. List of employees with their managers' names; NULL if no manager

B. List of managers with their employees' names

C. List of employees with their own names repeated

D. Syntax error due to missing WHERE clause

Solution

1. Step 1: Understand LEFT JOIN with SELF JOIN

   The query joins employees to themselves matching manager_id to id, showing employee and manager names.

2. Step 2: Interpret NULL values

   If an employee has no manager (manager_id is NULL), LEFT JOIN keeps employee row with manager name as NULL.

3. Final Answer:

   List of employees with their managers' names; NULL if no manager -> Option A

4. Quick Check:

   LEFT JOIN keeps all employees, shows manager or NULL [OK]

Hint: LEFT JOIN keeps all employees, shows NULL for missing managers [OK]

Common Mistakes:

• Confusing employee and manager roles
• Expecting only matched rows (INNER JOIN behavior)
• Thinking query has syntax error

4. Identify the error in this SELF JOIN query:

SELECT e1.name, e2.name FROM employees e1 JOIN employees e2 ON e1.id = e2.manager_id WHERE e1.manager_id = NULL;

medium

A. JOIN condition is reversed

B. Missing alias for employees table

C. Using JOIN instead of LEFT JOIN causes error

D. Incorrect use of NULL comparison in WHERE clause

Solution

1. Step 1: Check WHERE clause for NULL comparison

   Using = NULL is incorrect; SQL requires IS NULL to check NULL values.

2. Step 2: Verify other parts of query

   Aliases are correct, JOIN condition is valid, and JOIN type is allowed.

3. Final Answer:

   Incorrect use of NULL comparison in WHERE clause -> Option D

4. Quick Check:

   Use IS NULL, not = NULL for NULL checks [OK]

Hint: Use IS NULL, not = NULL to check NULL values [OK]

Common Mistakes:

• Using = NULL instead of IS NULL
• Confusing JOIN condition direction
• Assuming JOIN type causes error

5. You have a table employees with columns id, name, and manager_id. Write a query using SELF JOIN to find all employees who are also managers of others. Which query correctly returns the names of employees who manage at least one other employee?

hard

A. SELECT e1.name FROM employees e1 LEFT JOIN employees e2 ON e1.id = e2.manager_id WHERE e2.id IS NULL;

B. SELECT DISTINCT e1.name FROM employees e1 JOIN employees e2 ON e1.id = e2.manager_id;

C. SELECT e2.name FROM employees e1 JOIN employees e2 ON e1.manager_id = e2.id;

D. SELECT e1.name FROM employees e1 JOIN employees e2 ON e1.manager_id = e2.id WHERE e1.id = e2.id;

Solution

1. Step 1: Understand the requirement

   We want employees who appear as managers (their id is manager_id for others).

2. Step 2: Analyze each query

   SELECT DISTINCT e1.name FROM employees e1 JOIN employees e2 ON e1.id = e2.manager_id; joins employees to those they manage and selects distinct manager names correctly. SELECT e1.name FROM employees e1 LEFT JOIN employees e2 ON e1.id = e2.manager_id WHERE e2.id IS NULL; finds employees with no subordinates (wrong). SELECT e2.name FROM employees e1 JOIN employees e2 ON e1.manager_id = e2.id; returns manager names duplicated for each subordinate (wrong). SELECT e1.name FROM employees e1 JOIN employees e2 ON e1.manager_id = e2.id WHERE e1.id = e2.id; has incorrect condition and will return no rows.

3. Final Answer:

   SELECT DISTINCT e1.name FROM employees e1 JOIN employees e2 ON e1.id = e2.manager_id; -> Option B

4. Quick Check:

   Managers have others with manager_id = their id [OK]

Hint: Join on e1.id = e2.manager_id to find managers [OK]

Common Mistakes:

• Selecting employees without subordinates
• Reversing join condition
• Using wrong WHERE clause filters