Self join concept in SQL - Time & Space Complexity

Time Complexity: Self join concept

O(n²)

Understanding Time Complexity

When we use a self join, we combine a table with itself to compare rows. Understanding how long this takes helps us know if it will work well with big data.

We want to find out how the work grows as the table gets bigger.

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 matches.
• How many times: For each employee row, the database checks multiple rows in the same table to find matching managers.

How Execution Grows With Input

As the number of employees grows, the number of comparisons grows much faster because each row is checked against many others.

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

Pattern observation: The work grows roughly by the square of the number of rows.

Final Time Complexity

Time Complexity: O(n²)

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

Common Mistake

[X] Wrong: "A self join only takes as long as a normal join, so it grows linearly with data size."

[OK] Correct: Because the table is joined with itself, the number of comparisons grows much faster, roughly with the square of the number of rows.

Interview Connect

Understanding how self joins scale helps you explain your choices clearly and shows you know how queries behave with bigger data. This skill is useful in many 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 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 the concept of self join

   A self join is used when you want to compare rows within the same table by treating it as two separate tables using aliases.

2. Step 2: Identify the correct purpose

   Joining a table to itself allows you to find relationships or comparisons between rows in the same table, such as hierarchical data or pairs.

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 joining two different tables
• Thinking self join deletes duplicates
• Assuming self join combines rows without condition

2. Which of the following is the correct syntax to perform a self join on a table named employees with alias e1 and e2?

easy

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

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

C. SELECT * FROM employees e1, employees e2 ON e1.id = e2.manager_id;

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

Solution

1. Step 1: Use table aliases for self join

   To join a table to itself, you must use aliases like e1 and e2 to distinguish the two instances.

2. Step 2: Write the join condition correctly

   The join condition should relate columns from the two aliases, for example e1.id = e2.manager_id to find employees and their managers.

3. Final Answer:

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

4. Quick Check:

   Self join syntax = table alias + join condition [OK]

Hint: Always use aliases to distinguish the same table twice [OK]

Common Mistakes:

• Not using aliases causes syntax errors
• Joining on wrong columns returns wrong results
• Using comma join without aliases is confusing

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. Syntax error due to missing WHERE clause

B. List of employees with their managers' names, NULL if no manager

C. List of employees without managers only

D. List of managers with their employees' names

Solution

1. Step 1: Understand the LEFT JOIN on self join

   The query joins the employees table to itself using aliases e1 and e2, matching e1.manager_id to e2.id to find each employee's manager.

2. Step 2: Interpret the SELECT columns and join type

   Using LEFT JOIN means all employees (e1) appear, even if they have no manager (e2.name will be NULL). The SELECT shows employee and manager names.

3. Final Answer:

   List of employees with their managers' names, NULL if no manager -> Option B

4. Quick Check:

   LEFT JOIN self join shows all employees with managers [OK]

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

Common Mistakes:

• Confusing employee and manager columns
• Thinking it lists only managers or only employees without managers
• Assuming syntax error without WHERE clause

4. Identify the error in this self join query:

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

medium

A. Missing table aliases for employees

B. Using JOIN instead of LEFT JOIN causes error

C. Syntax error due to missing WHERE clause

D. The join condition compares the same column, causing incorrect results

Solution

1. Step 1: Analyze the join condition

   The query joins employees to itself on e1.id = e2.id, which matches each row to itself only, not to related rows.

2. Step 2: Understand the effect of the condition

   This join condition does not find relationships like manager or pairs; it just duplicates rows, which is likely incorrect for self join use.

3. Final Answer:

   The join condition compares the same column, causing incorrect results -> Option D

4. Quick Check:

   Self join needs meaningful join condition, not same column equals [OK]

Hint: Join condition must relate different columns for meaningful self join [OK]

Common Mistakes:

• Joining on identical columns returns only same rows
• Forgetting to use aliases
• Assuming JOIN requires WHERE clause

5. You have a table employees with columns id, name, and manager_id. Write a query using self join to find all employees who share the same manager. Which query correctly achieves this?

hard

A. SELECT e1.name, e2.name FROM employees e1 JOIN employees e2 ON e1.manager_id = e2.manager_id WHERE e1.id <> e2.id;

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

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

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

Solution

1. Step 1: Understand the goal

   We want pairs of employees who share the same manager, so their manager_id values must be equal but employees must be different.

2. Step 2: Write the self join condition

   Joining on e1.manager_id = e2.manager_id finds employees with the same manager. Adding WHERE e1.id <> e2.id excludes pairing an employee with themselves.

3. Final Answer:

   SELECT e1.name, e2.name FROM employees e1 JOIN employees e2 ON e1.manager_id = e2.manager_id WHERE e1.id <> e2.id; -> Option A

4. Quick Check:

   Same manager and different employees = SELECT e1.name, e2.name FROM employees e1 JOIN employees e2 ON e1.manager_id = e2.manager_id WHERE e1.id <> e2.id; [OK]

Hint: Join on manager_id and exclude same employee IDs [OK]

Common Mistakes:

• Joining on employee id instead of manager id
• Not excluding same employee pairs
• Using equality on employee IDs causing no pairs