Cross joins and when to avoid them in Apache Spark - Time & Space Complexity

Time Complexity: Cross joins and when to avoid them

O(n * m)

Understanding Time Complexity

Cross joins combine every row from one table with every row from another. This can create a huge number of results quickly.

We want to understand how the work grows as the input tables get bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

val df1 = spark.read.csv("data1.csv")
val df2 = spark.read.csv("data2.csv")

val crossJoined = df1.crossJoin(df2)
crossJoined.show()

This code reads two datasets and creates a cross join, pairing every row from the first with every row from the second.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Pairing each row of the first dataset with every row of the second dataset.
• How many times: For each row in the first dataset, it repeats for all rows in the second dataset.

How Execution Grows With Input

Explain the growth pattern intuitively.

Input Size (n)	Approx. Operations
10 rows in each dataset	100 pairs (10 x 10)
100 rows in each dataset	10,000 pairs (100 x 100)
1,000 rows in each dataset	1,000,000 pairs (1,000 x 1,000)

Pattern observation: The number of pairs grows very fast, multiplying the sizes of both datasets.

Final Time Complexity

Time Complexity: O(n * m)

This means the work grows by multiplying the number of rows in both datasets, so doubling one dataset doubles the total work.

Common Mistake

[X] Wrong: "Cross joins only add a small amount of extra work compared to normal joins."

[OK] Correct: Cross joins multiply the number of rows, which can quickly explode the amount of data and work, unlike normal joins that match rows based on keys.

Interview Connect

Understanding how cross joins grow helps you explain why some queries become slow and how to avoid costly operations in real projects.

Self-Check

"What if we replaced the cross join with an inner join on a key? How would the time complexity change?"

Practice

1. What does a cross join do in Apache Spark?

easy

A. Combines every row of one table with every row of another table

B. Joins tables based on matching keys

C. Filters rows based on a condition

D. Aggregates data by groups

Solution

1. Step 1: Understand the join type

   A cross join pairs each row from the first table with every row from the second table, creating all possible combinations.

2. Step 2: Compare with other join types

   Unlike inner or outer joins, cross join does not require matching keys or conditions.

3. Final Answer:

   Combines every row of one table with every row of another table -> Option A

4. Quick Check:

   Cross join = all row pairs [OK]

Hint: Cross join = all combinations of rows [OK]

Common Mistakes:

• Confusing cross join with inner join
• Thinking cross join filters rows
• Assuming cross join requires keys

2. Which of the following is the correct syntax to perform a cross join between two DataFrames df1 and df2 in Apache Spark?

easy

A. df1.join(df2, on='id', how='cross')

B. df1.join(df2, 'inner')

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

D. df1.crossJoin(df2)

Solution

1. Step 1: Recall cross join method

   In Spark, cross joins are done using the crossJoin() method on a DataFrame.

2. Step 2: Check other options

   Syntax using join() with on='id' or how='inner' performs key-based or inner joins, not cross joins. df1.join(df2, on='id', how='cross') is invalid for cross join due to the key condition.

3. Final Answer:

   df1.crossJoin(df2) -> Option D

4. Quick Check:

   Use crossJoin() for cross joins [OK]

Hint: Use df.crossJoin(other_df) for cross joins [OK]

Common Mistakes:

• Using join() with how='cross' (not supported)
• Forgetting to use crossJoin() method
• Confusing join types in syntax

3. Given two DataFrames df1 with 3 rows and df2 with 4 rows, what will be the number of rows after performing df1.crossJoin(df2)?

medium

A. 7

B. 12

C. 1

D. 0

Solution

1. Step 1: Understand cross join output size

   A cross join creates every combination of rows from both DataFrames, so total rows = rows in df1 * rows in df2.

2. Step 2: Calculate total rows

   3 rows in df1 * 4 rows in df2 = 12 rows in the result.

3. Final Answer:

   12 -> Option B

4. Quick Check:

   3 * 4 = 12 rows [OK]

Hint: Multiply row counts for cross join output size [OK]

Common Mistakes:

• Adding row counts instead of multiplying
• Assuming cross join filters rows
• Confusing with inner join row counts

4. You run a cross join on two large DataFrames and your Spark job crashes due to memory errors. What is the most likely cause?

medium

A. Cross join created too many row combinations causing memory overflow

B. The join condition was missing

C. DataFrames had no columns in common

D. Spark does not support cross joins

Solution

1. Step 1: Understand cross join behavior on large data

   Cross joins multiply row counts, so large DataFrames produce huge outputs that can exceed memory limits.

2. Step 2: Analyze other options

   Missing join condition is normal for cross join. Having no columns in common is allowed. Spark supports cross joins explicitly.

3. Final Answer:

   Cross join created too many row combinations causing memory overflow -> Option A

4. Quick Check:

   Large cross join = memory issues [OK]

Hint: Avoid cross joins on big data to prevent crashes [OK]

Common Mistakes:

• Thinking missing join condition causes crash
• Believing Spark disallows cross joins
• Ignoring data size impact on memory

5. You have two DataFrames: products with 1000 rows and colors with 50 rows. You want to generate all possible product-color pairs but avoid performance issues. Which approach is best?

hard

A. Use inner join on a common key

B. Use products.crossJoin(colors) directly

C. Filter products or colors first to reduce rows before cross join

D. Avoid joining and process separately

Solution

1. Step 1: Understand cross join size impact

   Direct cross join creates 1000 * 50 = 50,000 rows, which may be large but manageable depending on resources.

2. Step 2: Optimize by filtering

   Reducing rows before cross join lowers output size and improves performance, avoiding memory issues.

3. Step 3: Evaluate other options

   Inner join requires keys which may not exist. Avoiding join loses the goal of pairing products and colors.

4. Final Answer:

   Filter products or colors first to reduce rows before cross join -> Option C

5. Quick Check:

   Filter before cross join to optimize [OK]

Hint: Filter data before cross join to reduce size [OK]

Common Mistakes:

• Using cross join without filtering on large data
• Trying inner join without keys
• Skipping join when pairs are needed