Adaptive query execution in Apache Spark - Time & Space Complexity

Time Complexity: Adaptive query execution

O(n)

Understanding Time Complexity

Adaptive query execution helps Spark run queries faster by changing plans while running.

We want to know how the time to run a query changes as data size grows when using this feature.

Scenario Under Consideration

Analyze the time complexity of the following Spark code using adaptive query execution.

spark.conf.set("spark.sql.adaptive.enabled", "true")

val df = spark.read.parquet("/data/large_dataset")
val filtered = df.filter("age > 30")
val joined = filtered.join(spark.read.parquet("/data/lookup"), Seq("id"))
val result = joined.groupBy("country").count()
result.show()

This code reads large data, filters, joins with another dataset, groups, and counts, using adaptive query execution to optimize.

Identify Repeating Operations

Look for repeated work that affects time.

• Primary operation: Scanning and filtering large datasets, then joining and grouping.
• How many times: Each stage processes all rows in its input, but adaptive execution may split or adjust tasks.

How Execution Grows With Input

As data size grows, the work grows mostly in scanning and joining.

Input Size (n)	Approx. Operations
10	About 10 units of work scanning and joining
100	About 100 units of work, more scanning and joining
1000	About 1000 units, much more data to process

Pattern observation: The work grows roughly in proportion to the data size, but adaptive execution can reduce some repeated work by adjusting plans.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the query grows roughly in direct proportion to the amount of data processed.

Common Mistake

[X] Wrong: "Adaptive query execution makes the query run in constant time no matter the data size."

[OK] Correct: Adaptive execution helps optimize but still needs to process all data, so time grows with data size.

Interview Connect

Understanding how adaptive query execution affects time helps you explain real-world data processing efficiency clearly and confidently.

Self-Check

"What if we disabled adaptive query execution? How would the time complexity change?"

Practice

1.

What is the main purpose of adaptive query execution in Apache Spark?

easy

A. To improve query performance by adjusting the execution plan during runtime

B. To statically compile queries before execution

C. To disable query optimization for faster execution

D. To manually rewrite queries for better speed

Solution

1. Step 1: Understand adaptive query execution concept

   Adaptive query execution allows Spark to change the query plan dynamically while the query runs.

2. Step 2: Identify the main benefit

   This dynamic adjustment improves performance by optimizing joins and data shuffles based on actual data size.

3. Final Answer:

   To improve query performance by adjusting the execution plan during runtime -> Option A

4. Quick Check:

   Adaptive query execution = dynamic plan adjustment [OK]

Hint: Think: adaptive means changing during execution [OK]

Common Mistakes:

• Confusing adaptive execution with static query compilation
• Believing it disables optimization
• Thinking it requires manual query rewriting

2.

Which Spark configuration enables adaptive query execution?

?

easy

A. spark.sql.execution.adaptive.enabled = false

B. spark.execution.adaptive = true

C. spark.adaptive.query.execution = true

D. spark.sql.adaptive.enabled = true

Solution

1. Step 1: Recall the exact configuration key

   The correct key to enable adaptive query execution is spark.sql.adaptive.enabled.

2. Step 2: Confirm the value to enable

   Setting it to true activates adaptive query execution.

3. Final Answer:

   spark.sql.adaptive.enabled = true -> Option D

4. Quick Check:

   Enable adaptive query with spark.sql.adaptive.enabled [OK]

Hint: Remember full key: spark.sql.adaptive.enabled [OK]

Common Mistakes:

• Using incorrect config keys like spark.execution.adaptive
• Setting the value to false instead of true
• Mixing up config names with similar words

3.

Given the following Spark SQL code with adaptive query execution enabled, what will be the effect on the join?

spark.conf.set("spark.sql.adaptive.enabled", "true")

val df1 = spark.range(1000)
val df2 = spark.range(10)

val joined = df1.join(df2, df1("id") === df2("id"))
joined.explain(true)

What does adaptive query execution do here?

medium

A. It converts the join to a broadcast join because df2 is small

B. It disables the join optimization and runs a shuffle join

C. It throws an error because adaptive execution cannot handle joins

D. It caches both dataframes before joining

Solution

1. Step 1: Identify adaptive execution behavior on join

   Adaptive query execution detects small tables and converts joins to broadcast joins to reduce shuffle.

2. Step 2: Analyze data sizes in example

   df2 has only 10 rows, which is small enough to broadcast.

3. Final Answer:

   It converts the join to a broadcast join because df2 is small -> Option A

4. Quick Check:

   Small table join = broadcast join [OK]

Hint: Small table in join? Adaptive broadcasts it [OK]

Common Mistakes:

• Assuming adaptive disables optimization
• Thinking adaptive causes errors on joins
• Believing it caches dataframes automatically

4.

Consider this Spark code snippet with adaptive query execution enabled:

spark.conf.set("spark.sql.adaptive.enabled", "true")

val df1 = spark.range(1000)
val df2 = spark.range(1000000)

val joined = df1.join(df2, df1("id") === df2("id"))
joined.show()

The job runs very slowly. What is the likely cause?

medium

A. Adaptive query execution is disabled by default

B. Adaptive query execution tries to broadcast df2, which is too large

C. The join condition is invalid causing a runtime error

D. Spark automatically caches df2 causing memory overflow

Solution

1. Step 1: Understand adaptive join behavior with large tables

   Adaptive query execution may try to broadcast a table if it thinks it's small enough.

2. Step 2: Analyze table sizes

   df2 has 1,000,000 rows, which is too large to broadcast efficiently, causing slow execution.

3. Final Answer:

   Adaptive query execution tries to broadcast df2, which is too large -> Option B

4. Quick Check:

   Broadcasting large tables causes slow jobs [OK]

Hint: Large table broadcast causes slow join [OK]

Common Mistakes:

• Assuming adaptive is disabled by default
• Thinking join condition is invalid
• Believing Spark caches large tables automatically

5.

You have a Spark job joining three datasets of unknown sizes. How can adaptive query execution help optimize this multi-join query?

hard

A. It forces all joins to be shuffle joins regardless of size

B. It disables all joins and runs map-only jobs

C. It dynamically chooses broadcast or shuffle joins for each join based on runtime data size

D. It requires manual hints to optimize each join

Solution

1. Step 1: Understand adaptive query execution with multiple joins

   Adaptive query execution evaluates data sizes during runtime for each join.

2. Step 2: Explain optimization choice

   It chooses broadcast joins for small tables and shuffle joins for large tables automatically.

3. Step 3: Apply to multi-join scenario

   For three datasets, it optimizes each join individually based on actual data size.

4. Final Answer:

   It dynamically chooses broadcast or shuffle joins for each join based on runtime data size -> Option C

5. Quick Check:

   Adaptive = dynamic join strategy per join [OK]

Hint: Adaptive picks join type per join at runtime [OK]

Common Mistakes:

• Thinking adaptive disables joins
• Assuming all joins become shuffle joins
• Believing manual hints are always required