Inner, left, right, and full outer joins in Apache Spark - Time & Space Complexity

Time Complexity: Inner, left, right, and full outer joins

O(n + m)

Understanding Time Complexity

When working with big data, joining tables is common. We want to know how the time to join grows as data grows.

How does the join operation cost change when the input data size increases?

Scenario Under Consideration

Analyze the time complexity of the following join operations in Apache Spark.

df1 = spark.read.csv('data1.csv', header=True)
df2 = spark.read.csv('data2.csv', header=True)

# Inner join
inner_join = df1.join(df2, 'id', 'inner')

# Left outer join
left_join = df1.join(df2, 'id', 'left_outer')

# Right outer join
right_join = df1.join(df2, 'id', 'right_outer')

# Full outer join
full_join = df1.join(df2, 'id', 'full_outer')

This code reads two datasets and performs four types of joins on the "id" column.

Identify Repeating Operations

Look at what repeats when Spark joins data.

• Primary operation: Matching rows from both datasets by the join key.
• How many times: Each row in both datasets is processed at least once during the join.

How Execution Grows With Input

As the number of rows in the datasets grows, the work to match rows grows too.

Input Size (n)	Approx. Operations
10	About 20 row matches
100	About 200 row matches
1000	About 2000 row matches

Pattern observation: The number of operations grows roughly in proportion to the total number of rows in both datasets combined.

Final Time Complexity

Time Complexity: O(n + m)

This means the time to join grows linearly with the size of both datasets combined.

Common Mistake

[X] Wrong: "Joins always take time proportional to the product of dataset sizes (like n * m)."

[OK] Correct: Spark uses smart methods like hashing and shuffling to avoid checking every pair, so it does not compare every row to every other row.

Interview Connect

Understanding join time complexity helps you explain how your data processing scales. It shows you know how big data tools handle large datasets efficiently.

Self-Check

"What if one dataset is much smaller than the other? How would that affect the time complexity of the join?"

Practice

1. Which type of join in Apache Spark returns only the rows that have matching keys in both DataFrames?

easy

A. Full outer join

B. Inner join

C. Right outer join

D. Left outer join

Solution

1. Step 1: Understand join types

   Inner join returns rows where keys match in both tables only.

2. Step 2: Compare with other joins

   Left, right, and full outer joins include unmatched rows from one or both tables.

3. Final Answer:

   Inner join -> Option B

4. Quick Check:

   Inner join = matching rows only [OK]

Hint: Inner join keeps only matching rows from both tables [OK]

Common Mistakes:

• Confusing inner join with left or right join
• Thinking full outer join returns only matches
• Assuming left join excludes unmatched rows

2. Which of the following is the correct syntax to perform a left outer join between two DataFrames df1 and df2 on column id in Apache Spark?

easy

A. df1.join(df2, df1.id == df2.id, 'inner')

B. df1.join(df2, df1.id == df2.id, 'full')

C. df1.join(df2, df1.id == df2.id, 'right_outer')

D. df1.join(df2, df1.id == df2.id, 'left')

Solution

1. Step 1: Identify join type keyword

   Left outer join uses 'left' as the join type string in Spark.

2. Step 2: Match syntax format

   The syntax is df1.join(df2, condition, 'left').

3. Final Answer:

   df1.join(df2, df1.id == df2.id, 'left') -> Option D

4. Quick Check:

   Left join keyword = 'left' [OK]

Hint: Use 'left' string for left outer join in join() method [OK]

Common Mistakes:

• Using 'left_outer' instead of 'left'
• Confusing join type strings like 'right_outer' for left join
• Omitting join condition or using wrong syntax

3. Given two DataFrames:
df1 = spark.createDataFrame([(1, 'A'), (2, 'B')], ['id', 'val1'])
df2 = spark.createDataFrame([(2, 'X'), (3, 'Y')], ['id', 'val2'])
What will be the result of df1.join(df2, 'id', 'right')?

medium

A. [ (1, 'A', null), (2, 'B', 'X'), (3, null, 'Y') ]

B. [ (1, 'A', null), (2, 'B', 'X') ]

C. [ (2, 'B', 'X'), (3, null, 'Y') ]

D. [ (2, 'B', 'X') ]

Solution

1. Step 1: Understand right join behavior

   Right join keeps all rows from right DataFrame (df2) and matches from left (df1).

2. Step 2: Match rows by 'id'

   Id=2 matches in both, id=3 only in df2, so df1 columns are null for id=3.

3. Final Answer:

   [ (1, 'A', null), (2, 'B', 'X'), (3, null, 'Y') ] -> Option A

4. Quick Check:

   Right join keeps all right rows [OK]

Hint: Right join keeps all right table rows, fills left with nulls if no match [OK]

Common Mistakes:

• Expecting left table rows to appear in right join
• Confusing right join with full outer join
• Misunderstanding null placement for unmatched rows

4. You wrote this Spark join code:
df1.join(df2, df1.id == df2.id, 'full_outerjoin')
But it throws an error. What is the likely cause?

medium

A. The join type string should be 'full' instead of 'full_outerjoin'

B. The join condition must use a string column name, not an expression

C. You must use 'outer' instead of 'full_outerjoin' as join type

D. Spark does not support full outer joins

Solution

1. Step 1: Check valid join type strings in Spark

   Spark expects 'full' or 'fullouter' but not 'full_outerjoin'.

2. Step 2: Identify correct string for full outer join

   The correct string is 'full', so 'full_outerjoin' causes error.

3. Final Answer:

   The join type string should be 'full' instead of 'full_outerjoin' -> Option A

4. Quick Check:

   Use 'full' for full outer join [OK]

Hint: Use 'full' not 'full_outerjoin' for full outer join string [OK]

Common Mistakes:

• Using 'full_outerjoin' instead of 'full'
• Thinking join condition must be string only
• Believing Spark lacks full outer join support

5. You have two DataFrames:
df1 = spark.createDataFrame([(1, 'A'), (2, 'B'), (4, 'D')], ['id', 'val1'])
df2 = spark.createDataFrame([(2, 'X'), (3, 'Y'), (4, 'Z')], ['id', 'val2'])
You want a DataFrame that shows all ids from both tables, with values from both, and null where no match exists. Which join should you use and what will be the output?

hard

A. Use left join; output: [(1, 'A', null), (2, 'B', 'X'), (4, 'D', 'Z')]

B. Use inner join; output: [(2, 'B', 'X'), (4, 'D', 'Z')]

C. Use full outer join; output: [(1, 'A', null), (2, 'B', 'X'), (3, null, 'Y'), (4, 'D', 'Z')]

D. Use right join; output: [(2, 'B', 'X'), (3, null, 'Y'), (4, 'D', 'Z')]

Solution

1. Step 1: Identify join type for all rows from both tables

   Full outer join returns all rows from both DataFrames, filling nulls where no match.

2. Step 2: Match rows and fill nulls

   Ids 1 and 3 appear only in one table, so their unmatched columns are null.

3. Final Answer:

   Use full outer join; output: [(1, 'A', null), (2, 'B', 'X'), (3, null, 'Y'), (4, 'D', 'Z')] -> Option C

4. Quick Check:

   Full outer join = all rows, nulls for no match [OK]

Hint: Full outer join keeps all rows from both tables with nulls [OK]

Common Mistakes:

• Using inner join and missing unmatched rows
• Confusing left or right join with full outer join
• Expecting no nulls in full outer join result