LEFT JOIN execution behavior in SQL - Time & Space Complexity

Time Complexity: LEFT JOIN execution behavior

O(n * m)

Understanding Time Complexity

We want to understand how the time to run a LEFT JOIN query changes as the data grows.

Specifically, how does the database handle matching rows from two tables?

Scenario Under Consideration

Analyze the time complexity of the following SQL LEFT JOIN query.

SELECT a.id, a.name, b.order_date
FROM customers a
LEFT JOIN orders b ON a.id = b.customer_id;
    

This query returns all customers and their orders if any, matching by customer ID.

Identify Repeating Operations

Look for repeated work done by the database to join tables.

• Primary operation: For each row in the customers table, the database looks for matching rows in the orders table.
• How many times: This happens once per customer, so as many times as there are customers.

How Execution Grows With Input

As the number of customers grows, the database must check more rows to find matches.

Input Size (customers)	Approx. Operations
10	About 10 lookups in orders
100	About 100 lookups in orders
1000	About 1000 lookups in orders

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

Final Time Complexity

Time Complexity: O(n * m)

This means the time to run the LEFT JOIN grows proportionally to the product of the number of rows in both tables if no indexes are used.

Common Mistake

[X] Wrong: "LEFT JOIN always takes the same time no matter how big the tables are."

[OK] Correct: The database must check each row in the first table and find matches in the second, so more rows means more work.

Interview Connect

Understanding how joins scale helps you explain query performance clearly and shows you know how databases work under the hood.

Self-Check

"What if we added an index on the orders.customer_id column? How would that affect the time complexity?"

Practice

1. What does a LEFT JOIN do in SQL?

easy

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

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

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

D. Returns rows only from the left table without any matching

Solution

1. Step 1: Understand LEFT JOIN behavior

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

2. Step 2: Check what happens when no match exists

   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 B

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 LEFT JOIN returns only matching rows
• Assuming NULLs never appear in results

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

easy

A. SELECT * FROM table1 LEFT 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 ON table1.id = table2.id;

D. SELECT * FROM table1 LEFT JOIN table2 USING id;

Solution

1. Step 1: Recall correct LEFT JOIN syntax

   The correct syntax uses LEFT JOIN followed by ON clause to specify join condition.

2. Step 2: Check each option

   SELECT * FROM table1 LEFT JOIN table2 ON table1.id = table2.id; uses correct syntax: LEFT JOIN with ON condition. SELECT * FROM table1 JOIN LEFT table2 ON table1.id = table2.id; has incorrect order. SELECT * FROM table1 LEFT JOIN table2 WHERE table1.id = table2.id; uses WHERE instead of ON. SELECT * FROM table1 LEFT JOIN table2 USING id; uses USING without parentheses, which is invalid syntax.

3. Final Answer:

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

4. Quick Check:

   LEFT JOIN ... ON condition is standard syntax [OK]

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

Common Mistakes:

• Using WHERE instead of ON for join condition
• Swapping JOIN and LEFT keywords
• Confusing USING with ON without proper column names

3. Given these tables:
Employees(id, name)
Departments(id, dept_name, manager_id)
What will this query return?

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

medium

A. All employees with their department names if they are managers, NULL otherwise

B. Only employees who are managers with their department names

C. All departments with their managers' names

D. Only departments with managers matching employee ids

Solution

1. Step 1: Analyze LEFT JOIN condition

   The query LEFT JOINs Employees (left) with Departments (right) on employee id matching department manager_id.

2. Step 2: Understand output rows

   All employees appear. If an employee is a manager (id matches manager_id), department name shows; else department columns are NULL.

3. Final Answer:

   All employees with their department names if they are managers, NULL otherwise -> Option A

4. Quick Check:

   LEFT JOIN keeps all employees, adds department if manager [OK]

Hint: LEFT JOIN keeps all left rows, adds right data if matched [OK]

Common Mistakes:

• Thinking only managers appear in result
• Confusing which table is left or right
• Expecting departments without managers to appear

4. Identify the error in this SQL query:

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

medium

A. The ON clause is missing a join condition

B. The SELECT clause must include all columns from both tables

C. LEFT JOIN should be INNER JOIN for this query

D. The WHERE clause filters out rows where b.value is NULL, negating LEFT JOIN effect

Solution

1. Step 1: Understand LEFT JOIN with WHERE filter

   The WHERE clause filters rows after join. Filtering on b.value > 10 excludes rows where b.value is NULL.

2. Step 2: Effect on LEFT JOIN

   This filtering removes rows without matches in B, making LEFT JOIN behave like INNER JOIN.

3. Final Answer:

   The WHERE clause filters out rows where b.value is NULL, negating LEFT JOIN effect -> Option D

4. Quick Check:

   Filtering on right table in WHERE breaks LEFT JOIN [OK]

Hint: Use ON for right table filters, not WHERE, to keep LEFT JOIN effect [OK]

Common Mistakes:

• Filtering right table columns in WHERE after LEFT JOIN
• Confusing ON and WHERE clauses
• Assuming LEFT JOIN always keeps all left rows regardless of WHERE

5. You want to list all customers and their last order date if any. Which query correctly uses LEFT JOIN to achieve this?

Customers(id, name)
Orders(id, customer_id, order_date)

hard

A. SELECT c.name, MAX(o.order_date) FROM Customers c LEFT JOIN Orders o ON c.id = o.customer_id GROUP BY c.name;

B. SELECT c.name, o.order_date FROM Customers c LEFT JOIN Orders o ON c.id = o.customer_id WHERE o.order_date = (SELECT MAX(order_date) FROM Orders);

C. SELECT c.name, o.order_date FROM Customers c INNER JOIN Orders o ON c.id = o.customer_id;

D. SELECT c.name, MAX(o.order_date) FROM Customers c INNER JOIN Orders o ON c.id = o.customer_id GROUP BY c.name;

Solution

1. Step 1: Understand requirement for all customers

   We want all customers listed, even those without orders, so LEFT JOIN is needed.

2. Step 2: Aggregate last order date per customer

   Using MAX(o.order_date) with GROUP BY c.name gives last order date or NULL if no orders.

3. Step 3: Check options

   SELECT c.name, MAX(o.order_date) FROM Customers c LEFT JOIN Orders o ON c.id = o.customer_id GROUP BY c.name; uses LEFT JOIN and GROUP BY correctly. SELECT c.name, o.order_date FROM Customers c LEFT JOIN Orders o ON c.id = o.customer_id WHERE o.order_date = (SELECT MAX(order_date) FROM Orders); filters in WHERE, excluding customers without orders. Options A and C use INNER JOIN, excluding customers without orders.

4. Final Answer:

   SELECT c.name, MAX(o.order_date) FROM Customers c LEFT JOIN Orders o ON c.id = o.customer_id GROUP BY c.name; -> Option A

5. Quick Check:

   LEFT JOIN + GROUP BY + MAX gets last order date including customers without orders [OK]

Hint: Use LEFT JOIN with GROUP BY and MAX to include all left rows [OK]

Common Mistakes:

• Using INNER JOIN excludes customers without orders
• Filtering right table in WHERE removes unmatched rows
• Not grouping when using aggregate functions