干货|Spark优化之高性能Range Join

作者|张兴超

编辑|林颖

供稿|ADI Carmel Team

本文共3884字，预计阅读时间10分钟

导读

Carmel是eBay内部基于Apache Spark打造的一款SQL-on-Hadoop查询引擎。通过对Apache Spark的改进，我们为用户提供了一套高可用高性能的服务，以满足eBay内部大量分析型的查询需求（如今单日查询量已超过30万）。

在生产中，我们发现有很多包含非等值连接的查询。因为BroadcastNestedLoop的实现，这些查询会产生效率问题，而变得非常耗时。本文就非等值连接中的Range Join进行分析，并重点介绍了我们对此所做的优化。

1 背景

Background

Range Join 发生在两个表的连接（Join）条件中包含“点是否在区间中”或者“两个区间是否相交”的时候[1]。过去一周，我们的OLAP引擎（Spark）中，检测到7k多条这样的SQL查询语句，在所有包含非等值连接的SQL中占比82.95%（如下图所示）。

在现在的Spark实现中，Range Join作为一种非等值连接，是通过BroadcastNestedLoop（嵌套循环）的方式来实现的，时间复杂度为N*M，其中N为Stream表的行数，M为Build表的行数。当两个表都很大的时候，BroadcastNestedLoop效率不高的缺点就会变得愈发明显，连接过程可能会花费数个小时来完成，有的甚至无法给出结果。

比如下图中的两个例子：

案例1：数据分析师希望根据150w左右的用户登录IP，来查询用户所在的国家和地区。这就需要User Login IP表和eBay Data Warehouse（以下简称DW）中IP Range Lookup表（>1200w行）来进行连接，这在Spark引擎中需要4小时才能返回。

(点击可查看大图)

案例2：这个属于更为常见的案例，数据分析师会经常根据日期来查询相应时间段的关联数据，如下图所示，在我们系统中同样发现了很多耗时的查询语句（Query）。

(点击可查看大图)

无论从用户等待的耗时，还是系统资源的使用角度来看，这都是不能接受的。

本文中涉及的方案将在Spark中支持Range Join，以解决现有实现中效率低、耗时长的问题。结合Spark社区对Range Join的讨论[2-3]，我们对原始方案进行了升级和重写，并成功应用于eBay OLAP的生产实践中。

2 Range Join的定义

Definition of Range Join

典型的Range Join主要有以下两种形式[1]：

1）点在区间中

2）两个区间相交

Range Join的优化可以作用于有以下特点的连接上：

1）连接条件中包含“点在区间中”或者“两个区间重叠”；

2）连接条件中的所有值为以下类型：数值（Integral、Floating Point、Decimal）、日期（DATE）、时间戳（TIMESTAMP）或者空值（NULL）；

3）连接条件中的Range值有相同的类型。如对于Decimal类型，要有相同的长度和精度；

4）连接类型可以是内连接（INNER JOIN）、交叉连接（CROSS JOIN）、左外连接（LEFT OUTER JOIN）和右外连接（RIGHT OUTER JOIN）。

3 方案设计

Project Design

我们对原始方案进行了升级和重写，主要包含以下几个步骤：

1）基于Build表创建一个Range Index数据；

2）Broadcast这个Index数据到Stream端；

3）Stream表基于这个Index进行连接匹配。

和传统的嵌套循环连接（Nested Loop Join）相比，这会将连接的时间复杂度从n大幅降低为log(n)，其中n是Build表的行数。

下图简要说明了该方案和传统Nested Loop Join的区别：Range Join的实现重点在构建Range Index，然后基于Index进行数据连接。

(点击可查看大图)

下面我们将分别阐述Index的构建过程和连接时的查找过程。

3.1 基于Range构建的查询方案设计

如下表所示，我们现有一个Range表（原始数据是非排序的，为了更好的展示例子，这里按照第一列做了排序），含有6行数据：

基于上述这个表，我们建立了一个Range Index，如下图所示，其数据结构包含5个部分：

1）Keys

对表中的Range列（即range_start 和 range_end）排序，并做Distinct后组成的一个有序数组。

2）Offsets

是一个有序数组。其下标Index和“Keys”中的下标Index相同，其值表示小于“Keys”中相同Index对应值的Rows数，同时也表示“activatedRows”的下标Index。

3）activiatedRows

记录了原始表中的数据。

4）activeRows

记录了和相应Key有重叠的Rows。

5）activeNewOffsets

主要用于边界情况检查。

(点击可查看大图)

3.1.1 Range Index的创建

Index的创建需要对Build表做一些预处理，过程如下：

1）基于Rows创建Range Event，一个包含Range的Row往往可以产生两个Range Event。比如（range_start, 0, (row, index)）和（range_end, 1, (row, index)），其中0和1表示Range的开和闭，row表示原始Row的值，index表示原始Row的index；

2）对Range Event按照三元组的前两个值进行排序；

3）循环排序好的Range Event填充Range Index，比如“Keys”（为Build表中range start和range end唯一不同的值）、“activated Rows”（等价于原始Build表中的Rows）以及“Offsets”（用于映射“Keys”和“activatedRows”）；

4）对于activeRows：

如果是Range Event起始，则把当前行加入到“CurrentActiveRows”；

如果是Range Event结束，则把当前行从“CurrentActiveRows”中移除；

如果本次循环的Key与上次循环的Key不同，则把“CurrentActiveRows”写入“activeRows”。

3.1.2 Range数据的查找

我们对上述Range表基于Range Index进行查找。

(点击可查看大图)

比如，对于一个Point(108)，从上面的示意图中可以直观地得到可能匹配到的Rows——R1和R2。而对于一个Range(150, 310)，从示意图中也可以得到可能匹配到的Rows——R3和R4，那么是如何通过算法来进行查找的呢？

1）点查找一个数据（如Point(108)）

A. 采用二分查找算法，在“Keys”中找到比108小又最接近的Key：3->100；

B. 在“activeRows”中找到下标3对应的Row：R1和R2；

C. 得到最终结果为R1和R2。

2）匹配一个Range（如Range(150, 310)）

A. 采用二分查找算法，在Keys中找到比150小又最接近的Key：6->140；

B. 在“activeRows”中找到下标6对应的Row：R3；

C. 在“Keys”中找到比310小又最接近的Key：8->300；

D. 结合步骤B中的下标“6”，我们要找到比6大而又小于C中“8 1”对应的Rows。于是，在Offsets中获得下标区间[6 1, 8 1]，其对应的值为：(6 1)->4,(7 1)->4,(8 1)->5，即得到左闭右开的区间[4, 5)；

E. 在“activatedRows”中根据区间[4, 5)找到对应的Row：R4；

F. 得到最终结果：R3和R4。

3.2 基于Point构建的查询方案设计

实践中，我们发现非Range表（不包含Range）一般比较小，是可以进行Broadcast的。对于这种情况，我们也可以建立只包含点的Range Index。比如下表所示的Point表（同样原始数据是非排序的，为了更好的展示例子，这里按照第一列做了排序），含有7行数据：

3.2.1 Range Index的创建

我们对Point列构建Range Index，得到的如下所示的Index数据。与Range表生成的Range Index不同的是：这次的Range Index中只有Keys、Offsets和activiatedRows被填充了数据。

(点击可查看大图)

3.2.2 Range数据的查找

我们对上Point表基于Range Index进行查找。

(点击可查看大图)

比如，对于一个Range(300, 600)，从以上示意图中，可以直观地得到可能匹配到的Rows：R3、R4和R5。以下是通过算法进行的查找过程：

A. 采用二分查找算法，在“Keys”中找到比300小又最接近的Key：3->200；

B. 在“Keys”中找到比600小又最接近的Key：5->500；

C. 结合步骤A中的下标“3”，我们要找到比3大而又小于步骤B中“5 1”对应的Rows。于是，在Offsets中获得下标区间[3 1, 5 1]，其对应的值为：4->3,5->4和6->6，即得到左闭右开的区间[3, 6)；

D. 在 “activatedRows”中对应的下标区间[3, 6)找到对应的值：R3、R4和R5；

E. 得到最终结果：R3、R4和R5。

4 性能对比

Performance Comparison

4.1 时间复杂度对比

相比嵌套循环连接（Nested Loop Join），时间复杂度的变化为：

其中，N = 大表中的Records数量；M = 小表中的Records数量；2 = 我们需要在Range Index分别查找下限和上限。

如12M*1M→12M*2*20，理论上可以节省99.996%的计算量。

4.2 优化后的SQL查询时间对比

我们可以看到经过优化以后（如下图所示），案例1“IP Range”可以在26秒内完成，节约了99.8%的时间，而案例2“Date Range”也节约了93.9%的查询时间。如此看来，基于Range Index数据进行的连接，表现得非常令人满意。

(点击可查看大图)

4.3 Spark DAG对比

相比于传统的BroadcastNestLoopJoin算子（如下表所示），我们引入了一种新的BroadcastRangeJoin算子来进行连接的计算，同时选择BroadcastRangeExechange来代替BroadcastExechange，用于基于Build表数据来创建RangeIndex。