Self join patterns in PostgreSQL - Time & Space Complexity

Time Complexity: Self join patterns

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 the query will run fast or slow as data grows.

We want to find out how the work needed changes when the table gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT a.id, b.id
FROM employees a
JOIN employees b ON a.manager_id = b.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 first table to rows in the second table to find matches.
• How many times: For each of the n rows, the database looks for matching rows in the same table, potentially checking many rows.

How Execution Grows With Input

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

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

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 needed to complete the join roughly quadruples.

Common Mistake

[X] Wrong: "A self join only takes as long as a normal join, so it's always fast."

[OK] Correct: Because the table joins with itself, the number of comparisons can grow much faster, making the query slower as data grows.

Interview Connect

Understanding how self joins scale helps you explain query performance clearly and shows you can think about how data size affects work done.

Self-Check

"What if we add 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 PostgreSQL?

easy

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

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

C. To create a backup of a 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 joining the table to itself.

2. Step 2: Differentiate from other joins

   Other joins combine different tables, but self join works on one table with aliases to distinguish instances.

3. Final Answer:

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

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 creates a new table
• Assuming self join deletes duplicates

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

easy

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

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

C. SELECT * FROM employees AS e1, employees AS e2 WHERE e1.id = e2.id;

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

Solution

1. Step 1: Identify correct alias usage

   Using aliases e1 and e2 for the same table employees is necessary to distinguish instances.

2. Step 2: Check join condition

   The join 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 D

4. Quick Check:

   Use aliases and proper ON condition [OK]

Hint: Use aliases and ON clause for self join syntax [OK]

Common Mistakes:

• Not using aliases causing ambiguity
• Wrong join condition columns
• Using comma join without ON clause

3. Given the table employees(id, name, manager_id) with data:

id | name  | manager_id
---+-------+-----------
1  | Alice | NULL
2  | Bob   | 1
3  | Carol | 1
4  | Dave  | 2

What will be the output of this query?

SELECT e1.name AS employee, e2.name AS manager
FROM employees e1
LEFT JOIN employees e2 ON e1.manager_id = e2.id
ORDER BY e1.id;

medium

A. [{"employee": "Alice", "manager": null}, {"employee": "Bob", "manager": null}, {"employee": "Carol", "manager": null}, {"employee": "Dave", "manager": null}]

B. [{"employee": "Alice", "manager": null}, {"employee": "Bob", "manager": "Alice"}, {"employee": "Carol", "manager": "Alice"}, {"employee": "Dave", "manager": "Bob"}]

C. [{"employee": "Alice", "manager": "Alice"}, {"employee": "Bob", "manager": "Bob"}, {"employee": "Carol", "manager": "Carol"}, {"employee": "Dave", "manager": "Dave"}]

D. [{"employee": "Alice", "manager": "Bob"}, {"employee": "Bob", "manager": "Carol"}, {"employee": "Carol", "manager": "Dave"}, {"employee": "Dave", "manager": null}]

Solution

1. Step 1: Understand the join logic

   The LEFT JOIN matches each employee's manager_id to the manager's id, returning manager's name or null if none.

2. Step 2: Map each employee to their manager

   Alice has no manager (null), Bob and Carol have Alice as manager, Dave has Bob as manager.

3. Final Answer:

   [{"employee": "Alice", "manager": null}, {"employee": "Bob", "manager": "Alice"}, {"employee": "Carol", "manager": "Alice"}, {"employee": "Dave", "manager": "Bob"}] -> Option B

4. Quick Check:

   LEFT JOIN matches manager_id to id [OK]

Hint: Match manager_id to id with LEFT JOIN for manager names [OK]

Common Mistakes:

• Confusing employee and manager columns
• Using INNER JOIN losing employees without managers
• Assuming manager_id is employee id

4. Consider this query intended to find pairs of employees who share the same manager:

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

What is the main issue with this query?

medium

A. It will return duplicate pairs in both orders (e.g., (Alice, Bob) and (Bob, Alice))

B. It will not return any rows because of the WHERE clause

C. It causes a syntax error due to missing aliases

D. It only returns employees with no manager

Solution

1. Step 1: Analyze join condition

   The join matches employees with the same manager_id, including reversed pairs.

2. Step 2: Check WHERE clause effect

   WHERE e1.id != e2.id avoids self-pairing but does not prevent duplicate pairs in reverse order.

3. Final Answer:

   It will return duplicate pairs in both orders (e.g., (Alice, Bob) and (Bob, Alice)) -> Option A

4. Quick Check:

   Self join can produce reversed duplicate pairs [OK]

Hint: Self join pairs may appear twice reversed; use filtering [OK]

Common Mistakes:

• Assuming WHERE clause removes duplicates
• Thinking query causes syntax error
• Believing it returns only employees without managers

5. You want to find all employees who are managers themselves, i.e., employees who have at least one other employee reporting to them. Which self join query correctly achieves this?

hard

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

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

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

D. SELECT e1.name FROM employees e1 WHERE e1.manager_id IS NOT NULL;

Solution

1. Step 1: Understand the requirement

   Managers are employees whose id appears as manager_id for others.

2. Step 2: Analyze each option

   SELECT DISTINCT e1.name FROM employees e1 JOIN employees e2 ON e1.id = e2.manager_id; joins employees where e1.id = e2.manager_id, selecting distinct managers correctly.

3. Final Answer:

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

4. Quick Check:

   Join on id = manager_id finds managers [OK]

Hint: Join employees where id = manager_id to find managers [OK]

Common Mistakes:

• Using LEFT JOIN with IS NULL returns non-managers
• Joining on wrong columns (manager_id = id reversed)
• Filtering on manager_id IS NOT NULL returns employees with managers