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?"