Merge (upsert) operations in Apache Spark - Time & Space Complexity

Time Complexity: Merge (upsert) operations

O(n)

Understanding Time Complexity

When we merge data in Apache Spark, we combine two datasets by matching rows. Understanding how long this takes helps us work efficiently with big data.

We want to know how the time to merge grows as the data gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import org.apache.spark.sql.functions._

val target = spark.table("target_table")
val updates = spark.table("updates_table")

val merged = target.as("t")
  .join(updates.as("u"), Seq("id"), "full_outer")
  .selectExpr(
    "coalesce(u.id, t.id) as id",
    "coalesce(u.value, t.value) as value"
  )

merged.write.mode("overwrite").saveAsTable("target_table")
    

This code merges updates into a target table by joining on an ID and choosing updated values when available.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The join operation compares rows from both datasets based on the ID.
• How many times: Each row in the target is compared to matching rows in updates, so roughly once per row in each dataset.

How Execution Grows With Input

As the number of rows in the datasets grows, the join operation must handle more comparisons.

Input Size (n)	Approx. Operations
10	About 10 comparisons per dataset
100	About 100 comparisons per dataset
1000	About 1000 comparisons per dataset

Pattern observation: The work grows roughly in direct proportion to the number of rows in the datasets.

Final Time Complexity

Time Complexity: O(n)

This means the time to merge grows roughly in a straight line as the data size increases.

Common Mistake

[X] Wrong: "Merging two datasets always takes the same time no matter how big they are."

[OK] Correct: The bigger the datasets, the more rows need to be matched and combined, so it takes more time.

Interview Connect

Knowing how merge operations scale helps you explain data processing choices clearly and shows you understand working with large datasets efficiently.

Self-Check

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

Practice

1. What is the main purpose of a merge (upsert) operation in Apache Spark with Delta Lake?

easy

A. To update existing rows and insert new rows in one step

B. To delete all rows from a table

C. To create a new Spark session

D. To read data from a CSV file

Solution

1. Step 1: Understand the merge operation concept

   Merge (upsert) combines update and insert actions to keep data synchronized.

2. Step 2: Identify the main use case in Spark with Delta Lake

   It updates existing rows and inserts new rows efficiently in one command.

3. Final Answer:

   To update existing rows and insert new rows in one step -> Option A

4. Quick Check:

   Merge = update + insert [OK]

Hint: Merge means update existing and insert new rows together [OK]

Common Mistakes:

• Confusing merge with delete operation
• Thinking merge only inserts data
• Assuming merge creates new tables

2. Which of the following is the correct syntax to start a merge operation in Spark SQL with Delta Lake?

easy

A. deltaTable.select(sourceDF).merge()

B. deltaTable.join(sourceDF).update()

C. deltaTable.insert(sourceDF).update()

D. deltaTable.merge(sourceDF, condition).whenMatchedUpdateAll().whenNotMatchedInsertAll().execute()

Solution

1. Step 1: Recall the merge syntax in Delta Lake

   The merge starts with deltaTable.merge(sourceDF, condition) followed by update and insert clauses.

2. Step 2: Match the full correct method chain

   Correct chain is whenMatchedUpdateAll(), whenNotMatchedInsertAll(), then execute().

3. Final Answer:

   deltaTable.merge(sourceDF, condition).whenMatchedUpdateAll().whenNotMatchedInsertAll().execute() -> Option D

4. Quick Check:

   Correct merge syntax = deltaTable.merge(sourceDF, condition).whenMatchedUpdateAll().whenNotMatchedInsertAll().execute() [OK]

Hint: Merge uses .merge().whenMatchedUpdateAll().whenNotMatchedInsertAll().execute() [OK]

Common Mistakes:

• Using join instead of merge
• Calling update before merge
• Missing execute() at the end

3. Given the following Spark code snippet, what will be the output count of rows in targetTable after the merge?

val sourceDF = spark.createDataFrame(Seq((1, "A"), (3, "C"))).toDF("id", "value")
val deltaTable = DeltaTable.forName("targetTable")
deltaTable.merge(sourceDF, "target.id = source.id")
  .whenMatchedUpdateExpr(Map("value" -> "source.value"))
  .whenNotMatchedInsertExpr(Map("id" -> "source.id", "value" -> "source.value"))
  .execute()
val count = spark.table("targetTable").count()

Assuming targetTable initially has rows with ids 1 and 2.

medium

A. 2

B. 3

C. 4

D. 1

Solution

1. Step 1: Analyze initial data in targetTable

   targetTable has ids 1 and 2 initially.

2. Step 2: Apply merge logic with sourceDF

   Source has ids 1 and 3. Id 1 matches and updates value. Id 3 does not match and inserts new row.

3. Step 3: Calculate final row count

   Rows after merge: ids 1 (updated), 2 (unchanged), 3 (inserted) -> total 3 rows.

4. Final Answer:

   3 -> Option B

5. Quick Check:

   Initial 2 + 1 inserted = 3 rows [OK]

Hint: Count = initial rows + new inserts after merge [OK]

Common Mistakes:

• Counting only updated rows
• Ignoring inserted rows
• Assuming rows are deleted

4. Identify the error in the following merge operation code snippet:

deltaTable.merge(sourceDF, "target.id = source.id")
  .whenMatchedUpdate(Map("value" -> "source.value"))
  .whenNotMatchedInsert(Map("id" -> "source.id", "value" -> "source.value"))
  .execute()

medium

A. The update and insert methods should be whenMatchedUpdateExpr and whenNotMatchedInsertExpr

B. The condition string should use backticks around column names

C. The execute() method is missing

D. The source DataFrame is not registered as a temp view

Solution

1. Step 1: Check method names for update and insert

   In Delta Lake merge, update and insert with expressions require whenMatchedUpdateExpr and whenNotMatchedInsertExpr.

2. Step 2: Verify other parts of the code

   Condition string and execute() are correct; sourceDF does not need temp view for merge.

3. Final Answer:

   The update and insert methods should be whenMatchedUpdateExpr and whenNotMatchedInsertExpr -> Option A

4. Quick Check:

   Use whenMatchedUpdateExpr and whenNotMatchedInsertExpr [OK]

Hint: Use whenMatchedUpdateExpr and whenNotMatchedInsertExpr for expression maps [OK]

Common Mistakes:

• Using whenMatchedUpdate instead of whenMatchedUpdateExpr
• Forgetting execute()
• Miswriting condition string syntax

5. You have a Delta table users with columns user_id and email. You receive a new DataFrame updatesDF with updated emails and new users. How do you write a merge operation to update emails for existing users and insert new users, ensuring no duplicates and preserving existing users without changes?

hard

A. Use filter to remove duplicates before inserting

B. Use join and then insert only new users

C. Use merge with condition on user_id, update email when matched, insert all columns when not matched

D. Overwrite the entire users table with updatesDF

Solution

1. Step 1: Define merge condition on user_id

   Match rows where users.user_id = updatesDF.user_id to identify existing users.

2. Step 2: Specify update and insert actions

   Update email for matched users, insert all columns for unmatched (new) users.

3. Step 3: Preserve existing users without changes

   Rows not matched remain unchanged automatically in merge.

4. Final Answer:

   Use merge with condition on user_id, update email when matched, insert all columns when not matched -> Option C

5. Quick Check:

   Merge = update matched + insert unmatched [OK]

Hint: Merge on user_id, update email if matched, insert if not [OK]

Common Mistakes:

• Overwriting entire table losing data
• Using join without update logic
• Not handling unmatched rows