LEFT JOIN preserving all left rows in SQL - Time & Space Complexity

Time Complexity: LEFT JOIN preserving all left rows

O(n)

Understanding Time Complexity

When using a LEFT JOIN in SQL, we want to keep all rows from the left table, even if there is no matching row in the right table.

We ask: How does the time to run this query grow as the tables get bigger?

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, keeping all customers even if they have no orders.

Identify Repeating Operations

Look for repeated work done by the database engine.

• Primary operation: For each row in the left table (customers), the database looks for matching rows in the right table (orders).
• How many times: This matching happens once per left table row, 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 in orders.

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)

This means the time to run the query grows linearly with the number of rows in the left table.

Common Mistake

[X] Wrong: "The LEFT JOIN will check every row in both tables against each other, so it's quadratic time."

[OK] Correct: The database uses indexes or efficient lookups on the join column, so it doesn't scan the entire right table for each left row.

Interview Connect

Understanding how LEFT JOIN scales helps you explain query performance clearly and shows you know how databases handle joins efficiently.

Self-Check

"What if the right table has no index on the join column? How would the time complexity change?"