Time Complexity: FULL OUTER JOIN availability across databases
O(n * m)
0
0
FULL OUTER JOIN availability across databases in SQL - Time & Space Complexity
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?"