Apache Spark - Sort Merge Join

By








Apache Spark is a well known open source cluster computation system, for large scale data processing. If you are into Big Data and Machine Learning, Apache Spark may not need any introduction.

Its capabilities include In-memory processing, Distributed SQL Analytics, Real Time stream processing, Graph processing, Machine Learning, support for several programming languages and many more. 


"What happens under the hood, when we execute a Spark application?".  

thinking?????







This is a very common question, which crops up in every Apache Spark user's mind.

If you have the same question, I'll answer this using Spark SQL by executing one of the most common data processing operation i.e. "Join".

Spark being a vast technology, it is nearly impossible to cover all of Spark's details in a single article. And we all learn something new, every time we use a technology to solve a new challenge. However, the details I'll cover here, should be enough to give you an idea of what goes on behind the scenes in a Spark application. 


Prerequisite - This article is going to be technical and would uncover the deeper details of a Spark application. Hence some basic familiarity with Spark and distributed processing, is a prerequisite. 
Though if you are new to Spark, I will cover some fundamentals of Spark in the "Spark fundamentals" section of this article.


Let's get started ðŸš€ 

Let us consider a company named A2ZMoney. A2ZMoney provides online financial services such as money transfer, business accounting and tax filing. 
A2ZMoney is completely web based and has its customer base globally, with thousands of businesses signed up to use its services.


Business use case: 

A2ZMoney wants to grow its revenue. And to grow its revenue, it is laser focused on achieving the following 2 goals:

1. Increase its mobile app usage. To achieve this goal, A2ZMoney wants to convert its desktop users to mobile app users. As mobile app usage leads to more engagement and hence more business.

2. Send promotional offers to its users, who are already on mobile platform. These promotional offers would lead to more transactions and hence generate more revenue. 

To fulfill these two goals, A2ZMoney first would like to know about its customers and most importantly the devices they use. This would help it to target customers accordingly. 

So the business requirement is to fetch the customers and the corresponding device used by them. 
Data:

We'll use the following two datasets, one with the details of customers(business) and the other with the details of devices used by them.

 Business Accounts data (Parquet files) - It consists of the data of customer's online account they used to access services offered by A2ZMoney. The schema of this dataset though consists of several columns, but the key column of interest for us is business's accountId. 

Device data (Parquet files) - It consists of the details of devices used by customers(business). Primary columns of interest are business's accountId, deviceId, date_of_use(date on which the device was used).

To fetch the required customer and device details, one of the very first approach would be to join the business and device datasets. 


Infrastructure we'll use:

We'll use AWS Cloud for this exercise.

Processing Cluster - EMR(v5.12.1), 5 node cluster of r4.8xlarge instances.

Data storage - S3


Datasets location in S3:

I have created a dedicated S3 bucket named spark-buckt to load these datasets:

Data files paths in S3:

business_account -> s3://spark-buckt/src/business_account/
business_device -> s3://spark-buckt/src/business_device/

Note - While reading this article, if any time you need better image resolution, please click on images to enlarge.
Click on image to enlarge












Some data analysis before performing join:

Spark has a concept of dataframes(similar to Pandas dataframe) which is a distributed collection of data organized into named columns. Hence to perform any processing on these two datasets present in S3, we'll first create 2 dataframes on top of each. 

But before we can create a Spark dataframe, we need a Spark Session object which is the entry point to all Spark functionalities and is the first key entity which should be created. Below in the Application Code section, you can find the application code which shows the creation of Spark Session and data frames on our business accounts and device data. 

Before processing the data through our application, let us first count the number of records in our two dataframes separately in a notebook. I am using Zeppelin notebook for achieving this, using the read transformation and count action of Spark as follows. We'll learn about Spark transformation and action in the next section called Spark fundamentals:

 Business_account - count ~ 10 million


Business_device - count ~ 3 million


Now we need to join these two datasets, to retrieve the customer details and the device used by them. The Spark application code is as follows:


Application code:


Click on image to enlarge


Before we execute this spark application, lets understand the code. 

We first create two data frames, one for business and the other for device datasets stored in S3. Then we perform joins on these two data frames, on matching join key accountId and then write the output data files back to S3.


Spark fundamentals:

Spark works on the concept of lazy evaluation using transformations and actions. 

Transformation - An operation which transforms a dataset and produces a new dataset. In our code join is that transformation.

Action - An action is an operation which performs some computations and returns a result back. In our code write is that action.

Transformations are always lazy, meaning they do not apply their computation until an action is executed or there is a need for some data to be returned. 




To achieve this lazy evaluation, Spark creates a directed graph called DAG (Directed Acyclic Graph) behind the scenes. A DAG is a directed graph with no cycles or loops. 
Directed Acyclic Graph

In a Spark DAG, vertices reflect the data and edges reflect the operations performed on that data. 

A DAG is entirely logical and Spark does not materialize a DAG until an action is performed. In our code, write() is that action, which triggers the materialization of our application's DAG. We'll look at the DAG shortly to understand the details.

Every action triggers a Spark job. A job gets further subdivided into sets of tasks called stages. The DAG gives us the details of the stages. A stage has tasks working on the colocated data partitions and across stages the data travels over the network.

Both these datasets are larger than 10 MB in size, hence by default this join would be executed by Spark as Sort Merge Join.

Why is it so - Because the default maximum size of any table to participate in a broadcast hash join is 10 MB as shown below(for Spark v2.3.0).


Click on image to enlarge








Let us now look at the Spark application execution details.


Execution details of application:


 Execution time = 47s(as shown below):
Click on image to enlarge



Click on image to enlarge


As we can see, the last job corresponding to parquet action took most of the execution time(31 s). We'll dive into the details of this Job and analyze the stages:

Click on image to enlarge


As shown above, this job executed in 3 stages with the exchange phases doing the shuffling of data over the network, as required for the join operation. 

The first two stages performs the shuffle write for the respective two business account and device datasets. The last stage reads all of the shuffled data as written in the previous two stages and performs the join. Lets take a look at what exactly is happening in these stages by opening the query plan. 





If you are familiar with Map Reduce, then this would be easy to understand. 

For this join, the data of these two datasets - business_account and business_device first gets scanned and mapped on the join key column accountId. Then in the exchange phase the data is hash partitioned on the join key and in the sort phase, it is sorted on the hash partitioned join key columns. Then once the required partitioning and sorting is done, the data from the two required tables are joined on the join key accountId, in the SortMergeJoin phase(inner join here). 

Then in the final project phase the final required output data is fetched from this result. Finally the output data file of join result is written in parquet format to the S3 output location(as shown below).



Click on image to enlarge




I hope through this article, you were able to get some understanding of the fundamentals of Spark and how Spark engine formulates the DAG and translates and performs the computation.

   Thanks for taking the time to read this article.


Big Data, Cloud(AWS), Graph and Machine Learning professional.

Comments

  1. ITOctober 8, 2019 at 11:38 PM

    I like your post very much. It is very much useful for my research. I hope you to share more info about this. Keep posting Spark Training

    ReplyDelete
    Replies
    1. Akshay AgarwalMarch 24, 2020 at 7:43 PM

      Thank you IT. I'll surely be posting more articles around Big Data processing.

      Delete
  2. UnknownJuly 6, 2020 at 10:57 PM

    This is great post.

    ReplyDelete

New comments are not allowed.

Popular posts from this blog

UPSERT in Hive(3 Step Process)

By
Image
In this post we'll learn an efficient 3 step process, for performing UPSERT in hive on a large size table containing entire history. Just for the audience not aware of UPSERT - It is a combination of UPDATE and INSERT. If on a table containing history data, we receive new data which needs to be inserted as well as some data which is an UPDATE to the existing data, then we have to perform an UPSERT operation to achieve this. Prerequisite  – The table containing history being very large in size should be partitioned, which is also a best practice for efficient data storage, when storing large volume of data in any Big Data warehouse. Business scenario  – Lets take an example of click stream data of a website, as gathered from different browsers of visitors who visited the website. The site_view_hist table contains the clicks and page impressions counts from different browsers and the table is partitioned on hit_date(the date on which the visitor hitted or visited the websi...
Read more

Parquet tools utility

By
Image
It is a well known fact, that parquet format is a binary format. And for humans, reading binary data is not as easy as opening a text file and understanding its contents. But no worries, today we'll learn how to read a parquet file . If you would like to understand all the internal details of a parquet file , you can please refer my previous article here . In this article I have tried to explain all the inner storage details of Parquet and answered most of the questions around its usage, efficiency and performance.                                                                                Parquet tools - As we know parquet is a binary format, we need an interpreter to translate its contents so that we can understand them. And this is what parquet-tools  utility project does...
Read more

Hive - Merging small files into bigger files.

By
Image
Since Hadoop's inception, we have learnt that it is good for processing small number of large files, instead of large number of small files. Part of the reason pertaining to this behavior is, its MapReduce Paradigm which works on splits of input data.  In our day to day data processing, there can be various situations where our processes can produce large number of small files. Assume a process generated output data of 300 MB, but this data is distributed in approximately 3000 files of 99 KB each. Today we'll learn how to merge such large number of small files into bigger files. Before that let us quickly understand the problems, such large number of small files can cause. Problems posed by large number of small files -   1.   I f we store the data of this table in GZIP format(3000 files each of 99KB), then a downstream process running a hive query(MapReduce job) on this data, would spin up 3000 mappers to process individual splits for each file, as the GZIP format ...
Read more

Parquet File format - Storage details

By
Image
Columnar storage has revolutionized Big data processing, since its inception.  Its power can be realized from the fact that Google Big Query, Hbase, Amazon Redshift, Azure SQL Data Warehouse and many more, all utilize columnar storage. As you are here today reading this article, it is obvious that you are curious to learn how Columnar storage internally works. Well, just stay tuned for next few minutes, as  I'll explain all the details of the  most popular columnar file format called Parquet.  We'll learn the details  by  actually opening  a parquet file and by  going deep, at the level of how things work under the hood at disc level.  We'll also learn why Parquet would save cost, when it is used as underlying file format with A WS services such as Athena . When to use Parquet format  -  Just check this less than 30 seconds conversation, going on between a Data Engineer(male) and a  BI Analyst(female) . When to us...
Read more

Skew Join Optimization in Hive

By
Image
Skew is a very common issue which most of the data engineers come across.  What is Skew - When in our data we have very large number of records associated with one(or more) particular key, then this data is said to be skewed on that key.  We'll understand this with a very simple example. Think about world's population data table, where each record is of one person and the number of records equals to total world population. As we all know China and India, each accounts for around 17-18% of world's population, hence such population table is referred to as skewed on keys country=China and country=India. If you focus on the following pie chart of world's population distribution by country, then this would make exact sense. Problem statement  - Assume we have a table which tracks the online visits to different online websites. In this table amazon.com  being very popular,  has 1 Billion rows whereas other not very popular sites ( www.abc.com , w...
Read more

Apache Spark - Explicit Broadcasting Optimization

By
Image
Join operation is an indispensable part of majority of Big Data Projects. If you are using Apache Spark for your Big Data processing and using join operation, in this article I'll explain a strategy to optimize joins. The technique I'll explain is how to explicitly broadcast a table, in any Spark join operation and convert the join operation to Broadcast Hash Join. Why Broadcasting - W hen we perform a join operation in Spark SQL, b roadcasting proves very efficient in reducing data shuffling and hence serialization and deserialization of data over the network, which happens during a Sort Merge Join operation. If you haven't read my previous article on Spark's Broadcast Hash join, I highly recommend you to first go through that. This would provide you most of the deeper details of Spark's Broadcast hash Join. You can please find it here :- Broadcast Hash Join - By Akshay Agarwal Business use case  -  To explain this optimization, let's take the business...
Read more

Spark Optimization - Bucketing

By
Image
Complex data computation is a part of every Big Data Project.  Do you have a business scenario requiring complex join on data having billions or trillions of values?  If you are using Apache Spark, stay tuned for next few minutes, as this article will address this expensive join problem, using Spark's optimization technique called Bucketing. Before reading this article, I recommend you to once go through my previous articles on Spark's Sort Merge Join and Broadcast Hash Join . They will set up your foundation for understanding bucketing technique. It is recommended but is not mandatory, as you would still be able to grasp the core concept. When to use Bucketing ?    For any business problem, where we need to perform a join on tables with very high cardinality on join column( I repeat very high ) in say millions, billions or even trillions and also this join needs to happen multiple times. Lets understand bucketing using the data of a hypothetical service ...
Read more

Fraud Detection - Using Graph Database

By
Image
Graph DBs have become a buzzword in recent years.  In addition to social networks and recommendation systems, fraud detection is a field where the value of graph technology cannot be understated.  In this article we'll learn how Graph technology can be used to detect fraud.  If you are new to Graph technology, and haven't read my previous publication Graph technology in plain english , I highly recommend to read that once. It will help you to understand the fundamentals of Graph technology and serve as a catalyst for your learning process.  Fraud detection According to the research published by Crowe in July 2019, global fraud losses equate to shocking US$5.127 trillion each year . Fraudsters commit monetary frauds almost every day.  What if such fraud can be detected at an early stage, through prior experience of  some common fraud patterns  or known fraudsters.  We'll look at how Graph can be used to identify one such link and how tedious it...
Read more

Apache Spark - Broadcast Hash Join

By
Image
In this technical article, we'll discuss about one of Apache Spark's efficient join technique called Broadcast Hash Join. I will explain in detail how this operation is implemented internally in Spark at DAG(Directed Acyclic Graph) level and also different phases of DAG. We'll also uncover the details of division of spark application into jobs and stages.  Data  -  To explain this join concept, I'll take customer data of a hypothetical online service provider organization with international presence. Different customers across the world using its services holds accounts with this company. Moreover the customers uses different devices to access this company's website. Hence to fetch the details of different  customers(business_accounts) and the corresponding device used by them, we'll use two datasets: Business Accounts data   -  Data consisting of details of the customer's business account, created with this service providing organizatio...
Read more