Self join for hierarchical data in SQL - Time & Space Complexity

Time Complexity: Self join for hierarchical data

O(n)

Understanding Time Complexity

When we use a self join to find relationships within the same table, it is important to understand how the work grows as the table gets bigger.

We want to know how the number of operations changes when the number of rows increases.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT e1.employee_id, e1.name, e2.name AS manager_name
FROM employees e1
LEFT JOIN employees e2 ON e1.manager_id = e2.employee_id;

This query finds each employee and their manager by joining the employees table to itself.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: For each employee row, the database looks for a matching manager row in the same table.
• How many times: This matching happens once per employee, so it repeats as many times as there are employees.

How Execution Grows With Input

As the number of employees grows, the database must check more rows to find matches.

Input Size (n)	Approx. Operations
10	About 10 lookups for managers
100	About 100 lookups for managers
1000	About 1000 lookups for managers

Pattern observation: The number of operations grows directly with the number of employees.

Final Time Complexity

Time Complexity: O(n)

This means the work grows in a straight line as the number of rows increases.

Common Mistake

[X] Wrong: "Because it joins the table to itself, the work is squared (n²)."

[OK] Correct: The join uses a key to find one matching row per employee, so it does not check every pair of rows.

Interview Connect

Understanding how self joins scale helps you explain how databases handle hierarchical data efficiently, a useful skill in many real projects.

Self-Check

"What if the join condition was missing an index? How would the time complexity change?"

Practice

1. What is the main purpose of using a self join in SQL when working with hierarchical data?

easy

A. To join two different tables based on a common key

B. To connect rows within the same table to show parent-child relationships

C. To combine rows from multiple tables into one result

D. To delete duplicate rows from a table

Solution

1. Step 1: Understand self join concept

   A self join connects rows within the same table, unlike regular joins that connect different tables.

2. Step 2: Apply to hierarchical data

   Hierarchical data like employees and managers require linking rows to show parent-child links, which self join does.

3. Final Answer:

   To connect rows within the same table to show parent-child relationships -> Option B

4. Quick Check:

   Self join = parent-child links [OK]

Hint: Self join links rows in one table for hierarchy [OK]

Common Mistakes:

• Confusing self join with joining different tables
• Thinking self join deletes duplicates
• Assuming self join merges tables horizontally

2. Which of the following SQL queries correctly uses a self join to find each employee's manager name from an employees table with columns id, name, and manager_id?

easy

A. SELECT e.name, m.name AS manager_name FROM employees e JOIN employees m ON e.id = m.manager_id;

B. SELECT e.name, m.name AS manager_name FROM employees e JOIN managers m ON e.manager_id = m.id;

C. SELECT e.name, m.name AS manager_name FROM employees e JOIN employees m ON e.manager_id = m.id;

D. SELECT e.name, m.name AS manager_name FROM employees e LEFT JOIN employees m ON e.id = m.manager_id;

Solution

1. Step 1: Identify correct table aliases and join condition

   We must join the employees table to itself using aliases (e and m) and match e.manager_id = m.id to get the manager's name.

2. Step 2: Check each option

   SELECT e.name, m.name AS manager_name FROM employees e JOIN employees m ON e.manager_id = m.id; correctly uses self join with proper aliases and join condition. Options B uses a non-existent table 'managers'. SELECT e.name, m.name AS manager_name FROM employees e JOIN employees m ON e.id = m.manager_id; reverses the join condition. SELECT e.name, m.name AS manager_name FROM employees e LEFT JOIN employees m ON e.id = m.manager_id; uses LEFT JOIN but with wrong condition.

3. Final Answer:

   SELECT e.name, m.name AS manager_name FROM employees e JOIN employees m ON e.manager_id = m.id; -> Option C

4. Quick Check:

   Correct self join syntax = SELECT e.name, m.name AS manager_name FROM employees e JOIN employees m ON e.manager_id = m.id; [OK]

Hint: Match child.manager_id to parent.id in self join [OK]

Common Mistakes:

• Using wrong join condition reversing keys
• Joining with a non-existent table
• Confusing LEFT JOIN with INNER JOIN in this context

3. Given the categories table:

id | name       | parent_id
---+------------+----------
1  | Electronics| NULL
2  | Computers  | 1
3  | Laptops    | 2
4  | Phones     | 1
5  | Smartphones| 4

What will be the output of this query?

SELECT c.name AS category, p.name AS parent_category
FROM categories c
LEFT JOIN categories p ON c.parent_id = p.id
ORDER BY c.id;

medium

A. [{"category": "Electronics", "parent_category": null}, {"category": "Computers", "parent_category": "Electronics"}, {"category": "Laptops", "parent_category": "Computers"}, {"category": "Phones", "parent_category": "Electronics"}, {"category": "Smartphones", "parent_category": "Phones"}]

B. [{"category": "Electronics", "parent_category": "Electronics"}, {"category": "Computers", "parent_category": "Computers"}, {"category": "Laptops", "parent_category": "Laptops"}, {"category": "Phones", "parent_category": "Phones"}, {"category": "Smartphones", "parent_category": "Smartphones"}]

C. [{"category": "Electronics", "parent_category": "Computers"}, {"category": "Computers", "parent_category": "Laptops"}, {"category": "Laptops", "parent_category": "Phones"}, {"category": "Phones", "parent_category": "Smartphones"}, {"category": "Smartphones", "parent_category": null}]

D. [{"category": "Electronics", "parent_category": "Phones"}, {"category": "Computers", "parent_category": "Smartphones"}, {"category": "Laptops", "parent_category": null}, {"category": "Phones", "parent_category": "Computers"}, {"category": "Smartphones", "parent_category": "Electronics"}]

Solution

1. Step 1: Understand the LEFT JOIN on self

   The query joins each category (c) with its parent category (p) by matching c.parent_id = p.id. If no parent, parent_category is NULL.

2. Step 2: Map each category to its parent

   Electronics has NULL parent, Computers' parent is Electronics, Laptops' parent is Computers, Phones' parent is Electronics, Smartphones' parent is Phones.

3. Final Answer:

   [{"category": "Electronics", "parent_category": null}, {"category": "Computers", "parent_category": "Electronics"}, {"category": "Laptops", "parent_category": "Computers"}, {"category": "Phones", "parent_category": "Electronics"}, {"category": "Smartphones", "parent_category": "Phones"}] -> Option A

4. Quick Check:

   Parent matches child.parent_id = parent.id [OK]

Hint: Parent name is NULL if parent_id is NULL [OK]

Common Mistakes:

• Assuming parent_category equals category name
• Mixing up parent_id and id in join condition
• Ignoring NULL parent_id results

4. Consider this SQL query intended to list employees and their managers:

SELECT e.name, m.name AS manager_name
FROM employees e
JOIN employees m ON e.id = m.manager_id;

What is the error in this query?

medium

A. The join condition is reversed; it should be e.manager_id = m.id

B. The table alias 'm' is not defined

C. The query should use LEFT JOIN instead of JOIN

D. The SELECT clause should use m.manager_name instead of m.name

Solution

1. Step 1: Analyze the join condition

   The query joins on e.id = m.manager_id, which means employee id equals manager's manager_id, which is incorrect.

2. Step 2: Correct join condition for manager lookup

   To find each employee's manager, join on e.manager_id = m.id so employee's manager_id matches manager's id.

3. Final Answer:

   The join condition is reversed; it should be e.manager_id = m.id -> Option A

4. Quick Check:

   Join on employee.manager_id = manager.id [OK]

Hint: Match child.manager_id to parent.id, not reverse [OK]

Common Mistakes:

• Reversing join keys causing wrong matches
• Confusing alias usage
• Assuming INNER JOIN always needed

5. You have a parts table with columns part_id, part_name, and parent_part_id. Write a query to list each part with its top-level ancestor part name (the root parent with parent_part_id IS NULL). Which approach correctly achieves this using self joins?

hard

A. Use UNION ALL to combine parts with their children without join

B. Use a single self join on part_id = parent_part_id to get the immediate parent only

C. Use GROUP BY part_id and MAX(parent_part_id) to find the top ancestor

D. Use multiple self joins chaining parent_part_id until parent_part_id IS NULL, selecting the top ancestor name

Solution

1. Step 1: Understand hierarchical traversal

   Finding the top-level ancestor requires following parent links repeatedly until reaching a part with no parent (parent_part_id IS NULL).

2. Step 2: Use multiple self joins or recursive CTE

   This can be done by chaining self joins or using recursive queries to climb the hierarchy to the root ancestor.

3. Final Answer:

   Use multiple self joins chaining parent_part_id until parent_part_id IS NULL, selecting the top ancestor name -> Option D

4. Quick Check:

   Top ancestor requires repeated self joins [OK]

Hint: Top ancestor needs repeated self joins or recursion [OK]

Common Mistakes:

• Using single join only finds immediate parent
• Trying to use aggregate functions incorrectly
• Ignoring recursive nature of hierarchy