Select, filter, and where operations in Apache Spark - Time & Space Complexity

Time Complexity: Select, filter, and where operations

O(n)

Understanding Time Complexity

We want to understand how the time to run select, filter, and where operations changes as the data grows.

How does the work increase when we have more rows in our data?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

from pyspark.sql import SparkSession

spark = SparkSession.builder.getOrCreate()
df = spark.read.csv('data.csv', header=True, inferSchema=True)

filtered_df = df.filter(df['age'] > 30)
selected_df = filtered_df.select('name', 'age')
result = selected_df.where(selected_df['age'] < 50)

This code reads data, filters rows where age is over 30, selects only name and age columns, then filters again where age is less than 50.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning each row to apply filter conditions.
• How many times: Each row is checked once per filter operation, so twice in total here.

How Execution Grows With Input

As the number of rows grows, the time to check each row grows too.

Input Size (n)	Approx. Operations
10	About 20 checks (2 filters x 10 rows)
100	About 200 checks
1000	About 2000 checks

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

Final Time Complexity

Time Complexity: O(n)

This means the time grows linearly with the number of rows in the data.

Common Mistake

[X] Wrong: "Filtering multiple times multiplies the time complexity exponentially."

[OK] Correct: Each filter scans the data once, so time adds up linearly, not exponentially.

Interview Connect

Understanding how filtering and selecting scale helps you explain data processing speed clearly and confidently.

Self-Check

"What if we added a join operation after the filters? How would the time complexity change?"

Practice

1. What does the select operation do in Apache Spark DataFrame?

easy

A. It chooses specific columns from the DataFrame.

B. It filters rows based on a condition.

C. It sorts the DataFrame by a column.

D. It adds new columns to the DataFrame.

Solution

1. Step 1: Understand the purpose of select

   The select operation is used to pick specific columns from a DataFrame, reducing the data to only those columns.

2. Step 2: Differentiate from filtering rows

   Filtering rows is done by filter or where, not by select.

3. Final Answer:

   It chooses specific columns from the DataFrame. -> Option A

4. Quick Check:

   Select = Choose columns [OK]

Hint: Select picks columns, filter/where pick rows [OK]

Common Mistakes:

• Confusing select with filter or where
• Thinking select filters rows
• Assuming select adds columns

2. Which of the following is the correct syntax to filter rows where column age is greater than 30 in a Spark DataFrame df?

easy

A. df.where(df.age > 30)

B. df.filter('age > 30')

C. All of the above

D. df.filter(df.age > 30)

Solution

1. Step 1: Understand filter syntax options

   In Spark, filter can accept either a column expression like df.age > 30 or a string condition like 'age > 30'.

2. Step 2: Recognize where is similar to filter

   where is an alias for filter and accepts the same arguments.

3. Final Answer:

   All of the above -> Option C

4. Quick Check:

   filter and where accept column or string conditions [OK]

Hint: filter and where accept column or string conditions [OK]

Common Mistakes:

• Using wrong syntax like df.filter(age > 30) without df.
• Confusing filter with select syntax
• Thinking where is different from filter

3. Given the Spark DataFrame df with columns name and age, what will be the output of this code?

df.select('name').filter(df.age >= 25).show()

medium

A. Shows names of all rows where age is 25 or more.

B. Shows all columns for rows where age is 25 or more.

C. Shows names of all rows regardless of age.

D. Throws an error because of wrong syntax.

Solution

1. Step 1: Analyze select operation

   select('name') projects only the name column, resulting in a DataFrame schema of ['name'].

2. Step 2: Analyze filter condition

   filter(df.age >= 25) tries to use the age column, but age is unavailable after select, causing a column resolution error.

3. Final Answer:

   Throws an error because of wrong syntax. -> Option D

4. Quick Check:

   Filter on unselected column after select = error [OK]

Hint: Filter rows before selecting columns [OK]

Common Mistakes:

• Thinking filter applies before select due to lazy evaluation
• Expecting all columns to show
• Confusing syntax causing errors

4. Identify the error in this Spark code snippet:

df.filter(df['age'] > 20).select('name', 'age').where('age < 18').show()

medium

A. Using both filter and where is not allowed.

B. The filter and where conditions contradict each other.

C. select must come before filter or where.

D. The syntax for where is incorrect.

Solution

1. Step 1: Analyze filter condition

   filter(df['age'] > 20) keeps rows where age is greater than 20.

2. Step 2: Analyze where condition

   where('age < 18') keeps rows where age is less than 18.

3. Step 3: Identify contradiction

   Rows cannot satisfy both conditions simultaneously, so the result will be empty or logically inconsistent.

4. Final Answer:

   The filter and where conditions contradict each other. -> Option B

5. Quick Check:

   Contradictory filters = no matching rows [OK]

Hint: Check if filter and where conditions conflict [OK]

Common Mistakes:

• Thinking filter and where cannot be chained
• Assuming select must come first
• Ignoring logical contradictions in conditions

5. You have a Spark DataFrame df with columns city, temperature, and humidity. You want to select only city and temperature columns, but only for rows where temperature is above 30 and humidity is below 50. Which code snippet correctly does this?

hard

A. df.filter((df.temperature > 30) & (df.humidity < 50)).select('city', 'temperature')

B. df.select('city', 'temperature').where('temperature > 30 AND humidity < 50')

C. df.select('city', 'temperature').filter((df.temperature > 30) & (df.humidity < 50))

D. df.select('city', 'temperature').where('temperature > 30').filter('humidity < 50')

Solution

1. Step 1: Filter rows first based on both conditions

   We must first keep rows where temperature > 30 and humidity < 50. This is done by filter or where with both conditions combined.

2. Step 2: Select only the desired columns after filtering

   After filtering, select only city and temperature columns to reduce data.

3. Step 3: Check each option

   A: selects first then filters on temperature and humidity -> error (humidity unavailable).
   B: selects first then where string with both -> error (humidity unavailable).
   C: filters first then selects -> correct.
   D: selects first, where on temperature then filter on humidity -> error.

4. Final Answer:

   df.filter((df.temperature > 30) & (df.humidity < 50)).select('city', 'temperature') -> Option A

5. Quick Check:

   Filter rows first, then select columns [OK]

Hint: Filter rows before selecting columns with needed data [OK]

Common Mistakes:

• Selecting columns before filtering on columns not selected
• Splitting filter conditions incorrectly
• Using string conditions inconsistently