RIGHT JOIN execution behavior in SQL - Time & Space Complexity

Time Complexity: RIGHT JOIN execution behavior

O(n)

Understanding Time Complexity

When using a RIGHT JOIN in SQL, it's important to understand how the database processes the data. We want to know how the work grows as the tables get bigger.

How does the number of rows in each table affect the time it takes to run the RIGHT JOIN?

Scenario Under Consideration

Analyze the time complexity of the following SQL RIGHT JOIN query.

SELECT A.id, B.value
FROM TableA A
RIGHT JOIN TableB B ON A.id = B.a_id;
    

This query returns all rows from TableB and matches rows from TableA where the ids are equal.

Identify Repeating Operations

Look for repeated steps the database takes to join the tables.

• Primary operation: For each row in TableB, the database looks for matching rows in TableA.
• How many times: This happens once for every row in TableB.

How Execution Grows With Input

As TableB grows, the database must do more matching work for each new row.

Input Size (rows in TableB)	Approx. Operations
10	About 10 lookups in TableA
100	About 100 lookups in TableA
1000	About 1000 lookups in TableA

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

Final Time Complexity

Time Complexity: O(n)

This means the time to run the RIGHT JOIN grows linearly with the size of the right table (TableB), assuming efficient indexing on the join key.

Common Mistake

[X] Wrong: "The RIGHT JOIN time depends mostly on the left table (TableA)."

[OK] Correct: The database must check every row in the right table (TableB) to find matches, so the right table size drives the main work.

Interview Connect

Understanding how JOINs scale helps you write queries that run efficiently and predict how they behave with bigger data. This skill shows you think about performance, not just correctness.

Self-Check

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