LEFT JOIN in MySQL - Time & Space Complexity

Time Complexity: LEFT JOIN

O(n * m)

Understanding Time Complexity

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

We want to know how the number of rows in each table affects the work the database does.

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;
    

This query returns all rows from tableA and matches rows from tableB where the IDs match.

Identify Repeating Operations

Look at what repeats as the query runs:

• 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. For each row in tableA, it searches tableB for matches.

Input Size (rows in tableA)	Approx. Operations
10	About 10 searches in tableB
100	About 100 searches in tableB
1000	About 1000 searches in tableB

Pattern observation: The work grows roughly in direct proportion to the size of tableA.

Final Time Complexity

Time Complexity: O(n * m)

This means the work grows roughly by multiplying the number of rows in tableA (n) by the number of rows in tableB (m).

Common Mistake

[X] Wrong: "LEFT JOIN only depends on the size of the first table, so it's always fast if the first table is small."

[OK] Correct: Even if the first table is small, the database must still search the second table for each row, so the second table's size also affects the time.

Interview Connect

Understanding how LEFT JOIN scales helps you explain query performance clearly and shows you can think about how databases handle data behind the scenes.

Self-Check

What if we added an index on the join column in tableB? How would the time complexity change?

Practice

1. What does a LEFT JOIN do in SQL?

easy

A. Deletes rows from the left table that do not have matches in the right table.

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

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

D. Returns all rows from the left table and matching rows from the right table, NULL if no match.

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: Check what happens with unmatched rows

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

3. Final Answer:

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

4. Quick Check:

   LEFT JOIN = all left rows + matched right rows [OK]

Hint: LEFT JOIN keeps all left rows, fills right with NULL if no match [OK]

Common Mistakes:

• Confusing LEFT JOIN with INNER JOIN
• Thinking it returns all right table rows
• Assuming unmatched rows are dropped

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

easy

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

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

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

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

Solution

1. Step 1: Review standard LEFT JOIN syntax

   The correct syntax uses LEFT JOIN followed by ON condition to specify matching columns.

2. Step 2: Check each option

   SELECT * FROM table1 LEFT JOIN table2 ON table1.id = table2.id; uses correct syntax: LEFT JOIN with ON clause. 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; uses WHERE instead of ON, which is incorrect for JOIN condition. SELECT * FROM table1 LEFT JOIN table2 WHERE table1.id = table2.id; uses WHERE instead of ON, invalid syntax.

3. Final Answer:

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

4. Quick Check:

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

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

Common Mistakes:

• Using JOIN LEFT instead of LEFT JOIN
• Using WHERE instead of ON for join condition
• Putting join condition directly in WHERE after table

3. Given these tables:

Employees(id, name)
Departments(id, dept_name, emp_id)

What is the output of this query?

SELECT e.name, d.dept_name FROM Employees e LEFT JOIN Departments d ON e.id = d.emp_id ORDER BY e.id;

Assuming:
Employees: (1, 'Alice'), (2, 'Bob'), (3, 'Carol')
Departments: (10, 'HR', 1), (20, 'IT', 3)

medium

A. [('Alice', NULL), ('Bob', NULL), ('Carol', NULL)]

B. [('Alice', 'HR'), ('Bob', 'IT'), ('Carol', NULL)]

C. [('Alice', 'HR'), ('Bob', NULL), ('Carol', 'IT')]

D. [('Alice', 'HR'), ('Carol', 'IT')]

Solution

1. Step 1: Match Employees with Departments using LEFT JOIN

   LEFT JOIN keeps all Employees. For each employee, it tries to find a matching department where e.id = d.emp_id.

2. Step 2: Check matches and NULLs

   'Alice' (id=1) matches department 'HR' (emp_id=1). 'Bob' (id=2) has no matching department, so dept_name is NULL. 'Carol' (id=3) matches 'IT' (emp_id=3).

3. Final Answer:

   [('Alice', 'HR'), ('Bob', NULL), ('Carol', 'IT')] -> Option C

4. Quick Check:

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

Hint: LEFT JOIN shows all left rows; unmatched right columns are NULL [OK]

Common Mistakes:

• Assuming unmatched rows are dropped
• Mixing up emp_id and id columns
• Ignoring ORDER BY effect

4. Identify the error in this LEFT JOIN query:

SELECT a.id, b.value FROM tableA a LEFT JOIN tableB b ON a.id = b.id WHERE b.value > 10;

medium

A. The WHERE clause filters out rows where b.value is NULL, defeating LEFT JOIN purpose.

B. The ON clause is missing a join condition.

C. LEFT JOIN should be replaced with INNER JOIN for this query.

D. The SELECT statement is missing table aliases.

Solution

1. Step 1: Understand effect of WHERE on LEFT JOIN

   LEFT JOIN keeps all rows from tableA, but WHERE b.value > 10 excludes rows where b.value is NULL (no match), effectively turning it into INNER JOIN.

2. Step 2: Identify the error

   The error is using WHERE to filter on right table columns after LEFT JOIN, which removes unmatched rows.

3. Final Answer:

   The WHERE clause filters out rows where b.value is NULL, defeating LEFT JOIN purpose. -> Option A

4. Quick Check:

   WHERE on right table column after LEFT JOIN removes unmatched rows [OK]

Hint: Use ON for filtering right table, not WHERE, to keep unmatched rows [OK]

Common Mistakes:

• Using WHERE instead of ON for right table filters
• Confusing LEFT JOIN with INNER JOIN
• Ignoring NULLs in join columns

5. You have two tables:

Products(product_id, name)
Sales(sale_id, product_id, quantity)

You want to list all products with total quantity sold, including products with zero sales.
Which query correctly uses LEFT JOIN to achieve this?

hard

A. SELECT p.name, SUM(s.quantity) FROM Products p INNER JOIN Sales s ON p.product_id = s.product_id GROUP BY p.product_id;

B. SELECT p.name, SUM(s.quantity) FROM Products p LEFT JOIN Sales s ON p.product_id = s.product_id GROUP BY p.product_id;

C. SELECT p.name, SUM(s.quantity) FROM Sales s LEFT JOIN Products p ON p.product_id = s.product_id GROUP BY p.product_id;

D. SELECT p.name, COUNT(s.sale_id) FROM Products p LEFT JOIN Sales s ON p.product_id = s.product_id WHERE s.quantity > 0 GROUP BY p.product_id;

Solution

1. Step 1: Use LEFT JOIN from Products to Sales

   To include all products even with no sales, LEFT JOIN Sales to Products on product_id.

2. Step 2: Aggregate sales quantity and group by product

   Use SUM(s.quantity) to total sales per product. Group by p.product_id to get one row per product.

3. Final Answer:

   SELECT p.name, SUM(s.quantity) FROM Products p LEFT JOIN Sales s ON p.product_id = s.product_id GROUP BY p.product_id; -> Option B

4. Quick Check:

   LEFT JOIN + SUM + GROUP BY lists all products with total sales [OK]

Hint: LEFT JOIN products to sales, SUM quantity, GROUP BY product [OK]

Common Mistakes:

• Using INNER JOIN excludes products with zero sales
• Joining Sales to Products reverses LEFT JOIN logic
• Filtering in WHERE removes unmatched rows