FULL OUTER JOIN in PostgreSQL - Time & Space Complexity

Time Complexity: FULL OUTER JOIN

O(n * m)

Understanding Time Complexity

When we use a FULL OUTER JOIN in a database, we combine rows from two tables, keeping all rows from both sides.

We want to understand how the time it takes grows as the tables get bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT *
FROM table_a
FULL OUTER JOIN table_b
ON table_a.id = table_b.id;
    

This query returns all rows from both tables, matching rows where the id is the same, and filling with NULLs where there is no match.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Comparing rows from both tables to find matches.
• How many times: Each row in the first table is compared to rows in the second table to find matching ids.

How Execution Grows With Input

As the number of rows in each table grows, the work to find matching rows grows too.

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

Pattern observation: The number of comparisons grows quickly as both tables get bigger, roughly multiplying their sizes.

Final Time Complexity

Time Complexity: O(n * m)

This means the time grows roughly by multiplying the number of rows in the first table (n) by the number of rows in the second table (m).

Common Mistake

[X] Wrong: "FULL OUTER JOIN only looks at one table at a time, so time grows linearly."

[OK] Correct: The join must compare rows from both tables to find matches, so it depends on both table sizes together, not just one.

Interview Connect

Understanding how joins scale helps you write efficient queries and explain your reasoning clearly in interviews.

Self-Check

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

Practice

1. What does a FULL OUTER JOIN do in PostgreSQL?

easy

A. It returns all rows from the right table and matching rows from the left table.

B. It returns only rows that have matching values in both tables.

C. It returns all rows from the left table and matching rows from the right table.

D. It returns all rows from both tables, matching where possible, and NULLs where no match exists.

Solution

1. Step 1: Understand the join types

   INNER JOIN returns only matching rows; LEFT JOIN returns all left table rows plus matches; RIGHT JOIN returns all right table rows plus matches.

2. Step 2: Define FULL OUTER JOIN behavior

   FULL OUTER JOIN returns all rows from both tables, matching where possible, and fills unmatched columns with NULL.

3. Final Answer:

   It returns all rows from both tables, matching where possible, and NULLs where no match exists. -> Option D

4. Quick Check:

   FULL OUTER JOIN = all rows both tables [OK]

Hint: Remember: FULL OUTER JOIN = all rows from both tables [OK]

Common Mistakes:

• Confusing FULL OUTER JOIN with INNER JOIN
• Thinking FULL OUTER JOIN returns only left or right table rows
• Assuming unmatched rows are excluded

2. Which of the following is the correct syntax for a FULL OUTER JOIN in PostgreSQL?

easy

A. SELECT * FROM table1 FULL OUTER JOIN table2 ON table1.id = table2.id;

B. SELECT * FROM table1 JOIN FULL OUTER table2 ON table1.id = table2.id;

C. SELECT * FROM table1 FULL JOIN table2 WHERE table1.id = table2.id;

D. SELECT * FROM table1 OUTER FULL JOIN table2 ON table1.id = table2.id;

Solution

1. Step 1: Recall PostgreSQL FULL OUTER JOIN syntax

   The correct syntax is: SELECT ... FROM table1 FULL OUTER JOIN table2 ON condition;

2. Step 2: Check each option

   The syntax 'SELECT * FROM table1 FULL OUTER JOIN table2 ON table1.id = table2.id;' matches exactly. Others err: 'JOIN FULL OUTER' wrong order; 'FULL JOIN ... WHERE' misuses WHERE for join; 'OUTER FULL JOIN' wrong sequence.

3. Final Answer:

   SELECT * FROM table1 FULL OUTER JOIN table2 ON table1.id = table2.id; -> Option A

4. Quick Check:

   FULL OUTER JOIN syntax = FULL OUTER JOIN ON [OK]

Hint: FULL OUTER JOIN always uses 'FULL OUTER JOIN ... ON' syntax [OK]

Common Mistakes:

• Swapping JOIN and FULL OUTER keywords
• Omitting ON clause
• Using WHERE instead of ON for join condition

3. Given these tables:
Table A:
ID | Name
1 | Alice
2 | Bob
4 | Diana

Table B:
ID | City
2 | Paris
3 | London
4 | Berlin

What is the result of:
SELECT COALESCE(A.ID, B.ID) AS ID, A.Name, B.City FROM A FULL OUTER JOIN B ON A.ID = B.ID ORDER BY ID;

medium

A. [{2, 'Bob', 'Paris'}, {3, NULL, 'London'}, {4, 'Diana', 'Berlin'}]

B. [{1, 'Alice', NULL}, {2, 'Bob', NULL}, {3, NULL, 'London'}, {4, 'Diana', 'Berlin'}]

C. [{1, 'Alice', NULL}, {2, 'Bob', 'Paris'}, {3, NULL, 'London'}, {4, 'Diana', 'Berlin'}]

D. [{1, 'Alice', NULL}, {2, 'Bob', 'Paris'}, {4, 'Diana', 'Berlin'}]

Solution

1. Step 1: Identify matching and unmatched IDs

   Matching IDs: 2 and 4. Unmatched in A: 1. Unmatched in B: 3.

2. Step 2: Construct FULL OUTER JOIN result

   Rows:
   - ID 1: Name 'Alice', City NULL (no match in B)
   - ID 2: Name 'Bob', City 'Paris' (match)
   - ID 3: Name NULL, City 'London' (no match in A)
   - ID 4: Name 'Diana', City 'Berlin' (match)

3. Final Answer:

   [{1, 'Alice', NULL}, {2, 'Bob', 'Paris'}, {3, NULL, 'London'}, {4, 'Diana', 'Berlin'}] -> Option C

4. Quick Check:

   FULL OUTER JOIN includes all rows with NULLs for unmatched [OK]

Hint: Match IDs, include all rows, NULL for missing side [OK]

Common Mistakes:

• Excluding unmatched rows from either table
• Mixing up NULL placement
• Ordering rows incorrectly

4. Consider this query:
SELECT * FROM A FULL OUTER JOIN B ON A.id = B.id WHERE A.name = 'Alice';
Why might this query return fewer rows than expected?

medium

A. Because the WHERE clause filters out rows where A.name is NULL, excluding unmatched rows from B.

B. Because FULL OUTER JOIN only returns matching rows.

C. Because the ON condition is incorrect syntax.

D. Because the query needs GROUP BY to include all rows.

Solution

1. Step 1: Understand FULL OUTER JOIN with WHERE clause

   FULL OUTER JOIN returns all rows, but WHERE filters after join. Filtering on A.name excludes rows where A.name is NULL (unmatched in A).

2. Step 2: Effect of filtering on unmatched rows

   Rows unmatched in A have NULL for A.name, so WHERE A.name = 'Alice' removes them, reducing rows.

3. Final Answer:

   Because the WHERE clause filters out rows where A.name is NULL, excluding unmatched rows from B. -> Option A

4. Quick Check:

   WHERE filters after join, can exclude NULLs [OK]

Hint: Use WHERE carefully; it filters after join, may exclude NULLs [OK]

Common Mistakes:

• Thinking FULL OUTER JOIN ignores WHERE filters
• Assuming ON clause filters rows after join
• Believing GROUP BY affects join row count

5. You have two tables:
Employees(emp_id, name) and Departments(dept_id, emp_id, dept_name).
You want a list of all employees and their departments if any, plus all departments and their employees if any.
Which query correctly uses FULL OUTER JOIN to achieve this?

hard

A. SELECT e.emp_id, e.name, d.dept_name FROM Employees e RIGHT JOIN Departments d ON e.emp_id = d.emp_id;

B. SELECT e.emp_id, e.name, d.dept_name FROM Employees e FULL OUTER JOIN Departments d ON e.emp_id = d.emp_id;

C. SELECT e.emp_id, e.name, d.dept_name FROM Employees e INNER JOIN Departments d ON e.emp_id = d.emp_id;

D. SELECT e.emp_id, e.name, d.dept_name FROM Employees e LEFT JOIN Departments d ON e.emp_id = d.emp_id;

Solution

1. Step 1: Understand the requirement

   We want all employees and their departments if any, plus all departments and their employees if any. This means all rows from both tables.

2. Step 2: Choose the correct join type

   FULL OUTER JOIN returns all rows from both tables, matching where possible. LEFT or RIGHT JOIN only return all rows from one table.

3. Final Answer:

   SELECT e.emp_id, e.name, d.dept_name FROM Employees e FULL OUTER JOIN Departments d ON e.emp_id = d.emp_id; -> Option B

4. Quick Check:

   FULL OUTER JOIN returns all rows both tables [OK]

Hint: Use FULL OUTER JOIN to include all rows from both tables [OK]

Common Mistakes:

• Using LEFT or RIGHT JOIN excludes unmatched rows from one table
• Using INNER JOIN excludes unmatched rows
• Forgetting ON condition