Theta Join
Preliminaries
Overview
HIVE-556请求 Hive 支持非等分联接，通常称为 theta 联接。 Theta 联接涵盖了各种非等距联接，例如\ <, <=, >，> =，\ <>，LIKE，RLIKE 和通用 UDF。
范围联接是一种特殊的 theta 联接，在时空应用中非常有用。这项工作首先将重点放在范围联接上，因为它可以说是最重要的 theta 联接。实施范围联接之后，可以相对轻松地实现其余的 theta 联接运算符。支持 theta 联接，尤其是范围联接非常重要，因为它将使 Hive 在其他用例中具有竞争力，并且与传统系统相比，可以消除缺陷。
具体用例
Geo-Location
对于 Hive 网站，移动电话服务和在线广告营销商的许多普通用户而言，今天这种用例非常普遍。用户希望将网站访问日志与 IP 地址的地理位置信息一起加入。可以将其实现为interval join。当前，此用例是通过创建执行查找的自定义 UDF 来实现的。对于大多数 Hive 用户而言，编译和部署 UDF 是容易出错的过程，而不是常见的任务。
作为此用例的一个示例，我们可以使用按国家/地区数据集划分的 Maxmind GeoIP，该记录为 79,980 条记录。考虑使用笛卡尔积将具有 5,000,000 个条目的很小访问日志的数据集连接起来，然后过滤结果。这种方法导致需要在 Map 器中过滤 399,900,000,000 个 Tuples。对 Hive 主干进行了修改，以实现 Map 端间隔连接，并且先前讨论的连接在单个主机上以 21 秒完成，而笛卡尔乘积然后进行过滤的方法运行了多个小时才被杀死。
Side-Table Similarity
该用例最初是由其创建者 Min Zhou 在HIVE-556中提出的。用户有一个带有一些条目的边表，并希望基于相似性将边表与主表连接起来。提供的示例使用的是 RLIKE 运算符，但也可以使用 LIKE 或通用布尔 UDF。
Requirements
这项工作的显着目标是 n 路 theta 联接。实现 n 路 theta 联接的算法的灵感来自于实现 2 路 theta 联接的算法。因此，n-theta 联接可以在将来的工作中实现。
Goals
Map 侧 2 路 theta 联接
减少侧 2 通 theta 联接
Specific Non-Goals
Map 侧 n 路 theta 联接
减少端 n 路 theta 联接
附加统计收集
Literature Review
Map-Reduce-Merge：大型集群上的简化关系数据处理[1]
这项工作为 Map-Reduce 添加了一个“合并”步骤，该步骤可简化关系代数运算符的表达。这很有趣，但不是立即有用的，因为它需要修改 Map-Reduce 框架，但不是立即有用的。
使用 MapReduce 进行有效的并行集相似性联接[2]
这项工作研究了一种特殊类型的集合相似性，特别是相似的字符串或位向量。这项工作可能对实现某些运算符(如 LIKE)很有用。另外，这种需要在运行时计算统计信息的方法会导致多个 Map-Reduce 作业。
使用 MapReduce 处理 Theta-Joins [3]
这项工作提出了一种 1-Bucket-Theta 算法，可以在给定一些基本统计信息(即两个关系的基数)的情况下，在单个 Map-Reduce 作业中对两个关系执行 theta 联接。这种方法也允许并行执行笛卡尔积。该工作还详细介绍了如何利用附加的 Importing 统计信息来提高效率。该方法是对两个关系的联接矩阵进行分区。
使用 MapReduce 的高效多路 Theta-Join 处理[4]
这项工作受到[3]的启发，并将方法扩展到 N 向联接。所使用的方法是对关系的超立方体进行分区。还讨论了一种将生成的许多 Map-Reduce 作业合并为一个作业的方法，其结果类似于 Y-Smart [5]。
Design
Map-side
大量的 theta 联接用例具有很好的特性，即只有一种关系是“大”的。因此，许多 theta 联接可以转换为 map-joins。当前，这些用例利用带有后联接过滤器的 Map 侧笛卡尔积。如上面的地理位置用例所述，其中一些用例(特别是范围联接)可以看到使用 theta 联接的速度提高了几个数量级。
当前，Map 端联接使用哈希 Map，并且当传入密钥与哈希 Map 中的密钥匹配时，将执行联接。为了支持范围连接，它将抽象为可插入接口。插件可以决定如何将两个键连接在一起。等式联接接口将 continue 使用哈希图，而范围联接可以使用诸如间隔树之类的数据结构。可以进行其他此类优化。例如，不等于加入条件\ <>可以使用[在 Map 上查看](http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/collect/Maps.html#filterKeys(java.util.Map, com.google.common.base.Predicate))。
Reduce-side
减少侧连接将通过[3]中所述的 1-Bucket-Theta 来实现。这需要两个关系的基数，因此必须执行减少侧 theta 联接统计。最初，如果所需的统计信息不存在，将引发异常以指示问题。初始实施后，我们可以使用一种方法来估计基数。
如前所述，位于 1-Bucket-Theta 的详细说明位于[3]。这样，对算法内部的讨论将是简短的。连接两个关系 S 和 T 可以看作是矩阵，其中 S，较小的关系在左侧，T 在右侧。
矩阵由 r(约简器的数量)划分。下面是一个示例连接矩阵，其中四个减速器 1-4 各自具有单独的颜色：
| Row Ids | T 1 | T 2 | T 3 | T 4 |
| S 1 | 1 | 1 | 2 | 2 |
| S 2 | 1 | 1 | 2 | 2 |
| S 3 | 3 | 3 | 4 | 4 |
| S 4 | 3 | 3 | 4 | 4 |
在 Map 阶段，将 S 中的每个 Tuples 发送到与 Tuples 的行 ID 相交的所有 reducer。例如，行 ID 为 2 的 STuples 被发送到缩减程序 1 和 2.类似地，T 中的每个 Tuples 被发送给与 Tuples 的行 ID 相交的所有缩减程序。例如，将具有 rowid 4 的 Tuples 发送到 reducer 2 和 4.
在 Hive 和 MapReduce 中，行 ID 并不常见。因此，我们选择介于 1 和| S |之间的随机行 ID。 S 和 1 和| T |(S 的基数) (T 的基数)。因此，减少侧 theta 联接必须知道每个关系的估计基数，并且必须启用统计信息。处理较大的关系时，随机行 ID 将导致平衡器 Importing 平衡良好。如[3]中所述，分区方案的工作方式是，如果一个关系比它的对小得多，则较小的关系将被全部 Broadcast 为两个 reducer。因此，对于小关系会发生的随机偏斜实际上不会影响算法。此外，在 Hive 中，如果关系很小，则联接将转换为 Map 侧联接，并且不使用 1-Bucket-Theta。
Mapper
在 Map 器中，将初始化联接矩阵，选择一个随机行 ID，然后将为与该行 ID 相交的每个化简器发出 Tuples。 Hive 已经有一种机制可以为特定的 Tuples 设置哈希码，可以在此处重复使用。另外，将需要对 Tuples 进行排序，以使用于 S 的 Tuples 首先到达减速器。幸运的是，Hive 已经通过 JoinReorder 类实现了这一点。
Reducer
约简器非常简单，它缓冲了 S 关系，然后对接收到的每个 TTuples 执行请求的联接。