Multi-column joins in Apache Spark - Time & Space Complexity

Time Complexity: Multi-column joins

O(n^2)

Understanding Time Complexity

When joining two big tables on multiple columns, it is important to know how the time to join grows as the tables get bigger.

We want to understand how the work needed changes when the input size increases.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

df1.join(df2, ["colA", "colB"], "inner")

This code joins two Spark DataFrames on two columns using an inner join.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Matching rows from both tables based on values in both columns.
• How many times: Each row in the first table is compared to matching rows in the second table on both columns.

How Execution Grows With Input

As the number of rows in each table grows, the number of comparisons grows roughly in proportion to the size of the tables.

Input Size (n)	Approx. Operations
10	About 10 comparisons per row, total around 100
100	About 100 comparisons per row, total around 10,000
1000	About 1000 comparisons per row, total around 1,000,000

Pattern observation: The work grows quadratically as input size increases.

Final Time Complexity

Time Complexity: O(n^2)

This means the join operation grows roughly in proportion to the product of the number of rows in the tables, unless Spark uses broadcast joins or other optimizations.

Common Mistake

[X] Wrong: "Joining on multiple columns multiplies the time complexity by the number of columns."

[OK] Correct: The join time depends mainly on the number of rows, not the number of columns used for matching, because Spark uses hashing and sorting techniques to handle multiple columns efficiently.

Interview Connect

Understanding how joins scale helps you explain data processing choices clearly and shows you know how big data tools handle large datasets efficiently.

Self-Check

"What if we changed the join type from inner to full outer? How would the time complexity change?"

Practice

1.

What does a multi-column join in Apache Spark do?

Choose the best description.

easy

A. It sorts a DataFrame by multiple columns.

B. It merges two DataFrames by adding columns without any condition.

C. It filters rows from a single DataFrame based on multiple columns.

D. It joins two DataFrames using more than one column to match rows.

Solution

1. Step 1: Understand join basics

   A join combines rows from two tables based on matching column values.

2. Step 2: Recognize multi-column join

   Multi-column join uses more than one column to find matching rows, improving accuracy.

3. Final Answer:

   It joins two DataFrames using more than one column to match rows. -> Option D

4. Quick Check:

   Multi-column join = match on multiple columns [OK]

Hint: Multi-column join matches rows on several columns at once [OK]

Common Mistakes:

• Confusing join with filtering
• Thinking join adds columns without condition
• Mixing join with sorting

2.

Which of the following is the correct syntax to perform a multi-column inner join between df1 and df2 on columns "id" and "date"?

df1.join(df2, _____, how="inner")

easy

A. ["id", "date"]

B. "id, date"

C. df1["id"] == df2["id"] and df1["date"] == df2["date"]

D. on=("id", "date")

Solution

1. Step 1: Check join parameter for columns

   The on parameter accepts a list of column names for multi-column join.

2. Step 2: Identify correct list syntax

   Using ["id", "date"] correctly passes both columns as a list.

3. Final Answer:

   ["id", "date"] -> Option A

4. Quick Check:

   List of columns = ["id", "date"] [OK]

Hint: Use a list of column names for multi-column join [OK]

Common Mistakes:

• Passing columns as a single string
• Using boolean expressions instead of list
• Incorrect tuple syntax for columns

3.

Given the following two DataFrames:

df1 = spark.createDataFrame([
  (1, "2023-01-01", "A"),
  (2, "2023-01-02", "B"),
  (3, "2023-01-03", "C")
], ["id", "date", "value"])

df2 = spark.createDataFrame([
  (1, "2023-01-01", "X"),
  (2, "2023-01-04", "Y"),
  (3, "2023-01-03", "Z")
], ["id", "date", "value2"])

result = df1.join(df2, ["id", "date"], how="inner").select("id", "date", "value", "value2")
result.show()

What will be the output?

medium

A. +---+----------+-----+-------+
|id |date |value|value2 |
+---+----------+-----+-------+
|1 |2023-01-01|A |X |
|2 |2023-01-04|B |Y |
|3 |2023-01-03|C |Z |
+---+----------+-----+-------+

B. +---+----------+-----+-------+
|id |date |value|value2 |
+---+----------+-----+-------+
|2 |2023-01-02|B |Y |
+---+----------+-----+-------+

C. +---+----------+-----+-------+
|id |date |value|value2 |
+---+----------+-----+-------+
|1 |2023-01-01|A |X |
|3 |2023-01-03|C |Z |
+---+----------+-----+-------+

D. +---+----------+-----+-------+
|id |date |value|value2 |
+---+----------+-----+-------+
|1 |2023-01-01|A |null |
|2 |2023-01-02|B |null |
|3 |2023-01-03|C |Z |
+---+----------+-----+-------+

Solution

1. Step 1: Understand inner join on multiple columns

   Inner join keeps rows where both id and date match in both DataFrames.

2. Step 2: Identify matching rows

   Rows with (1, "2023-01-01") and (3, "2023-01-03") match in both DataFrames; (2, "2023-01-02") and (2, "2023-01-04") do not.

3. Final Answer:

   Rows with id 1 and 3 with matching dates and values -> Option C

4. Quick Check:

   Inner join = only matching rows on all columns [OK]

Hint: Inner join keeps only rows matching all join columns [OK]

Common Mistakes:

• Including rows with partial matches
• Confusing inner join with outer join
• Ignoring the multi-column condition

4.

Consider this code snippet:

result = df1.join(df2, on=["id", "date"], how="inner")

When running this, you get an error: TypeError: join() got an unexpected keyword argument 'on'. What is the likely cause?

medium

A. The how parameter must be a list, not a string.

B. The on parameter should be passed as the second positional argument, not as a keyword.

C. The join method does not support multi-column joins.

D. The DataFrames must have the same schema before joining.

Solution

1. Step 1: Check join method signature

   In Spark, join() expects the join columns as the second positional argument, not as a keyword on.

2. Step 2: Correct usage

   Use df1.join(df2, ["id", "date"], how="inner") without on=.

3. Final Answer:

   The on parameter should be passed as the second positional argument, not as a keyword. -> Option B

4. Quick Check:

   Join columns = positional argument [OK]

Hint: Pass join columns as positional argument, not 'on=' keyword [OK]

Common Mistakes:

• Using 'on=' keyword in join
• Passing 'how' as a list
• Assuming join needs identical schemas

5.

You have two DataFrames, orders and customers. You want to join them on customer_id and region, but some customers have missing region values in one DataFrame. You want to keep all orders and add customer info where possible. Which join type and approach should you use?

hard

A. Use a left join on customer_id only, then filter or fill missing region values separately.

B. Use an inner join on both columns; only rows with matching customer_id and region appear.

C. Use a left join on both columns; missing region values will exclude some matches.

D. Use a full outer join on both columns to keep all rows from both DataFrames.

Solution

1. Step 1: Understand join requirements

   You want all orders (left DataFrame) and customer info where available, but region may be missing in one DataFrame.

2. Step 2: Choose join columns carefully

   Joining on both columns will exclude rows with missing region. Joining only on customer_id keeps all orders.

3. Step 3: Handle missing region values separately

   After join, fill or filter missing region values as needed.

4. Final Answer:

   Use a left join on customer_id only, then handle missing region values separately. -> Option A

5. Quick Check:

   Left join on key column + handle missing data [OK]

Hint: Join on reliable keys first, handle missing columns after [OK]

Common Mistakes:

• Joining on columns with missing values directly
• Using inner join and losing rows
• Using full outer join when not needed