Finding unmatched rows with LEFT JOIN in SQL - Time & Space Complexity

Time Complexity: Finding unmatched rows with LEFT JOIN

O(n)

Understanding Time Complexity

When we use a LEFT JOIN to find rows in one table that don't have matches in another, we want to know how the work grows as the tables get bigger.

How does the number of rows affect the time it takes to find unmatched rows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT a.id
FROM TableA a
LEFT JOIN TableB b ON a.id = b.a_id
WHERE b.a_id IS NULL;
    

This query finds all rows in TableA that do not have a matching row in TableB.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: For each row in TableA, the database looks for matching rows in TableB.
• How many times: This happens once for every row in TableA.

How Execution Grows With Input

As TableA grows, the database must check more rows to find unmatched ones.

Input Size (rows in TableA)	Approx. Operations
10	About 10 lookups in TableB
100	About 100 lookups in TableB
1000	About 1000 lookups in TableB

Pattern observation: The work grows roughly in direct proportion to the number of rows in TableA.

Final Time Complexity

Time Complexity: O(n)

This means the time to find unmatched rows grows linearly with the number of rows in the first table.

Common Mistake

[X] Wrong: "The LEFT JOIN will check every combination of rows in both tables, so it's much slower than it really is."

[OK] Correct: The database uses indexes or efficient search methods to avoid checking every pair, so it doesn't do a full cross-check of all rows.

Interview Connect

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

Self-Check

"What if we added an index on TableB.a_id? How would the time complexity change?"