Incremental processing patterns in Apache Spark - Time & Space Complexity

Time Complexity: Incremental processing patterns

O(n)

Understanding Time Complexity

When working with incremental processing in Apache Spark, it's important to understand how the time to process data changes as new data arrives.

We want to know how the processing time grows when we add more data in small steps instead of all at once.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

val baseData = spark.read.parquet("/data/base")
val newData = spark.read.parquet("/data/new")

val updatedData = baseData.union(newData).dropDuplicates()
updatedData.write.mode("overwrite").parquet("/data/base")
    

This code reads existing data, adds new data incrementally, removes duplicates, and overwrites the base data.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Combining datasets and removing duplicates involves scanning all rows.
• How many times: The union and deduplication happen once per incremental update, but the deduplication scans all combined data.

How Execution Grows With Input

As the base data grows, each incremental update processes more total data because it combines old and new data before deduplication.

Input Size (n)	Approx. Operations
10	Processes about 10 + new data rows
100	Processes about 100 + new data rows
1000	Processes about 1000 + new data rows

Pattern observation: The work grows roughly with the total size of the combined data, not just the new data.

Final Time Complexity

Time Complexity: O(n)

This means the time to process grows linearly with the total amount of data being combined and deduplicated.

Common Mistake

[X] Wrong: "Incremental processing only takes time proportional to the new data size."

[OK] Correct: Because the code combines new data with all existing data and removes duplicates, it must scan all data each time, so time depends on total data size.

Interview Connect

Understanding how incremental data processing scales helps you explain real-world data workflows clearly and confidently.

Self-Check

"What if we stored and updated a separate index of unique keys instead of deduplicating all data each time? How would the time complexity change?"

Practice

1.

What is the main idea behind incremental processing in Apache Spark?

easy

A. Delete old data before processing new data

B. Process all data repeatedly for accuracy

C. Process only new or changed data instead of all data every time

D. Use only batch processing without updates

Solution

1. Step 1: Understand incremental processing concept

   Incremental processing means working only on data that is new or has changed, not the entire dataset.

2. Step 2: Compare options to concept

   Process only new or changed data instead of all data every time matches this idea, while others describe full or batch processing.

3. Final Answer:

   Process only new or changed data instead of all data every time -> Option C

4. Quick Check:

   Incremental processing = new or changed data only [OK]

Hint: Incremental means update only new or changed data [OK]

Common Mistakes:

• Thinking incremental means reprocessing all data
• Confusing incremental with deleting old data
• Assuming incremental ignores changes

2.

Which Spark code snippet correctly filters new data for incremental processing?

df_new = df_all.filter(____)

easy

A. df_all.timestamp > last_processed_time

B. df_all.timestamp < last_processed_time

C. df_all.id == last_processed_id

D. df_all.date == '2020-01-01'

Solution

1. Step 1: Identify filtering condition for new data

   To get new data, filter rows with timestamp greater than last processed time.

2. Step 2: Match condition to options

   df_all.timestamp > last_processed_time uses > last_processed_time, which correctly selects new data.

3. Final Answer:

   df_all.timestamp > last_processed_time -> Option A

4. Quick Check:

   Filter new data by timestamp > last processed [OK]

Hint: Filter with timestamp greater than last processed time [OK]

Common Mistakes:

• Using less than instead of greater than
• Filtering by exact id instead of timestamp
• Filtering by unrelated fixed date

3.

Given this Spark code for incremental processing, what will df_incremental.count() output?

from pyspark.sql import SparkSession
spark = SparkSession.builder.getOrCreate()
data = [(1, '2024-01-01'), (2, '2024-01-02'), (3, '2024-01-03')]
df_all = spark.createDataFrame(data, ['id', 'date'])
last_processed_date = '2024-01-01'
df_incremental = df_all.filter(df_all.date > last_processed_date)
print(df_incremental.count())

medium

A. 2

B. 3

C. 1

D. 0

Solution

1. Step 1: Understand filtering condition

   Filter keeps rows where date > '2024-01-01'. Data has dates '2024-01-01', '2024-01-02', '2024-01-03'.

2. Step 2: Count rows matching condition

   Rows with dates '2024-01-02' and '2024-01-03' match, so count is 2.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Dates after '2024-01-01' = 2 rows [OK]

Hint: Count rows with date greater than last processed date [OK]

Common Mistakes:

• Including the date equal to last_processed_date
• Counting all rows instead of filtered
• Confusing greater than with less than

4.

Find the error in this Spark code for incremental processing:

df_incremental = df_all.filter(df_all.timestamp < last_processed_time)

Assuming last_processed_time is the timestamp of the last processed batch.

medium

A. The variable last_processed_time is undefined

B. The filter should use <= to include last processed data

C. The filter should use == to match last processed time

D. The filter should use > instead of < to get new data

Solution

1. Step 1: Understand filtering logic for incremental data

   Incremental processing requires filtering data newer than last processed time, so timestamp > last_processed_time.

2. Step 2: Identify incorrect operator

   The code uses < which selects older data, not new data.

3. Final Answer:

   The filter should use > instead of < to get new data -> Option D

4. Quick Check:

   New data filter uses > last processed time [OK]

Hint: New data means timestamp greater than last processed [OK]

Common Mistakes:

• Using less than instead of greater than
• Confusing equality with incremental filter
• Assuming variable is undefined without checking

5.

You have a Delta Lake table storing daily sales data. You want to update it incrementally with new data from a streaming source. Which approach is best?

hard

A. Delete the Delta table and recreate it daily

B. Use merge operation to upsert new and updated records into the Delta table

C. Append new data without checking for duplicates or updates

D. Overwrite the entire Delta table with new streaming data each time

Solution

1. Step 1: Understand Delta Lake incremental update capabilities

   Delta Lake supports merge to upsert (insert or update) records efficiently.

2. Step 2: Evaluate options for incremental update

   Use merge operation to upsert new and updated records into the Delta table uses merge, which handles new and changed data correctly. Others cause data loss or duplicates.

3. Final Answer:

   Use merge operation to upsert new and updated records into the Delta table -> Option B

4. Quick Check:

   Delta Lake incremental update = merge upsert [OK]

Hint: Use merge for incremental upsert in Delta Lake [OK]

Common Mistakes:

• Overwriting entire table loses old data
• Appending without deduplication causes duplicates
• Deleting table loses all history