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