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