LEFT JOIN with NULL result rows in SQL - Time & Space Complexity

Time Complexity: LEFT JOIN with NULL result rows

O(n)

Understanding Time Complexity

When using a LEFT JOIN in SQL, it is important to understand how the query's work grows as the tables get bigger.

We want to know how the time to run the query changes when the input tables have more rows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT a.id, b.value
FROM tableA a
LEFT JOIN tableB b ON a.id = b.a_id
WHERE b.value IS NULL;

This query finds all rows in tableA that do not have matching rows in tableB.

Identify Repeating Operations

• Primary operation: For each row in tableA, the database looks for matching rows in tableB.
• How many times: This matching happens once per row in tableA.

How Execution Grows With Input

As tableA grows, the number of lookups into tableB grows proportionally.

Input Size (n)	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 directly with the number of rows in tableA.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the query grows roughly in direct proportion to the size of tableA.

Common Mistake

[X] Wrong: "The LEFT JOIN will take time proportional to the product of both tables' sizes because it compares every row to every other row."

[OK] Correct: The database uses indexes or efficient lookups, so it does not check every pair. It mainly scans tableA and looks up matches in tableB, not all combinations.

Interview Connect

Understanding how JOINs scale helps you write queries that run well on large data. This skill shows you can think about performance, not just correctness.

Self-Check

"What if we changed the LEFT JOIN to an INNER JOIN? How would the time complexity change?"