Window functions in Apache Spark - Time & Space Complexity

Time Complexity: Window functions

O(n log m)

Understanding Time Complexity

We want to understand how the time to run window functions changes as data grows.

How does the number of rows affect the work done by window functions?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

from pyspark.sql import Window
from pyspark.sql.functions import row_number

window_spec = Window.partitionBy('category').orderBy('value')
df = df.withColumn('row_num', row_number().over(window_spec))

This code adds a row number within each category, ordering rows by value.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: For each row, the window function looks at other rows in the same category to order them.
• How many times: This happens once per row, but ordering within each category involves comparing rows in that category.

How Execution Grows With Input

As the number of rows grows, the work to order rows in each category grows too.

Input Size (n)	Approx. Operations
10	About 10 rows ordered in groups
100	More rows, ordering within categories grows roughly with n log n per category
1000	Ordering cost increases more noticeably as groups get bigger

Pattern observation: The ordering inside each category grows faster than just the number of rows, because sorting takes more work as groups get larger.

Final Time Complexity

Time Complexity: O(n log m)

This means the time grows with the number of rows times the log of the average group size, due to sorting within each group.

Common Mistake

[X] Wrong: "Window functions always run in linear time with the number of rows."

[OK] Correct: Sorting inside each group takes more time than just looking at each row once, so the cost depends on group sizes and sorting.

Interview Connect

Understanding how window functions scale helps you explain performance in real data tasks and shows you know how grouping and ordering affect work done.

Self-Check

"What if we removed the orderBy clause from the window specification? How would the time complexity change?"

Practice

1. What is the main purpose of window functions in Apache Spark?

easy

A. To perform calculations across rows related to the current row without collapsing the data

B. To group data and reduce the number of rows

C. To filter rows based on a condition

D. To join two datasets together

Solution

1. Step 1: Understand window function behavior

   Window functions calculate values across related rows but keep all original rows intact.

2. Step 2: Compare with grouping

   Grouping reduces rows by aggregation, but window functions add columns without reducing rows.

3. Final Answer:

   To perform calculations across rows related to the current row without collapsing the data -> Option A

4. Quick Check:

   Window functions add calculations without grouping ≠ A [OK]

Hint: Window functions add columns, grouping reduces rows [OK]

Common Mistakes:

• Confusing window functions with groupBy aggregations
• Thinking window functions filter rows
• Assuming window functions join datasets

2. Which of the following is the correct way to define a window specification in PySpark to partition by 'department' and order by 'salary'?

easy

A. Window.groupBy('department').sortBy('salary')

B. Window.sortBy('salary').partitionBy('department')

C. Window.partitionBy('department').orderBy('salary')

D. Window.partition('department').order('salary')

Solution

1. Step 1: Recall PySpark window spec syntax

   The correct methods are partitionBy() and orderBy() chained on Window.

2. Step 2: Check method order and names

   partitionBy comes first, then orderBy; groupBy and sortBy are incorrect here.

3. Final Answer:

   Window.partitionBy('department').orderBy('salary') -> Option C

4. Quick Check:

   Use partitionBy then orderBy methods [OK]

Hint: Use Window.partitionBy().orderBy() exactly [OK]

Common Mistakes:

• Using groupBy instead of partitionBy
• Using sortBy instead of orderBy
• Using incorrect method names like partition or order

3. Given the following PySpark code, what will be the output of the 'rank' column?

from pyspark.sql import SparkSession
from pyspark.sql.window import Window
from pyspark.sql.functions import rank

spark = SparkSession.builder.getOrCreate()
data = [("Alice", "Sales", 5000), ("Bob", "Sales", 4000), ("Charlie", "Sales", 5000)]
df = spark.createDataFrame(data, ["name", "department", "salary"])
windowSpec = Window.partitionBy("department").orderBy("salary")
df = df.withColumn("rank", rank().over(windowSpec))
df.orderBy("salary").show()

medium

A. [ ("Bob", 4000, 1), ("Alice", 5000, 2), ("Charlie", 5000, 2) ]

B. [ ("Bob", 4000, 1), ("Alice", 5000, 3), ("Charlie", 5000, 3) ]

C. [ ("Bob", 4000, 1), ("Alice", 5000, 2), ("Charlie", 5000, 3) ]

D. [ ("Bob", 4000, 1), ("Alice", 5000, 1), ("Charlie", 5000, 1) ]

Solution

1. Step 1: Understand rank() behavior

   Rank assigns the same rank to ties and skips ranks after ties.

2. Step 2: Apply rank over salary ascending

   Bob has salary 4000 ranked 1; Alice and Charlie both have 5000, so both get rank 2.

3. Final Answer:

   [ ("Bob", 4000, 1), ("Alice", 5000, 2), ("Charlie", 5000, 2) ] -> Option A

4. Quick Check:

   rank() ties share rank, next rank skips [OK]

Hint: rank() gives same rank to ties, skips next ranks [OK]

Common Mistakes:

• Confusing rank() with dense_rank()
• Assigning different ranks to tied values
• Not ordering data before applying rank

4. Identify the error in this PySpark code snippet using window functions:

from pyspark.sql.window import Window
from pyspark.sql.functions import row_number

windowSpec = Window.partitionBy('department')
df = df.withColumn('row_num', row_number().over(windowSpec.orderBy('salary')))

medium

A. Missing import for Window functions causes error

B. windowSpec.orderBy('salary') is valid; no error in code

C. row_number() cannot be used with partitionBy

D. windowSpec.orderBy('salary') is invalid; orderBy should be called on Window, not on windowSpec

Solution

1. Step 1: Check windowSpec usage

   windowSpec is a WindowSpec object; calling orderBy on it is valid and returns a new WindowSpec.

2. Step 2: Confirm chaining

   Chaining orderBy on windowSpec is allowed to refine the window specification.

3. Final Answer:

   windowSpec.orderBy('salary') is valid; no error in code -> Option B

4. Quick Check:

   WindowSpec supports chaining orderBy to refine window [OK]

Hint: WindowSpec supports chaining orderBy to refine window [OK]

Common Mistakes:

• Calling orderBy on windowSpec instead of Window
• Assuming row_number can't be used with partitionBy
• Forgetting to import Window or functions

5. You have a sales dataset with columns: 'store', 'date', and 'sales'. You want to add a column showing the 3-day moving average of sales per store ordered by date. Which PySpark window function setup and code will achieve this?

hard

A. Use Window.partitionBy('store').orderBy('date').rowsBetween(0, 2) and avg('sales').over(windowSpec)

B. Use Window.partitionBy('store').orderBy('date').rangeBetween(-2, 0) and avg('sales').over(windowSpec)

C. Use Window.orderBy('date').rowsBetween(-3, 0) and avg('sales').over(windowSpec)

D. Use Window.partitionBy('store').orderBy('date').rowsBetween(-2, 0) and avg('sales').over(windowSpec)

Solution

1. Step 1: Define window for 3-day moving average per store

   Partition by 'store' to separate stores, order by 'date' for time sequence, use rowsBetween(-2, 0) for current and previous 2 rows.

2. Step 2: Apply avg() over this window

   Use avg('sales').over(windowSpec) to compute moving average over the defined window.

3. Final Answer:

   Use Window.partitionBy('store').orderBy('date').rowsBetween(-2, 0) and avg('sales').over(windowSpec) -> Option D

4. Quick Check:

   rowsBetween(-2,0) for 3-day window, partition by store [OK]

Hint: Use rowsBetween(-2,0) for 3-row moving average [OK]

Common Mistakes:

• Using rangeBetween instead of rowsBetween for row count
• Not partitioning by store
• Using wrong rowsBetween range (like 0 to 2)