Time Complexity: RIGHT JOIN
O(n)
0
0
RIGHT JOIN in MySQL - Time & Space Complexity
Understanding Time Complexity
When using a RIGHT 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 operations changes when the input tables increase in size.
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
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 match.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: For each row in TableB, the database looks for matching rows in TableA.
- How many times: This matching happens once per row in TableB.
How Execution Grows With Input
As TableB grows, the database must check more rows to find matches in TableA.
| Input Size (TableB rows) | 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 query grows linearly with the number of rows in the right table (TableB).
Common Mistake
[X] Wrong: "The time depends mostly on the left table (TableA) size."
[OK] Correct: In a RIGHT JOIN, the database must process every row in the right table (TableB), so its size mainly drives the work.
Interview Connect
Understanding how JOINs scale helps you write efficient queries and explain your reasoning clearly in interviews.
Self-Check
"What if we changed RIGHT JOIN to LEFT JOIN? How would the time complexity change?"