Streaming joins in Apache Spark - Time & Space Complexity

Time Complexity: Streaming joins

O(n * m)

Understanding Time Complexity

When working with streaming data, joining two streams efficiently is important.

We want to know how the time to join grows as the streams get bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

val stream1 = spark.readStream.format("socket").option("host", "localhost").option("port", 9999).load()
val stream2 = spark.readStream.format("socket").option("host", "localhost").option("port", 9998).load()

val joinedStream = stream1.join(stream2, expr("stream1.key = stream2.key"))

val query = joinedStream.writeStream.format("console").start()
query.awaitTermination()

This code joins two streaming data sources on a key and outputs the joined results.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Matching keys from both streams continuously as new data arrives.
• How many times: For each new batch of data, the join operation compares keys between the two streams.

How Execution Grows With Input

As more data arrives in each stream, the join operation must compare more keys.

Input Size (n)	Approx. Operations
10	About 100 key comparisons
100	About 10,000 key comparisons
1000	About 1,000,000 key comparisons

Pattern observation: The number of comparisons grows roughly with the product of the sizes of the two streams.

Final Time Complexity

Time Complexity: O(n * m)

This means the time to join grows roughly with the number of items in both streams multiplied together.

Common Mistake

[X] Wrong: "Joining two streams is always fast because data comes in small pieces."

[OK] Correct: Even small batches can add up, and the join compares keys across both streams, so time can grow quickly as data accumulates.

Interview Connect

Understanding how streaming joins scale helps you explain real-time data processing challenges clearly and confidently.

Self-Check

What if we added a time window to limit how far back the join looks? How would the time complexity change?

Practice

1. What is the main purpose of a streaming join in Apache Spark?

easy

A. To combine two live data streams based on matching keys

B. To save streaming data permanently to disk

C. To convert batch data into streaming data

D. To filter out duplicate records in a stream

Solution

1. Step 1: Understand streaming join concept

   Streaming joins are used to combine two live streams by matching keys in real time.

2. Step 2: Differentiate from other operations

   Saving data, converting batch to stream, or filtering duplicates are different tasks, not streaming joins.

3. Final Answer:

   To combine two live data streams based on matching keys -> Option A

4. Quick Check:

   Streaming join = combine streams by keys [OK]

Hint: Streaming joins combine live streams on keys [OK]

Common Mistakes:

• Confusing streaming join with saving data
• Thinking streaming join converts batch to stream
• Mixing up filtering duplicates with joining

2. Which of the following is the correct syntax to perform a streaming join between two DataFrames streamA and streamB on column id in Spark?

easy

A. streamA.concat(streamB, 'id')

B. streamA.merge(streamB, on='id')

C. streamA.join(streamB, streamA.id == streamB.id)

D. streamA.union(streamB).filter('id')

Solution

1. Step 1: Recall Spark join syntax

   Spark uses .join() with a join condition like streamA.id == streamB.id.

2. Step 2: Check other options

   .merge(), .concat(), and .union() are not valid for streaming joins in Spark.

3. Final Answer:

   streamA.join(streamB, streamA.id == streamB.id) -> Option C

4. Quick Check:

   Streaming join syntax = .join(condition) [OK]

Hint: Use .join() with condition for streaming joins [OK]

Common Mistakes:

• Using .merge() instead of .join()
• Trying to concatenate streams for join
• Using union which just stacks data

3. Given the following Spark Structured Streaming code, what will be the output schema of the joined stream?

streamA = spark.readStream.format('socket').option('host', 'localhost').option('port', 9999).load()
streamB = spark.readStream.format('socket').option('host', 'localhost').option('port', 9998).load()
joinedStream = streamA.join(streamB, streamA.value == streamB.value)
joinedStream.printSchema()

medium

A. StructType with only one 'value' column

B. StructType with two 'value' columns from streamA and streamB

C. Error due to ambiguous column names

D. Empty schema because streams are empty

Solution

1. Step 1: Understand join output schema

   Joining two streams with same column names results in both columns included with source prefixes.

2. Step 2: Check for ambiguity handling

   Spark automatically prefixes columns to avoid ambiguity, so no error occurs.

3. Final Answer:

   StructType with two 'value' columns from streamA and streamB -> Option B

4. Quick Check:

   Join output = both columns with prefixes [OK]

Hint: Joined streams keep both columns with prefixes [OK]

Common Mistakes:

• Assuming only one column remains after join
• Expecting error due to same column names
• Thinking schema is empty before data arrives

4. Consider this code snippet for joining two streaming DataFrames:

joinedStream = streamA.join(streamB, 'id')

When running this code, you get a runtime error about missing watermark. What is the likely cause?

medium

A. The join type is missing

B. The join condition 'id' is invalid syntax

C. The streams have different schemas

D. No watermark defined on one or both streams causing state to grow indefinitely

Solution

1. Step 1: Understand watermark role in streaming joins

   Watermarks limit how long Spark keeps state for late data in streaming joins.

2. Step 2: Identify cause of runtime error

   Without watermark, Spark cannot clean old state, causing errors about state size.

3. Final Answer:

   No watermark defined on one or both streams causing state to grow indefinitely -> Option D

4. Quick Check:

   Missing watermark = runtime error in streaming join [OK]

Hint: Always set watermark to avoid state errors [OK]

Common Mistakes:

• Thinking join condition syntax is wrong
• Assuming schema mismatch causes this error
• Believing join type must always be specified

5. You have two streaming DataFrames: orders with columns orderId, customerId, orderTime and customers with columns customerId, customerName, updateTime. You want to join them on customerId but only match orders with customer info updated within 1 hour before the order. Which approach correctly implements this streaming join?

hard

A. Use event-time watermark on both streams and join with condition: orders.customerId = customers.customerId AND customers.updateTime BETWEEN orders.orderTime - interval 1 hour AND orders.orderTime

B. Join on customerId only without watermark or time condition

C. Use batch join after collecting streaming data

D. Join on customerId and filter results after join for time difference

Solution

1. Step 1: Use watermarks to handle late data

   Set watermarks on orderTime and updateTime to manage state and late events.

2. Step 2: Apply join condition with time range

   Join on customerId and add time condition to match updates within 1 hour before order.

3. Step 3: Avoid filtering after join or batch join

   Filtering after join wastes resources; batch join loses streaming benefits.

4. Final Answer:

   Use event-time watermark on both streams and join with condition: orders.customerId = customers.customerId AND customers.updateTime BETWEEN orders.orderTime - interval 1 hour AND orders.orderTime -> Option A

5. Quick Check:

   Watermark + time condition in join = correct streaming join [OK]

Hint: Use watermark and time range in join condition [OK]

Common Mistakes:

• Skipping watermark causing state issues
• Joining without time condition losing accuracy
• Filtering after join instead of in join condition
• Using batch join losing streaming benefits