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?"