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

Practice

1. What does a LEFT JOIN do in SQL?

easy

A. Returns all rows from the left table and matched rows from the right table, NULL if no match.

B. Returns only rows that have matching values in both tables.

C. Returns all rows from the right table and matched rows from the left table.

D. Deletes rows from the left table that have no match in the right table.

Solution

1. Step 1: Understand LEFT JOIN behavior

   A LEFT JOIN keeps all rows from the left table regardless of matches in the right table.

2. Step 2: Identify NULLs for unmatched rows

   If there is no matching row in the right table, the result shows NULL for right table columns.

3. Final Answer:

   Returns all rows from the left table and matched rows from the right table, NULL if no match. -> Option A

4. Quick Check:

   LEFT JOIN = all left rows + NULL for no match [OK]

Hint: LEFT JOIN keeps all left rows, unmatched right rows show NULL [OK]

Common Mistakes:

• Confusing LEFT JOIN with INNER JOIN
• Thinking unmatched rows are dropped
• Assuming NULLs appear in left table columns

2. Which of the following is the correct syntax for a LEFT JOIN in SQL?

easy

A. SELECT * FROM table1 LEFT OUTER JOIN table2 WHERE table1.id = table2.id;

B. SELECT * FROM table1 JOIN LEFT table2 ON table1.id = table2.id;

C. SELECT * FROM table1 LEFT JOIN table2 USING (id);

D. SELECT * FROM table1 LEFT JOIN table2 ON table1.id = table2.id;

Solution

1. Step 1: Review standard LEFT JOIN syntax

   The correct syntax is: SELECT columns FROM left_table LEFT JOIN right_table ON condition.

2. Step 2: Check each option

   SELECT * FROM table1 LEFT JOIN table2 ON table1.id = table2.id; matches the correct syntax exactly. SELECT * FROM table1 JOIN LEFT table2 ON table1.id = table2.id; has JOIN LEFT which is invalid. SELECT * FROM table1 LEFT OUTER JOIN table2 WHERE table1.id = table2.id; is invalid because JOIN requires an ON clause (syntax error). SELECT * FROM table1 LEFT JOIN table2 USING (id); is correct syntax with parentheses.

3. Final Answer:

   SELECT * FROM table1 LEFT JOIN table2 ON table1.id = table2.id; -> Option D

4. Quick Check:

   LEFT JOIN syntax = LEFT JOIN ... ON ... [OK]

Hint: Use LEFT JOIN ... ON ... for correct syntax [OK]

Common Mistakes:

• Swapping JOIN and LEFT keywords
• Using WHERE instead of ON for join condition
• Omitting parentheses in USING clause

3. Given tables Employees and Departments with data:

Employees:
id | name | dept_id
1 | Alice | 10
2 | Bob | 20
3 | Carol | NULL

Departments:
dept_id | dept_name
10 | Sales
20 | HR
30 | IT

What is the result of this query?

SELECT e.name, d.dept_name FROM Employees e LEFT JOIN Departments d ON e.dept_id = d.dept_id;

medium

A. [{"name": "Alice", "dept_name": "Sales"}, {"name": "Bob", "dept_name": "HR"}]

B. [{"name": "Alice", "dept_name": "Sales"}, {"name": "Bob", "dept_name": "HR"}, {"name": "Carol", "dept_name": null}]

C. [{"name": "Alice", "dept_name": "Sales"}, {"name": "Bob", "dept_name": "HR"}, {"name": "Carol", "dept_name": "IT"}]

D. [{"name": "Alice", "dept_name": null}, {"name": "Bob", "dept_name": null}, {"name": "Carol", "dept_name": null}]

Solution

1. Step 1: Match Employees with Departments by dept_id

   Alice's dept_id 10 matches Sales, Bob's 20 matches HR, Carol's NULL has no match.

2. Step 2: Apply LEFT JOIN behavior

   All employees appear. For Carol, no matching department, so dept_name is NULL.

3. Final Answer:

   [{"name": "Alice", "dept_name": "Sales"}, {"name": "Bob", "dept_name": "HR"}, {"name": "Carol", "dept_name": null}] -> Option B

4. Quick Check:

   LEFT JOIN keeps all left rows, unmatched right columns NULL [OK]

Hint: LEFT JOIN shows NULL for unmatched right table rows [OK]

Common Mistakes:

• Omitting rows with NULL join keys
• Assuming unmatched rows get default values
• Confusing INNER JOIN output with LEFT JOIN

4. Consider this SQL query:

SELECT a.id, b.value FROM A a LEFT JOIN B b ON a.id = b.a_id WHERE b.value > 10;

Why might this query return fewer rows than table A has?

medium

A. Because the query syntax is invalid and causes an error.

B. Because LEFT JOIN only returns rows with matching b.value > 10.

C. Because the WHERE clause filters out rows where b.value is NULL, removing unmatched rows.

D. Because the ON condition is incorrect and causes no matches.

Solution

1. Step 1: Understand LEFT JOIN with WHERE filter

   LEFT JOIN keeps all rows from A, but WHERE filters after join.

2. Step 2: Effect of WHERE on NULLs from unmatched rows

   Rows with no match have b.value as NULL, and WHERE b.value > 10 excludes NULLs, removing those rows.

3. Final Answer:

   Because the WHERE clause filters out rows where b.value is NULL, removing unmatched rows. -> Option C

4. Quick Check:

   WHERE filters NULLs after LEFT JOIN, reducing rows [OK]

Hint: WHERE on right table column after LEFT JOIN filters out NULLs [OK]

Common Mistakes:

• Thinking LEFT JOIN always keeps all left rows regardless of WHERE
• Confusing ON and WHERE filtering effects
• Assuming query syntax error causes fewer rows

5. You have two tables:

Orders:
order_id | customer_id
1 | 101
2 | 102
3 | 103

Customers:
customer_id | name
101 | John
102 | Jane

You want to list all orders with customer names, but show 'Unknown' if no customer found.

Which SQL query correctly achieves this?

hard

A. SELECT o.order_id, COALESCE(c.name, 'Unknown') AS customer_name FROM Orders o LEFT JOIN Customers c ON o.customer_id = c.customer_id;

B. SELECT o.order_id, IFNULL(c.name, 'Unknown') AS customer_name FROM Orders o INNER JOIN Customers c ON o.customer_id = c.customer_id;

C. SELECT o.order_id, c.name FROM Orders o RIGHT JOIN Customers c ON o.customer_id = c.customer_id;

D. SELECT o.order_id, CASE WHEN c.name IS NULL THEN 'Unknown' ELSE c.name END FROM Orders o JOIN Customers c ON o.customer_id = c.customer_id;

Solution

1. Step 1: Use LEFT JOIN to keep all orders

   LEFT JOIN keeps all orders even if no matching customer exists.

2. Step 2: Replace NULL customer names with 'Unknown'

   Use COALESCE to show 'Unknown' when c.name is NULL.

3. Final Answer:

   SELECT o.order_id, COALESCE(c.name, 'Unknown') AS customer_name FROM Orders o LEFT JOIN Customers c ON o.customer_id = c.customer_id; -> Option A

4. Quick Check:

   LEFT JOIN + COALESCE handles missing customers [OK]

Hint: Use LEFT JOIN with COALESCE to replace NULLs [OK]

Common Mistakes:

• Using INNER JOIN excludes orders without customers
• Using RIGHT JOIN reverses table roles incorrectly
• Forgetting to handle NULL customer names