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?