Spark Join Strategies (Internals of Spark Joins & Spark’s choice of Join Strategy)

-

While dealing with data, we have to deal with different kinds of joins, be it inner, outer, left or (maybe)left-semi. This article covers the different join strategies employed by Spark to perform the join operations. Knowing spark join internals comes in handy to optimize tricky join operations, in finding root cause of some out of memory errors, and for improved performance of spark jobs(we all want that, don’t we?). Please read on to find out.

Broadcast Hash Join

Before beginning the Broadcast Hash join spark, let’s first understand Hash Join, in general:

As the name suggests, Hash Join is performed by first creating a Hash Table based on join_key of smaller relation and then looping over larger relation to match the hashed join_key values. Also, this is only supported for ‘=’ join.

In spark, Hash Join plays a role at per node level and the strategy is used to join partitions available on the node.

Now, coming to Broadcast Hash Join.

In broadcast hash join, copy of one of the join relations are being sent to all the worker nodes and it saves shuffling cost. This is useful when you are joining a large relation with a smaller one. It is also known as map-side join(associating worker nodes with mappers).

Spark deploys this join strategy when the size of one of the join relations is less than the threshold values(default 10 M). The spark property which defines this threshold is spark.sql.autoBroadcastJoinThreshold(configurable).

(read more here). It is a peer to peer protocol in which block of files can be shared by peers amongst each other. Hence, they don’t need to rely on a single node. This is how peer to peer protocol works:

Things to Note:

  • The broadcasted relation should fit completely into the memory of each executor as well as the driver. In Driver, because driver will start the data transfer.
  • Only supported for ‘=’ join.
  • Supported for all join types(inner, left, right) except full outer joins.
  • When the broadcast size is small, it is usually faster than other join strategies.
  • Copy of relation is broadcasted over the network. Therefore, being a network-intensive operation could cause out of memory errors or performance issues when broadcast size is big(for instance, when explicitly specified to use broadcast join/changes in the default threshold).
  • You can’t make changes to the broadcasted relation, after broadcast. Even if you do, they won’t be available to the worker nodes(because the copy is already shipped).

Shuffle hash join:

Shuffle Hash Join involves moving data with the same value of join key in the same executor node followed by Hash Join(explained above). Using the join condition as output key, data is shuffled amongst executor nodes and in the last step, data is combined using Hash Join, as we know data of the same key will be present in the same executor.

Things to Note:

  • Only supported for ‘=’ join.
  • The join keys don’t need to be sortable(this will make sense below).
  • Supported for all join types except full outer joins.
  • In my opinion, it’s an expensive join in a way that involves both shuffling and hashing(Hash Join as explained above). Maintaining a hash table requires memory and computation.

Shuffle sort-merge join

Let’s first understand Sort-Merge Join

Sort join involves, first sorting the relations based on join keys and then merging both the datasets(think of merge step of merge sort).

Now, let’s understand shuffle sort-merge join strategy in spark:

Shuffle sort-merge join involves, shuffling of data to get the same join_key with the same worker, and then performing sort-merge join operation at the partition level in the worker nodes.

Things to Note:

  • Since spark 2.3, this is the default join strategy in spark and can be disabled with spark.sql.join.preferSortMergeJoin.
  • Only supported for ‘=’ join.
  • The join keys need to be sortable(obviously).
  • Supported for all join types.

Cartesian Join

In this strategy, the cartesian product(similar to SQL) of the two relations is calculated to evaluate join.

Broadcast nested loop join

Think of this as a nested loop comparison of both the relations:

for record_1 in relation_1:  for record_2 in relation_2:    # join condition is executed

As you can see, this can be a very slow strategy. This is generally, a fallback option when no other join type can be applied. Spark handles this using BroadcastNestedLoopJoinExec operator that broadcasts the appropriate side of the query, so you can think that at least some chunk of results will be broadcasted to improve performance.

Things to note:

  • Supports both ‘=’ and non-equi-joins(‘≤=’, ‘<’ etc.).
  • Supports all the join types

How spark selects join strategy?

Taken directly from spark code, let’s see how spark decides on join strategy.

If it is an ‘=’ join:

Look at the join hints, in the following order:
1. Broadcast Hint: Pick broadcast hash join if the join type is supported.
2. Sort merge hint: Pick sort-merge join if join keys are sortable.
3. shuffle hash hint: Pick shuffle hash join if the join type is supported.
4. shuffle replicate NL hint: pick cartesian product if join type is inner like.

If there is no hint or the hints are not applicable
1. Pick broadcast hash join if one side is small enough to broadcast, and the join type is supported.
2. Pick shuffle hash join if one side is small enough to build the local hash map, and is much smaller than the other side, and spark.sql.join.preferSortMergeJoin is false.
3. Pick sort-merge join if join keys are sortable.
4. Pick cartesian product if join type is inner .
5. Pick broadcast nested loop join as the final solution. It may OOM but there is no other choice.

If it’s not ‘=’ join:

Look at the join hints, in the following order:
1. broadcast hint: pick broadcast nested loop join.
2. shuffle replicate NL hint: pick cartesian product if join type is inner like.

If there is no hint or the hints are not applicable
1. Pick broadcast nested loop join if one side is small enough to broadcast.
2. Pick cartesian product if join type is inner like.
3. Pick broadcast nested loop join as the final solution. It may OOM but we don’t have any other choice.

Popular posts from this blog

What is Garbage collection in Spark and its impact and resolution

-
Image
Garbage Collection Spark runs on the Java Virtual Machine (JVM). Because Spark can store large amounts of data in memory, it has a major reliance on Java’s memory management and garbage collection (GC). Therefore, garbage collection  (GC) can be a major issue that can affect many Spark applications. Common symptoms of excessive GC in Spark are: Slowness of application Executor heartbeat timeout GC overhead limit exceeded error Spark’s memory-centric approach and data-intensive applications make it a more common issue than other Java applications. Thankfully, it’s easy to diagnose if your Spark application is suffering from a GC problem. The Spark UI marks executors in red if they have spent too much time doing GC. Spark executors are spending a significant amount of CPU cycles performing garbage collection. This can be determined by looking at the “Executors” tab in the Spark application UI. Spark will mark an executor in  red  if the executor has spent more than 10% of the time in gar...
Read more

Window function in PySpark with Joins example using 2 Dataframes (inner join)

-
Input details: #● File has json records #● Each record has fields: #○ user_id #○ card_num #○ merchant #○ category #○ amount #○ ts ### Below analysis to be done Sample data: +------+--------+---------+--------+----------+-------+|amount|card_num| category|merchant| ts|user_id|+------+--------+---------+--------+----------+-------+| 243| C_108| food| M_102|1579532902| U_104|| 699| C_106|cosmetics| M_103|1581759040| U_103|| 228| C_104| children| M_110|1584161986| U_103| Solution: from pyspark.sql.functions import col # this can be done without using window function creditCardData = spark.read.json(“card_transactions.json”) useridMaxSpendDF = df.groupby(‘user_id’).max(‘amount’) useridMaxSpendDF=useridMaxSpendDF.withColumnRenamed(“max(amount)”,”max_amount”) useridMaxSpendDF=useridMaxSpendDF.withColumnRenamed(“user_id”,”m_user_id”) cond = [creditCardData.user_id == useridMaxSpen...
Read more

Complex SQL: fetch the users who logged in consecutively 3 or more times (lead perfect example)

-
From the login_details table, fetch the users who logged in consecutively 3 or more times. Table Name : LOGIN_DETAILS Approach : We need to fetch users who have appeared 3 or more times consecutively in login details table. There is a window function which can be used to fetch data from the following record. Use that window function to compare the user name in current row with user name in the next row and in the row following the next row. If it matches then fetch those records. –Table Structure: drop table login_details; create table login_details( login_id int primary key, user_name varchar(50) not null, login_date date); delete from login_details; insert into login_details values (101, ‘Michael’, current_date), (102, ‘James’, current_date), (103, ‘Stewart’, current_date+1), (104, ‘Stewart’, current_date+1), (105, ‘Stewart’, current_date+1), (106, ‘Michael’, current_date+2), (107, ‘Michael’, cur...
Read more