FULL OUTER JOIN availability across databases in SQL - Time & Space Complexity

Time Complexity: FULL OUTER JOIN availability across databases

O(n * m)

Understanding Time Complexity

We want to understand how the time it takes to run a FULL OUTER JOIN changes as the size of the tables grows.

How does the database handle joining all rows from two tables, even when some rows don't match?

Scenario Under Consideration

Analyze the time complexity of the following SQL query using FULL OUTER JOIN.

SELECT a.id, a.value, b.id, b.value
FROM TableA a
FULL OUTER JOIN TableB b
ON a.id = b.id;
    

This query returns all rows from both tables, matching rows where possible, and filling with NULLs where no match exists.

Identify Repeating Operations

Look for repeated work done by the database engine.

• Primary operation: Comparing rows from TableA and TableB to find matches.
• How many times: Each row in TableA is compared to rows in TableB, and vice versa, depending on join method.

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 roughly with the product of the sizes of the two tables.

Final Time Complexity

Time Complexity: O(n * m)

This means the time to run the FULL OUTER JOIN grows roughly with the number of rows in both tables multiplied together.

Common Mistake

[X] Wrong: "FULL OUTER JOIN runs as fast as INNER JOIN because it's just joining tables."

[OK] Correct: FULL OUTER JOIN must include all rows from both tables, even unmatched ones, so it often requires more work than INNER JOIN.

Interview Connect

Understanding how joins scale helps you explain database performance clearly and shows you know how data size affects query speed.

Self-Check

"What if we replaced FULL OUTER JOIN with LEFT JOIN? How would the time complexity change?"

Practice

1. Which of the following SQL databases natively supports the FULL OUTER JOIN clause?

easy

A. PostgreSQL

B. MySQL (before version 8.0)

C. SQLite

D. MariaDB (before version 10.2)

Solution

1. Step 1: Understand FULL OUTER JOIN support in popular databases

   PostgreSQL supports FULL OUTER JOIN natively, allowing retrieval of all matching and non-matching rows from both tables.

2. Step 2: Check other databases' support

   MySQL before 8.0 and SQLite do not support FULL OUTER JOIN natively; MariaDB added support only after version 10.2.

3. Final Answer:

   PostgreSQL -> Option A

4. Quick Check:

   PostgreSQL supports FULL OUTER JOIN [OK]

Hint: Remember PostgreSQL supports FULL OUTER JOIN natively [OK]

Common Mistakes:

• Assuming MySQL supports FULL OUTER JOIN before version 8.0
• Thinking SQLite supports FULL OUTER JOIN
• Confusing MariaDB versions for FULL OUTER JOIN support

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

easy

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

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

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

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

Solution

1. Step 1: Identify correct FULL OUTER JOIN syntax

   The correct syntax uses FULL OUTER JOIN with an ON clause to specify join condition.

2. Step 2: Analyze incorrect options

   SELECT * FROM table1 INNER FULL JOIN table2 ON table1.id = table2.id; uses invalid keyword INNER FULL JOIN, SELECT * FROM table1 FULL JOIN table2 WHERE table1.id = table2.id; misplaces join condition in WHERE, SELECT * FROM table1 OUTER JOIN table2 ON table1.id = table2.id; uses incomplete OUTER JOIN without FULL.

3. Final Answer:

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

4. Quick Check:

   FULL OUTER JOIN syntax = SELECT * FROM table1 FULL OUTER JOIN table2 ON table1.id = table2.id; [OK]

Hint: FULL OUTER JOIN requires ON clause, no INNER keyword [OK]

Common Mistakes:

• Using INNER FULL JOIN instead of FULL OUTER JOIN
• Placing join condition in WHERE instead of ON
• Omitting FULL keyword before OUTER JOIN

3. Given two tables:
Table A: id, name
Table B: id, city
With data:
Table A: (1, 'Alice'), (2, 'Bob')
Table B: (2, 'Paris'), (3, 'London')
What is the result of this query?

SELECT A.id, A.name, B.city FROM A FULL OUTER JOIN B ON A.id = B.id ORDER BY A.id, B.id;

medium

A. (1, 'Alice', NULL), (2, 'Bob', NULL)

B. (1, 'Alice', 'Paris'), (2, 'Bob', 'Paris'), (3, NULL, 'London')

C. (2, 'Bob', 'Paris')

D. (1, 'Alice', NULL), (2, 'Bob', 'Paris'), (3, NULL, 'London')

Solution

1. Step 1: Understand FULL OUTER JOIN behavior

   It returns all rows from both tables, matching rows where possible, NULL where no match.

2. Step 2: Match rows by id and fill NULLs

   id=1 only in A, so city NULL; id=2 in both, so matched; id=3 only in B, so name NULL.

3. Final Answer:

   (1, 'Alice', NULL), (2, 'Bob', 'Paris'), (3, NULL, 'London') -> Option D

4. Quick Check:

   FULL OUTER JOIN returns all rows with NULLs for missing matches [OK]

Hint: FULL OUTER JOIN keeps all rows, fills NULLs for no match [OK]

Common Mistakes:

• Expecting only matched rows like INNER JOIN
• Confusing NULL placement for unmatched rows
• Ignoring rows unique to one table

4. You run this query on MySQL 5.7:

SELECT * FROM employees FULL OUTER JOIN departments ON employees.dept_id = departments.id;

It returns a syntax error. What is the best fix?

medium

A. Upgrade MySQL to version 8.0 or higher

B. Replace FULL OUTER JOIN with LEFT JOIN and UNION with RIGHT JOIN

C. Use CROSS JOIN instead of FULL OUTER JOIN

D. Add parentheses around the JOIN clause

Solution

1. Step 1: Identify MySQL 5.7 limitation

   MySQL 5.7 does not support FULL OUTER JOIN syntax, causing syntax error.

2. Step 2: Use workaround with LEFT JOIN and RIGHT JOIN UNION

   Combine LEFT JOIN and RIGHT JOIN with UNION to simulate FULL OUTER JOIN in MySQL 5.7.

3. Final Answer:

   Replace FULL OUTER JOIN with LEFT JOIN and UNION with RIGHT JOIN -> Option B

4. Quick Check:

   MySQL 5.7 needs LEFT JOIN + RIGHT JOIN UNION for FULL OUTER JOIN [OK]

Hint: MySQL < 8.0 lacks FULL OUTER JOIN; use LEFT + RIGHT JOIN UNION [OK]

Common Mistakes:

• Trying to use FULL OUTER JOIN directly in MySQL 5.7
• Using CROSS JOIN which returns Cartesian product
• Thinking parentheses fix syntax error

5. You want to write a query that returns all customers and all orders, matching by customer_id, but your database is SQLite which does not support FULL OUTER JOIN. Which approach correctly simulates FULL OUTER JOIN?

hard

A. Use CROSS JOIN and filter rows where customer_id matches

B. Use INNER JOIN customers to orders and add WHERE clause for unmatched rows

C. Use LEFT JOIN customers to orders UNION ALL RIGHT JOIN orders to customers with filtering duplicates

D. Use LEFT JOIN only from customers to orders

Solution

1. Step 1: Recognize SQLite limitation

   SQLite does not support FULL OUTER JOIN, so we must simulate it.

2. Step 2: Simulate FULL OUTER JOIN with UNION of LEFT and RIGHT JOIN

   Use LEFT JOIN customers to orders plus UNION ALL with RIGHT JOIN orders to customers (emulated by LEFT JOIN orders to customers) filtering duplicates to get all rows.

3. Final Answer:

   Use LEFT JOIN customers to orders UNION ALL RIGHT JOIN orders to customers with filtering duplicates -> Option C

4. Quick Check:

   Simulate FULL OUTER JOIN with LEFT + RIGHT JOIN UNION [OK]

Hint: Simulate FULL OUTER JOIN with LEFT JOIN UNION RIGHT JOIN [OK]

Common Mistakes:

• Using INNER JOIN which excludes unmatched rows
• Using CROSS JOIN which creates all combinations
• Using only LEFT JOIN missing unmatched rows from right table