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

Practice

1. What does a LEFT JOIN combined with WHERE right_table.key IS NULL do in SQL?

easy

A. Finds rows in the right table that have no matching rows in the left table

B. Finds rows in the left table that have no matching rows in the right table

C. Returns all rows from both tables regardless of matches

D. Deletes unmatched rows from the left table

Solution

1. Step 1: Understand LEFT JOIN behavior

   A LEFT JOIN returns all rows from the left table and matching rows from the right table. If no match exists, right table columns are NULL.

2. Step 2: Apply WHERE condition to filter unmatched rows

   Filtering with WHERE right_table.key IS NULL selects only those left table rows without a match in the right table.

3. Final Answer:

   Finds rows in the left table that have no matching rows in the right table -> Option B

4. Quick Check:

   LEFT JOIN + IS NULL = unmatched left rows [OK]

Hint: LEFT JOIN + IS NULL filters unmatched left table rows [OK]

Common Mistakes:

• Confusing unmatched rows as from right table
• Using INNER JOIN instead of LEFT JOIN
• Not checking for NULL in right table columns

2. Which of the following SQL queries correctly finds customers without orders using LEFT JOIN?

easy

A. SELECT c.id FROM customers c RIGHT JOIN orders o ON c.id = o.customer_id WHERE c.id IS NULL;

B. SELECT c.id FROM customers c INNER JOIN orders o ON c.id = o.customer_id WHERE o.customer_id IS NULL;

C. SELECT c.id FROM customers c LEFT JOIN orders o ON c.id = o.customer_id WHERE c.id IS NULL;

D. SELECT c.id FROM customers c LEFT JOIN orders o ON c.id = o.customer_id WHERE o.customer_id IS NULL;

Solution

1. Step 1: Identify correct JOIN type

   LEFT JOIN keeps all customers and matches orders; unmatched orders will be NULL.

2. Step 2: Filter unmatched orders

   WHERE o.customer_id IS NULL selects customers without orders.

3. Final Answer:

   SELECT c.id FROM customers c LEFT JOIN orders o ON c.id = o.customer_id WHERE o.customer_id IS NULL; -> Option D

4. Quick Check:

   LEFT JOIN + right table NULL = unmatched left rows [OK]

Hint: Use LEFT JOIN and check right table key IS NULL [OK]

Common Mistakes:

• Using INNER JOIN which excludes unmatched rows
• Checking NULL on left table columns
• Using RIGHT JOIN incorrectly for this case

3. Given tables employees(id, name) and tasks(employee_id, task_name), what does this query return?

SELECT e.name FROM employees e LEFT JOIN tasks t ON e.id = t.employee_id WHERE t.employee_id IS NULL;

medium

A. Names of employees who have no tasks assigned

B. Names of employees who have at least one task

C. All employee names regardless of tasks

D. Names of tasks without employees

Solution

1. Step 1: Analyze LEFT JOIN and ON condition

   The query joins employees with tasks on employee ID, keeping all employees.

2. Step 2: Filter rows where tasks are missing

   WHERE t.employee_id IS NULL selects employees with no matching tasks.

3. Final Answer:

   Names of employees who have no tasks assigned -> Option A

4. Quick Check:

   LEFT JOIN + NULL in right table = unmatched left rows [OK]

Hint: LEFT JOIN + right key NULL = unmatched left rows [OK]

Common Mistakes:

• Thinking it returns employees with tasks
• Confusing NULL check on left table
• Assuming INNER JOIN behavior

4. Identify the error in this query intended to find products without sales:

SELECT p.product_id FROM products p LEFT JOIN sales s ON p.product_id = s.product_id WHERE p.product_id IS NULL;

medium

A. ON condition is incorrect, should join on sales_id

B. LEFT JOIN should be INNER JOIN

C. The WHERE clause should check s.product_id IS NULL, not p.product_id

D. Query is correct and will return unmatched products

Solution

1. Step 1: Understand LEFT JOIN result

   LEFT JOIN keeps all products; unmatched sales columns are NULL.

2. Step 2: Check WHERE clause correctness

   Filtering on p.product_id IS NULL is wrong because left table columns are never NULL in LEFT JOIN; should check s.product_id IS NULL.

3. Final Answer:

   The WHERE clause should check s.product_id IS NULL, not p.product_id -> Option C

4. Quick Check:

   Filter NULL on right table columns, not left [OK]

Hint: Check NULL on right table columns after LEFT JOIN [OK]

Common Mistakes:

• Checking NULL on left table columns
• Using INNER JOIN instead of LEFT JOIN
• Incorrect ON join condition

5. You have tables students(id, name) and enrollments(student_id, course_id). Write a query to find students not enrolled in any course, considering some students may have NULL IDs. Which query correctly handles this?

hard

A. SELECT s.name FROM students s LEFT JOIN enrollments e ON s.id = e.student_id WHERE e.student_id IS NULL AND s.id IS NOT NULL;

B. SELECT s.name FROM students s RIGHT JOIN enrollments e ON s.id = e.student_id WHERE s.id IS NULL;

C. SELECT s.name FROM students s INNER JOIN enrollments e ON s.id = e.student_id WHERE s.id IS NULL;

D. SELECT s.name FROM students s LEFT JOIN enrollments e ON s.id = e.student_id WHERE e.student_id IS NULL;

Solution

1. Step 1: Use LEFT JOIN to find unmatched students

   LEFT JOIN students with enrollments keeps all students; unmatched enrollments are NULL.

2. Step 2: Filter students without enrollments and exclude NULL student IDs

   WHERE e.student_id IS NULL finds students without courses; adding s.id IS NOT NULL excludes students with NULL IDs to avoid incorrect matches.

3. Final Answer:

   SELECT s.name FROM students s LEFT JOIN enrollments e ON s.id = e.student_id WHERE e.student_id IS NULL AND s.id IS NOT NULL; -> Option A

4. Quick Check:

   LEFT JOIN + right NULL + exclude NULL left keys = correct unmatched [OK]

Hint: Exclude NULL keys on left table when filtering unmatched [OK]

Common Mistakes:

• Ignoring NULL IDs in left table
• Using INNER JOIN which excludes unmatched rows
• Using RIGHT JOIN incorrectly