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?"

Practice

1. What does a LEFT JOIN do in PostgreSQL?

easy

A. Returns all rows from the left table and matching rows from the right table, or NULL if no match.

B. Returns all rows from the right table and matching rows from the left table, or NULL if no match.

C. Returns only rows that have matching values in both tables.

D. Returns all rows from both tables, matching where possible.

Solution

1. Step 1: Understand LEFT JOIN behavior

   A LEFT JOIN returns all rows from the left table regardless of matches in the right table.

2. Step 2: Check what happens with unmatched rows

   If there is no matching row in the right table, the result includes NULLs for right table columns.

3. Final Answer:

   Returns all rows from the left table and matching rows from the right table, or NULL if no match. -> Option A

4. Quick Check:

   LEFT JOIN = all left rows + matched right rows [OK]

Hint: LEFT JOIN keeps all left rows, fills right with NULL if no match [OK]

Common Mistakes:

• Confusing LEFT JOIN with RIGHT JOIN
• Thinking LEFT JOIN returns only matched rows
• Assuming unmatched rows are dropped

2. Which of the following is the correct syntax for a RIGHT JOIN in PostgreSQL?

easy

A. SELECT * FROM table1 RIGHT JOIN table2 ON table1.id = table2.id;

B. SELECT * FROM table1 JOIN RIGHT table2 ON table1.id = table2.id;

C. SELECT * FROM table1 RIGHT OUTER JOIN table2 WHERE table1.id = table2.id;

D. SELECT * FROM table1 RIGHT JOIN ON table1.id = table2.id table2;

Solution

1. Step 1: Recall correct RIGHT JOIN syntax

   The correct syntax is: SELECT ... FROM left_table RIGHT JOIN right_table ON condition;

2. Step 2: Check each option

   SELECT * FROM table1 RIGHT JOIN table2 ON table1.id = table2.id; matches the correct syntax exactly. Options B, C, and D have syntax errors or misplaced keywords.

3. Final Answer:

   SELECT * FROM table1 RIGHT JOIN table2 ON table1.id = table2.id; -> Option A

4. Quick Check:

   RIGHT JOIN syntax = FROM left_table RIGHT JOIN right_table ON condition [OK]

Hint: RIGHT JOIN syntax: FROM left_table RIGHT JOIN right_table ON condition [OK]

Common Mistakes:

• Placing JOIN keyword incorrectly
• Using WHERE instead of ON for join condition
• Misordering table names

3. Given these tables:

employees
id | name
1 | Alice
2 | Bob
3 | Carol

departments
id | dept_name
2 | Sales
3 | HR
4 | IT

What is the result of this query?

SELECT employees.name, departments.dept_name FROM employees LEFT JOIN departments ON employees.id = departments.id ORDER BY employees.id;

medium

A. [{"name": "Alice", "dept_name": "Sales"}, {"name": "Bob", "dept_name": "HR"}, {"name": "Carol", "dept_name": "IT"}]

B. [{"name": "Bob", "dept_name": "Sales"}, {"name": "Carol", "dept_name": "HR"}, {"name": null, "dept_name": "IT"}]

C. [{"name": "Alice", "dept_name": null}, {"name": "Bob", "dept_name": "Sales"}, {"name": "Carol", "dept_name": "HR"}]

D. [{"name": "Alice", "dept_name": null}, {"name": "Bob", "dept_name": null}, {"name": "Carol", "dept_name": null}]

Solution

1. Step 1: Understand LEFT JOIN with given tables

   LEFT JOIN keeps all employees. For each employee, it tries to find a department with matching id.

2. Step 2: Match rows and fill NULLs

   Alice (id=1) has no matching department, so dept_name is NULL. Bob (id=2) matches Sales. Carol (id=3) matches HR.

3. Final Answer:

   [{"name": "Alice", "dept_name": null}, {"name": "Bob", "dept_name": "Sales"}, {"name": "Carol", "dept_name": "HR"}] -> Option C

4. Quick Check:

   LEFT JOIN keeps all employees, unmatched dept_name is NULL [OK]

Hint: LEFT JOIN keeps all left rows; unmatched right columns are NULL [OK]

Common Mistakes:

• Assuming unmatched rows are excluded
• Mixing up LEFT and RIGHT JOIN results
• Ignoring NULL values for unmatched rows

4. You wrote this query but it gives an error:

SELECT * FROM employees RIGHT JOIN departments employees.id = departments.id;

What is the error and how to fix it?

medium

A. RIGHT JOIN is not supported; use LEFT JOIN instead

B. Missing ON keyword before join condition; fix by adding ON before employees.id = departments.id

C. Table names are reversed; switch employees and departments

D. Use WHERE instead of ON for join condition

Solution

1. Step 1: Identify syntax error in JOIN clause

   The query is missing the ON keyword before the join condition, which is required syntax.

2. Step 2: Correct the syntax

   Add ON before employees.id = departments.id to fix the error.

3. Final Answer:

   Missing ON keyword before join condition; fix by adding ON before employees.id = departments.id -> Option B

4. Quick Check:

   JOIN condition must use ON keyword [OK]

Hint: JOIN conditions always need ON keyword before condition [OK]

Common Mistakes:

• Omitting ON keyword
• Using WHERE instead of ON for join condition
• Confusing table order in JOIN

5. You want to list all departments and their employees, including departments with no employees. Which query achieves this?

hard

A. SELECT departments.dept_name, employees.name FROM employees RIGHT JOIN departments WHERE employees.id = departments.id;

B. SELECT departments.dept_name, employees.name FROM employees LEFT JOIN departments ON employees.id = departments.id;

C. SELECT departments.dept_name, employees.name FROM departments RIGHT JOIN employees ON departments.id = employees.id;

D. SELECT departments.dept_name, employees.name FROM departments LEFT JOIN employees ON departments.id = employees.id;

Solution

1. Step 1: Identify which table to keep all rows from

   We want all departments, even those without employees, so departments is the left table in LEFT JOIN.

2. Step 2: Use LEFT JOIN from departments to employees

   LEFT JOIN keeps all departments and adds matching employees or NULL if none.

3. Final Answer:

   SELECT departments.dept_name, employees.name FROM departments LEFT JOIN employees ON departments.id = employees.id; -> Option D

4. Quick Check:

   LEFT JOIN from departments keeps all departments [OK]

Hint: LEFT JOIN from main table keeps all its rows, unmatched get NULLs [OK]

Common Mistakes:

• Using employees as left table instead of departments
• Using RIGHT JOIN incorrectly
• Confusing which table to keep all rows from