LEFT JOIN and RIGHT JOIN in PostgreSQL - Time & Space Complexity

Time Complexity: LEFT JOIN and RIGHT JOIN

O(n)

Understanding Time Complexity

When we use LEFT JOIN or RIGHT JOIN in SQL, the database combines rows from two tables based on a condition.

We want to understand how the time it takes grows as the tables get bigger.

Scenario Under Consideration

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

SELECT a.id, b.value
FROM table_a a
LEFT JOIN table_b b ON a.id = b.a_id;
    

This query returns all rows from table_a and matches rows from table_b where the id matches a_id. If no match, it shows NULL for b.value.

Identify Repeating Operations

Look at what repeats as the query runs:

• Primary operation: For each row in table_a, the database looks for matching rows in table_b.
• How many times: This happens once per row in table_a.

How Execution Grows With Input

Imagine the number of rows in table_a is n and in table_b is m.

Input Size (n)	Approx. Operations
10	About 10 lookups in table_b
100	About 100 lookups in table_b
1000	About 1000 lookups in table_b

As table_a grows, the number of lookups grows roughly the same amount. The size of table_b affects how fast each lookup is.

Final Time Complexity

Time Complexity: O(n)

This means the time grows mostly with the number of rows in the first table (table_a), assuming lookups in table_b are fast (e.g., indexed).

Common Mistake

[X] Wrong: "The query always takes time proportional to the product of both tables' sizes (n x m)."

[OK] Correct: Because databases use indexes or hashing to find matches quickly, they don't check every row in table_b for each row in table_a. So the time depends mostly on table_a size.

Interview Connect

Understanding how JOINs scale helps you write queries that stay fast as data grows. This skill shows you know how databases work behind the scenes.

Self-Check

"What if we changed LEFT JOIN to RIGHT JOIN? How would the time complexity change?"