Multiple LEFT JOINs in one query in SQL - Time & Space Complexity

Time Complexity: Multiple LEFT JOINs in one query

O(n)

Understanding Time Complexity

When we use multiple LEFT JOINs in a SQL query, the database combines rows from several tables. We want to understand how the time to run this query grows as the tables get bigger.

How does adding more tables or more rows affect the work the database does?

Scenario Under Consideration

Analyze the time complexity of the following SQL query with multiple LEFT JOINs.

SELECT a.id, b.info, c.details
FROM tableA a
LEFT JOIN tableB b ON a.id = b.a_id
LEFT JOIN tableC c ON a.id = c.a_id;
    

This query selects data from tableA and adds matching rows from tableB and tableC if they exist.

Identify Repeating Operations

Look for repeated work the database does when joining tables.

• Primary operation: For each row in tableA, the database searches for matching rows in tableB and tableC.
• How many times: This happens once per row in tableA, and for each LEFT JOIN, it looks up matches in the other tables.

How Execution Grows With Input

As the number of rows in tableA grows, the database must do more lookups in tableB and tableC.

Input Size (rows in tableA)	Approx. Operations
10	About 10 lookups in tableB and 10 in tableC
100	About 100 lookups in tableB and 100 in tableC
1000	About 1000 lookups in tableB and 1000 in tableC

Pattern observation: The work grows roughly in direct proportion to the number of rows in the main table.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the query grows roughly in a straight line as the main table gets bigger.

Common Mistake

[X] Wrong: "Adding more LEFT JOINs multiplies the time by the size of all tables combined, making it exponential."

[OK] Correct: The database usually uses indexes to find matches quickly, so the time grows mostly with the size of the main table, not the product of all tables.

Interview Connect

Understanding how multiple LEFT JOINs affect query time helps you write efficient queries and explain your reasoning clearly in interviews. It shows you know how databases handle combining data from many tables.

Self-Check

What if we changed the LEFT JOINs to INNER JOINs? How would the time complexity change?