FULL OUTER JOIN behavior in SQL - Time & Space Complexity

Time Complexity: FULL OUTER JOIN behavior

O(n * m)

Understanding Time Complexity

When using FULL OUTER JOIN, we combine rows from two tables, including all matches and unmatched rows from both sides.

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

Scenario Under Consideration

Analyze the time complexity of the following SQL query.

SELECT A.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 IDs are equal, and including unmatched rows with NULLs.

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 against rows in TableB to find matching IDs.

How Execution Grows With Input

As the number of rows in both tables grows, the comparisons increase.

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 quickly, roughly multiplying as the product of the two table 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 by the number in the second.

Common Mistake

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

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

Interview Connect

Understanding how joins scale helps you explain query performance clearly and shows you know how databases handle data combinations.

Self-Check

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

Practice

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

easy

A. Returns all rows from the left table and matching rows from the right table.

B. Returns only rows that have matching values in both tables.

C. Returns all rows from both tables, matching where possible and NULLs where no match exists.

D. Returns all rows from the right table and matching rows from the left table.

Solution

1. Step 1: Understand join types

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

2. Step 2: Define FULL OUTER JOIN behavior

   FULL OUTER JOIN returns all rows from both tables, matching where possible, and fills NULLs where no match exists.

3. Final Answer:

   Returns all rows from both tables, matching where possible and NULLs where no match exists. -> Option C

4. Quick Check:

   FULL OUTER JOIN = all rows both tables [OK]

Hint: Full outer join keeps all rows from both tables [OK]

Common Mistakes:

• Confusing FULL OUTER JOIN with INNER JOIN
• Thinking FULL OUTER JOIN returns only matches
• Mixing up LEFT and RIGHT JOIN behavior

2. Which of the following is the correct syntax for a FULL OUTER JOIN between tables Employees and Departments on DeptID?

easy

A. SELECT * FROM Employees FULL OUTER JOIN Departments ON Employees.DeptID = Departments.DeptID;

B. SELECT * FROM Employees INNER JOIN Departments ON Employees.DeptID = Departments.DeptID;

C. SELECT * FROM Employees LEFT JOIN Departments ON Employees.DeptID = Departments.DeptID;

D. SELECT * FROM Employees RIGHT JOIN Departments ON Employees.DeptID = Departments.DeptID;

Solution

1. Step 1: Identify FULL OUTER JOIN syntax

   The correct syntax uses the keywords FULL OUTER JOIN between the two tables with an ON condition.

2. Step 2: Compare options

   SELECT * FROM Employees FULL OUTER JOIN Departments ON Employees.DeptID = Departments.DeptID; uses FULL OUTER JOIN correctly; others use INNER, LEFT, or RIGHT JOIN which are different join types.

3. Final Answer:

   SELECT * FROM Employees FULL OUTER JOIN Departments ON Employees.DeptID = Departments.DeptID; -> Option A

4. Quick Check:

   FULL OUTER JOIN syntax = SELECT * FROM Employees FULL OUTER JOIN Departments ON Employees.DeptID = Departments.DeptID; [OK]

Hint: FULL OUTER JOIN syntax includes FULL OUTER JOIN keywords [OK]

Common Mistakes:

• Using INNER JOIN instead of FULL OUTER JOIN
• Omitting FULL keyword and writing only OUTER JOIN
• Confusing LEFT or RIGHT JOIN with FULL OUTER JOIN

3. Given these tables:

Table A:
ID | Name
1 | Alice
2 | Bob
4 | Dana

Table B:
ID | City
2 | Boston
3 | Chicago
4 | Denver

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;

medium

A. [ (1, 'Alice', NULL), (2, 'Bob', NULL), (3, NULL, 'Chicago'), (4, 'Dana', NULL) ]

B. [ (2, 'Bob', 'Boston'), (4, 'Dana', 'Denver') ]

C. [ (1, 'Alice', 'Boston'), (2, 'Bob', 'Chicago'), (3, NULL, 'Denver'), (4, 'Dana', NULL) ]

D. [ (1, 'Alice', NULL), (2, 'Bob', 'Boston'), (4, 'Dana', 'Denver'), (NULL, NULL, 'Chicago') ]

Solution

1. Step 1: Match rows by ID using FULL OUTER JOIN

   IDs 2 and 4 appear in both tables, so their rows combine. ID 1 is only in A, ID 3 only in B.

2. Step 2: Fill NULLs for missing matches

   For ID 1 (A only), City is NULL; for ID 3 (B only), A.ID=NULL, A.Name=NULL, City='Chicago'. ORDER BY A.ID ASC places NULL last: rows for 1,2,4 then NULL row.

3. Final Answer:

   [ (1, 'Alice', NULL), (2, 'Bob', 'Boston'), (4, 'Dana', 'Denver'), (NULL, NULL, 'Chicago') ] -> Option D

4. Quick Check:

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

Hint: FULL OUTER JOIN shows all rows, NULLs where no match [OK]

Common Mistakes:

• Ignoring unmatched rows from either table
• Assuming INNER JOIN behavior returns only matches
• Misordering results by A.ID when NULLs exist

4. Consider this query:

SELECT * FROM Customers FULL OUTER JOIN Orders ON Customers.CustomerID = Orders.CustomerID WHERE Orders.OrderID IS NULL;

What is the likely purpose of this query?

medium

A. To find orders without customers.

B. To find customers who have no orders.

C. To find all customers and orders regardless of match.

D. To find customers with at least one order.

Solution

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

   The join returns all customers and orders; filtering WHERE Orders.OrderID IS NULL keeps rows where no matching order exists.

2. Step 2: Interpret the filter effect

   Rows with NULL in Orders.OrderID mean customers without orders are selected.

3. Final Answer:

   To find customers who have no orders. -> Option B

4. Quick Check:

   Filter NULL in Orders = customers without orders [OK]

Hint: Filter NULL in joined table to find unmatched rows [OK]

Common Mistakes:

• Thinking it finds orders without customers
• Assuming it returns all rows without filtering
• Confusing NULL filter with matching rows

5. You have two tables:

Products:
ProductID | Name
1 | Pen
2 | Pencil
3 | Eraser

Sales:
ProductID | Quantity
2 | 100
3 | 50
4 | 10

You want a query to list all products and sales quantities, including products with no sales and sales for unknown products.

Which query correctly achieves this?

hard

A. SELECT Products.ProductID, Products.Name, Sales.Quantity FROM Products FULL OUTER JOIN Sales ON Products.ProductID = Sales.ProductID;

B. SELECT Products.ProductID, Products.Name, Sales.Quantity FROM Products LEFT JOIN Sales ON Products.ProductID = Sales.ProductID;

C. SELECT Products.ProductID, Products.Name, Sales.Quantity FROM Sales RIGHT JOIN Products ON Sales.ProductID = Products.ProductID;

D. SELECT Products.ProductID, Products.Name, Sales.Quantity FROM Products INNER JOIN Sales ON Products.ProductID = Sales.ProductID;

Solution

1. Step 1: Identify requirement for all products and all sales

   We want all products even if no sales, and all sales even if product unknown.

2. Step 2: Choose join type

   FULL OUTER JOIN returns all rows from both tables, matching where possible, filling NULLs otherwise.

3. Step 3: Check options

   SELECT Products.ProductID, Products.Name, Sales.Quantity FROM Products FULL OUTER JOIN Sales ON Products.ProductID = Sales.ProductID; uses FULL OUTER JOIN correctly; others exclude unmatched rows from one side.

4. Final Answer:

   SELECT Products.ProductID, Products.Name, Sales.Quantity FROM Products FULL OUTER JOIN Sales ON Products.ProductID = Sales.ProductID; -> Option A

5. Quick Check:

   FULL OUTER JOIN = all products and sales [OK]

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

Common Mistakes:

• Using LEFT JOIN excludes sales without products
• Using INNER JOIN excludes unmatched rows
• Confusing RIGHT JOIN direction with LEFT JOIN