Tricks to improve computational performance of JOIN operation more than 10x

Hello, my name is Sourav Saha, a member of NEC Digital Technology Research and Development Laboratories. This is an article for [NEC デジタルテクノロジー開発研究所 Advent Calendar 2023](https://qiita.com/advent-calendar/2023/nec-dt-labs) **Day 11**, where I am going to discuss several possible ways to improve some commonly used Join queries during complex data analysis.

# Background
`Join` is one of the frequently used operations in table data analysis, involving two or more tables to be combined based on some common keys for further analysis. The computation cost grows with the growth of the input table sizes. There are many research artifacts available to optimize a `Join` algorithm. In today's article, I will talk about some commonly used patterns involving join operations, which can be optimized more than 10x by some expert-level code modifications. It is assumed that the readers are aware of the syntaxes of pandas [merge](https://pandas.pydata.org/docs/reference/api/pandas.DataFrame.merge.html) method along with [different type of join operations](https://www.geeksforgeeks.org/different-types-of-joins-in-pandas).

## Optimization Examples
Let's discuss with some problem statements!

Below are the input tables for three different entities, `supplier`, `nation`, and `region` 
(these are the part of the input tables from [TPC-H](https://www.tpc.org/tpch) SF-1 benchmark).

![data.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2917078/1bbd8eee-fe44-8cd9-8473-48b3f365b11c.png)

### **Problem 01:**
<font color=green> **Let's try to capture the names and phone numbers of the suppliers who operate in the `AMERICA` region.** </font>


From the above figure, it can be noted that the `supplier` and the `nation` tables are linked with a common key, `n_key`, whereas, the `nation` and the `region` tables are linked with another common key, `r_key`. Hence to get the information on suppliers operating in the `AMERICA` region, we would need to merge these three tables using the common keys. So, the very simple implementation for this query might look like:

```python
def ver_01(supplier: pd.DataFrame, 
           nation: pd.DataFrame, 
           region: pd.DataFrame):
    merged = supplier.merge(nation, on="n_key") 
                     .merge(region, on="r_key") 
    filtered = merged[merged["r_name"] == "AMERICA"]  
    return filtered[["s_name", "s_phone"]]                              
```

The same is depicted in the following figure:

![flow_1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2917078/38c80050-2515-341d-97f6-cd2c68f2c3a3.png)

<font color=blue> :point_right: Can you guess the performance issues with the above implementation? </font>
⇒ Yes, the very first bottleneck is in the **_order of join queries._**

The `supplier` table has 10000 rows, whereas the `nation` table has 25 rows (covering 25 unique nations), and the `region` key has only 5 rows (covering 5 unique regions).

Thus when joining the `supplier` table with the `nation` table, it will trigger an inner-join operation as follows:
- (10000 x 5) **inner_join** (25 x 3) -> (10000 x 7)

joining the same with the `region` table will again trigger another inner-join operation as follows:
- (10000 x 7) **inner_join** (5 x 2) -> (10000 x 8)

Both of these join operations depend on the size of the `supplier` table, which will significantly increase the computational cost of the above method with the increase in supplier numbers in the `supplier` table.

Therefore, let's look for an alternative solution!
Since `region` and `nation` tables are relatively smaller in size, those can first be joined to address the above problem to some extent. So, let's give it a try!

```python
def ver_02(supplier: pd.DataFrame, 
           nation: pd.DataFrame, 
           region: pd.DataFrame):
    merged = nation.merge(region, on="r_key")
                   .merge(supplier, on="n_key") # changes in join-order
    filtered = merged[merged["r_name"] == "AMERICA"]  
    return filtered[["s_name", "s_phone"]]
```

The same is depicted in the following figure:

![flow_2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2917078/157cc3f2-c5b2-900c-8847-b06cf9091174.png)

It can be seen that when joining the `nation` table with the `region` table, it will trigger an inner-join operation as follows:
- (25 x 3) **inner_join** (5 x 2) -> (25 x 4)

joining the same with the `supplier` table triggers another inner-join operation as follows:
- (25 x 4) **inner_join** (10000 x 5) -> (10000 x 8)

The first join operation can be done much faster due to the very small sizes of the input tables. Hence, it can significantly improve the overall performance of the entire query. 
So, the very first thing to be noted is that <font color=salmon>**_the order of join operation matters when joining more than two tables._**</font> It is always preferable to join the smaller tables before joining the larger tables.

The cost of the second operation will still be high and will grow along with the growth of the `supplier` table. So let's try to improve that.

The `supplier` table contains the details of all the suppliers irrespective of where they operate, but since our objective is to capture <ins>only those suppliers, who operate in the `AMERICA` region</ins>, we can indeed optimize the flow of the above query.

If we can simply join the `region` table with the `nation` table only considering the `AMERICA` region, and then join with the `supplier` table, we can significantly reduce the cost for the second join operation, as depicted in the following figure:

![flow_3.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2917078/792275e9-2d6a-ed1f-ab26-8cc6949d3456.png)

※ <ins>**Some facts about the data**</ins>:
- the joined table (america_region_nat) resultant from joining the `nation` and the `region` tables specific to the `AMERICA` region has only 5 rows and 4 columns.
- there are 2036 supplier entries for the `AMERICA` region in the `supplier` table.

Hence due to the inner-join of the `supplier` table with the `america_region_nat` table, we can optimize the size of the resultant table as follows:
    - (5 x 4) **inner_join** (10000 x 5) -> (2036 x 8)

Well, now let's consider how to join the `nation` and the `region` tables only for the `AMERICA` region. There are possibly two ways of doing the same:

```python
def merge_filter(nation: pd.DataFrame, 
                 region: pd.DataFrame):
    merged = nation.merge(region, on="r_key")
    return merged[merged["r_name"] == "AMERICA"] # filter-after-join


def filter_merge(nation: pd.DataFrame, 
                 region: pd.DataFrame):
    america_region = region[region["r_name"] == "AMERICA"]
    return nation.merge(america_region, on="r_key") # join-after-filter
```

The same is depicted in the following figure:

![merge-filter-opt.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2917078/d5d76fe5-4b2f-3679-0018-dd4f9eb4f534.png)

It is visible that `filter_merge` will make it more efficient since it reduces the target table sizes for the `join` operation. So, the second important point to be noted is that <font color=salmon>**_the order of join-filter operation matters._**</font> It is always preferable to perform the `join` operation followed by the `filter` operation.

So the overall query will look like this:
```python
def ver_03(supplier: pd.DataFrame, 
           nation: pd.DataFrame, 
           region: pd.DataFrame):
    america_region = region[region["r_name"] == "AMERICA"] # filter
    merged = nation.merge(america_region, on="r_key") # smaller-join
                   .merge(supplier, on="n_key")  # larger-join
    ret = merged[["s_name", "s_phone"]]  
```

:point_right_tone1: Wait! There is still room for improvement, as we <ins>only need the `name` and `phone` information for the suppliers</ins> operating in the `AMERICA` region.

Generally data frames are columnar data structures and performing join on the entire table (including all columns) might degrade the performance when we need only a specific field information from the joined table. For example, if we subset only the required columns from the input tables for the second join operation as follows:

```python
def ver_04(supplier: pd.DataFrame, 
           nation: pd.DataFrame, 
           region: pd.DataFrame):
    america_region = region[region["r_name"] == "AMERICA"]
    america_region_nat = nation.merge(america_region, on="r_key")
    america_nation_keys = america_region_nat[["n_key"]]  # keeping only required column for joining
    supplier_name_phone = supplier[["s_name", "n_key", "s_phone"]]  # keeping only required columns
    merged = supplier_name_phone.merge(america_nation_keys, on="n_key") # faster join on reduced data
    ret = merged[["s_name", "s_phone"]]
```
we can further reduce the cost of the overall query computation as depicted in the following figure:

![flow_4.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2917078/3130432b-e7e0-9407-0958-8ba72eb6a336.png)

So, another important point to be noted is that <font color=salmon> **_Subsetting the required columns before performing join matters when there are many columns in the input tables to be joined, but a few of them are required from the joined result._** </font>

The following table shows the evaluation of the above four versions for different supplier sizes using `pandas 1.5.3` (the execution times are in milliseconds):

![eval_01.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2917078/ef66e782-f85a-9308-12a3-c8b6b12eec46.png)
 
### **Problem 02:** 
<font color=green> **Let's consider the following table and find the rows that contain the `key`-wise minimum value for the `x` column and maximum value for the `y` column.** </font>

![prob_02.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2917078/f1304751-6481-bbe6-481b-f9fe6ec17fe1.png)

The very basic approach to solve the problem is as follows:
- x_min: perform key-wise min of `x` column
- y_max: perform key-wise max of `y` column
- join df with x_min and with y_max
- filter rows from resultant table where the value of `x` matches with the value of `x_min` and the value of `y` matches with the value of `y_max`
- extract the target columns

```python
def prob_02(df: pd.DataFrame):
    t1 = df.groupby("key").agg(x_min = ("x", "min"))
    t2 = df.groupby("key").agg(y_max = ("y", "max"))
    merged = df.merge(t1, left_on="key", right_index=True)\
               .merge(t2, left_on="key", right_index=True)
    ret = merged[(merged["x"] == merged["x_min"]) & (merged["y"] == merged["y_max"])]
    return ret[df.columns]
```

The same is depicted in the following figure:

![merge-groupby-org.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2917078/8598590e-3886-2464-d318-6e053b93bbb6.png)

In the above example, we can find multiple join operations, and the problem with `join-order` is to be noted here as well. The tables `t1` and `t2` contain group-wise aggregated results of `df`. If there are a smaller number of key groups (e.g. 10) in the input table `df` in comparison to its size (e.g., 100000), then joining `df` with `t1` will cause significant performance issues. Hence, as discussed previously <font color=salmon>**_the ideal solution should join `t1` with `t2` first, before joining with `df`_**</font> as depicted in the following figure:

![merge-groupby-opt.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2917078/89ae2682-c83d-f836-08ae-47781fd17b00.png)

Now, there exists one more performance issue with the second join operation.
Joining with the "key" column will result in a large data frame when the input `df` table has a large number of rows. Hence, joining with the `key` column and then filtering on the `x_min` and `y_max` columns will involve significant computational costs. Instead, <font color=salmon>**_it is recommended to perform multi-key-equi-join in this case_**</font> as depicted in the following figure:

```python
def opt_prob_02(df: pd.DataFrame):
    t1 = df.groupby("key").agg(x_min = ("x", "min"))
    t2 = df.groupby("key").agg(y_max = ("y", "max"))
    t1_t2 = t1.merge(t2, left_index=True, right_index=True).reset_index() # join on aggregated results
    ret = df.merge(t1_t2, left_on=["key", "x", "y"], right_on=["key", "x_min", "y_max"]) # multi-key equi-join
    return ret[df.columns]
```

![multi-key-merge.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2917078/1e0ce800-318c-5826-7b55-d0782f1218d3.png)

# FireDucks - Compiler-accelerated DataFrame Library

:speaker: We at NEC, have recently [released](https://www.nec.com/en/press/202310/global_20231019_01.html) a high-performance data analysis library, named `FireDucks` which is highly compatible with pandas and accelerated with different layers of optimization. It can outperform pandas even on CPU-only systems. Some of the above-explained performance bottlenecks can be auto-detected by the FireDucks compiler and automatically optimized according to the above-mentioned strategies. Whereas, development work is in progress for some of the other strategies to be automatically optimized and will be released in the future version of FireDucks. Please check out one of my [articles](https://qiita.com/qsourav/items/e87f25c4b307391d784a) explaining key features of `FireDucks`, along with its different layers of optimization to realize <font color=green>**_its potential to be used as a drop-in replacement for pandas._**</font>

Nevertheless, the current version itself is powerful enough to auto-tune your program using 
the critical domain-specific intelligence it is trained with. Hence, when [evaluating](https://fireducks-dev.github.io/en/docs/benchmarks/benchmarks/) with several performance-critical queries in the TPC-H benchmark, we could achieve <ins>**_up to 38x performance gain_**</ins> when using FireDucks.

# Wrapping-up
Thank you for reading so far! :bow: :gift: :rose: 

To summarize, we discussed different optimization strategies for commonly used `Join` operations in complex data analysis. Effective code modification using the explained strategies can significantly reduce your data analysis time with pandas. <font color=green>**_However, when switching to the compiler-accelerated FireDucks library, it can automatically optimize many of such patterns without any need for expert-level code changes._**</font> 

We recommend getting it installed using `pip` and trying to use it in your pandas application to enjoy its benefits. We are continuously striving towards improving its performance and releasing the same at [frequent intervals](https://fireducks-dev.github.io/en/docs/release-note/release-note/). Please stay tuned with [us](https://fireducks-dev.github.io/en/docs/about-us/about-us/) and keep sharing your valuable feedback on any execution issues you may face or optimization requests you may have. We are eagerly looking forward to hearing from you!