Docs4dev
Docs
apache-hive / 3.1.1 / reference / Hybrid_Hybrid_Grace_Hash_Join__v1.0.html

Overview

我们提出了一种增强的哈希联接算法，称为“混合混合宽限度哈希联接”。我们可以从此功能中受益，如下所示：

  • 即使估计的内存要求略有错误，查询也不会失败。

  • 当哈希表增长时，可以避免昂贵的垃圾回收开销。

  • 即使小表无法容纳在内存中，也可以使用 Map join 运算符执行联接执行，因为从构建和探针端溢出一些数据仍然比必须洗净大的事实表便宜。

该设计基于 Hadoop 的并行处理能力和大量可用内存。

有关这项工作的当前状态，请参见HIVE-9277。

Scope

这种新的连接算法仅适用于 Tez。它当前不支持 Map Reduce。

表示法和假设

目的是计算标记为 R 和 S 的两个关系的等联接结果。我们假设 R 是基数较小的小表，而 S 是基数较大的大表。

哈希联接算法简介

简单哈希加入

也称为经典哈希联接，当 R 的哈希表完全适合内存时使用。

通常，此处描述的所有哈希联接算法都有两个阶段：构建阶段和探测阶段。在构建阶段，基于小表 R 中的连接列将哈希表构建到内存中。在探测阶段，按 Sequences 扫描大表 S，并针对 S 的每一行探测哈希表用于匹配行。如果找到匹配项，则输出该对，否则从 S 删除行并 continue 扫描 S。

当 R 的哈希表不能完全适合内存时，R 的哈希表的仅一部分将首先放入内存，然后针对部分哈希表扫描 S。在对 S 的扫描完成之后，将清除内存，并将 R 的哈希表的另一部分放入内存，然后再次扫描 S。如果哈希表有更 Multipart，则此过程可以重复多次。

GRACE 哈希加入

显然，当小表 R 的大小比内存大得多时，我们最终会在内存中一张一张地装载 R 的许多局部哈希表，并且大表 S 被扫描了多次，这非常昂贵。

GRACE 哈希联接使对大表的扫描次数从许多次降到了两次。一个用于分区，另一个用于行匹配。同样，小桌子也将被扫描两次。

这是详细的过程。

  • 扫描小表 R，并在扫描过程中使用哈希函数将行分布到不同的输出缓冲区(或分区)中。每个输出缓冲区的大小应指定为尽可能接近内存限制，但不能超过该限制。完全扫描 R 之后，所有输出缓冲区都将刷新到磁盘。

  • 同样，大表 S 的扫描，分区和刷新方式也相同。此处使用的哈希函数与上一步相同。

  • 将 R 的一个分区加载到内存中并为其构建哈希表。这是构建阶段。

  • 对 S 的相应分区的每一行进行哈希处理，并在 R 的哈希表中查找匹配项。如果找到匹配项，则将对输出到结果，否则，continue 当前 S 分区中的下一行。这是探测阶段。

  • 对 R 的分区和 S 的探测分区重复加载和构建哈希表，直到两个都用尽。

可以看出，该算法中还有额外的分区步骤(1 和 2)。其余步骤与经典哈希联接相同，即构建和探测。这里的一个假设是 R 的所有分区都可以完全适合内存。

混合 GRACE 哈希加入

它是 Classic Hash Join 和 GRACE Hash Join 的混合体。这个想法是在分区阶段为 R 的第一个分区构建一个内存中的哈希表，而无需将该分区写入磁盘。类似地，在对 S 进行分区时，不必将第一个分区放入磁盘，因为可以直接针对 R 的内存中第一个分区进行探测。因此，在分区阶段结束时，将第一对 R 和 S 的分区已经完成。

与 GRACE 哈希联接相比，混合 GRACE 哈希联接具有避免在分区阶段将 R 和 S 的第一个分区写入磁盘并在探测阶段再次读回它们的优点。

Hash 加入 Hive

也称为复制联接，Map 侧联接或 mapjoin。当数据的一侧足够小以适合 Map 器的内存时，可以将其复制到所有 Map 器，并且仅在 Map 阶段执行连接。不需要还原阶段。

{#HybridHybridGraceHashJoin,v1.0-Motivationfor"HybridHybridGRACEHashJoin"}“ Hybrid Hybrid GRACE Hash Join”的动机

Hive 中哈希联接的当前实现是经典哈希联接，它只能处理小表可以完全容纳在内存中的情况。否则将无法执行哈希联接。此功能试图通过使散列连接更加通用来解除该限制，以便即使小表的大小大于内存，我们仍然可以以一种优雅的方式进行散列连接。

显而易见，GRACE Hash Join 在分区阶段将主内存用作暂存区，它无条件地从磁盘上扫描两个关系，然后进行分区并将其放回磁盘(Hybrid GRACE Hash Join 放少了一对)，最后将它们读回查找匹配项。

此功能试图尽可能避免不必要地将分区写回到磁盘，并且仅在必要时这样做。这个想法是充分利用主存储器来保存哈希表的现有分区。

影响该算法性能的关键因素是数据是否可以均匀地分布到不同的哈希分区中。如果我们偏斜了值，这将导致一些非常大的分区，则需要一个额外的分区步骤才能将大分区划分为多个。这可以递归发生。有关更多详细信息，请参见下面的递归散列和溢出。

Algorithm

像其他哈希联接一样，有一个构建阶段和一个探测阶段。但是有几个新的术语需要定义。

  • 划分 。与其将小表的所有键放到一个哈希表中，还不如将它们的哈希值放到许多哈希表中。这些哈希表称为分区。分区可以在最初创建时位于内存中，也可以在内存用完时溢出到磁盘中。

    • Sidefile *。它是磁盘上的行容器，用于保存来自小表的行，该行针对已泄漏到磁盘的特定分区。溢出到磁盘的每个分区可以有零个或一个辅助文件。

  • 匹配文件它是磁盘上的行容器，用于容纳大表中的行，这些行可能具有匹配的键，并且分区溢出到磁盘。它还与分区具有一对一关系。

当整个小表都可以容纳在内存中时，一切都与经典哈希联接类似，不同的是内存中有多个哈希表而不是一个。

当小表无法容纳在内存中时，事情就变得更加复杂了。

小表键会不断散列到不同的分区中，直到达到内存限制为止。然后，内存中最大的分区将移至磁盘，以便在某种程度上释放内存。应该放在该分区中的新密钥将放入相应的副文件中。

探测期间，如果在内存分区中找到匹配项，则将它们直接放入结果中。

如果找到可能的匹配项，即大表的键哈希值落入磁盘分区中，它将被放入磁盘匹配文件中。目前不进行匹配，但稍后会进行匹配。

大表耗尽后，不再需要并清除所有内存分区。清除是适当的，因为已经输出了应该匹配的键，而那些不匹配的键与磁盘上的结构无关。

现在，可能有许多磁盘上的三 Tuples(分区，sidefile 和 matchfile)。对于每个三 Tuples，合并分区和辅助文件，然后将它们放回内存以形成新的哈希表。然后针对新创建的哈希表扫描匹配文件以查找匹配项。这里的逻辑类似于经典哈希联接。

重复直到所有磁盘三 Tuples 用尽。至此，小表与大表的连接完成。

递归散列和溢出

在某些情况下，哈希函数不能很好地在哈希分区之间平均分配值，或者值本身存在偏差，这将导致很大的辅助文件。在将磁盘分区和辅助文件合并回内存时，新组合的哈希分区的大小将超过内存限制。在这种情况下，另一轮哈希和溢出是必要的。该过程如下图所示。

假设只有 1GB 的存储空间可用于联接。哈希函数 h1 将密钥分配到两个分区 HT1 和 HT2 中。在某个时间点，内存已满，并且 HT1 被移至磁盘。假设所有将来的密钥都哈希到 HT1，因此它们将进入 Sidefile1.

通常，在探测阶段，大表值将被匹配并放入结果中，或者将不匹配并放入 Matchfile 中。

大表用完后，大表中的所有值都应输出(匹配)到结果中，或暂存到 matchfiles 中。然后是时候合并回一对磁盘上的哈希分区和 sidefile，构建新的内存中的哈希表，并针对它探测相应的 matchfile 了。

在此示例中，由于合并的预计大小大于内存限制(800MB 300MB> 1GB)，因此我们不能简单地将它们合并回内存。相反，我们需要使用其他哈希函数 h2 重新哈希它们。

现在我们使用 Matchfile 1 针对 HT 3(在内存中)和 HT 4(在磁盘上)进行探测。 HT 3 的匹配值成为结果。 HT 4 的可能匹配值转到 Matchfile 4.

如果 HT 4 的大小加上 Sidefile 4 的大小仍大于内存限制，即使用第三个哈希函数 h3 对 HT 4 和 Sidefile 4 进行哈希处理，并使用 h3 探测 Matchfile 4，则该过程可以递归 continue。在此示例中，HT 4 的大小加上 Sidefile 4 的大小小于内存限制，因此我们完成了。

数据分布偏斜

有时，一个哈希分区中的所有或大多数行共享相同的值。在那种情况下，无论我们如何更改哈希函数，它都无济于事。

可以考虑几种方法来解决此问题。如果我们具有可靠的数据统计信息(例如详细的直方图)，则可以使用新的联接算法(使用或删除共享同一值的行一次删除)来处理具有相同值的行。或者，我们可以将行分成几部分，以便每一部分都可以放入内存中，并分多次进行探测。这可能会带来性能影响。此外，一旦我们发现 Mapjoin 无法处理这种情况，我们可以使用常规的 shuffle 联接作为后备选项。

Bloom Filter

从Hive 2.0.0开始，在 Hybrid 哈希表的构建阶段构建了一个廉价的 Bloom 过滤器，在将行溢出到 matchfile 中之前会进行咨询。目的是最大程度地减少最终溢出到磁盘的记录数量，这些记录在溢出的哈希表中可能没有任何匹配项。该优化还有利于左外部联接，因为进入混合联接的行可以立即生成为输出，并带有适当的 null 表示缺少匹配，而没有过滤器，则必须将其序列化到磁盘上，而无需在匹配时重新加载就可以了探针的末尾。

References

  • Hybrid Hybrid Grace Hash 加入 Mostafa 的演讲

  • MapJoinOptimization https://cwiki.apache.org/confluence/display/Hive/MapJoinOptimization

  • HIVE-1641将 Map 联接表添加到分布式缓存

  • HIVE-1642根据表/行的大小将联接查询转换为 Map 联接

  • 数据库 Management 系统，第三版

  • Kitsuregawa，M.哈希在数据库机及其体系结构中的应用

  • Shapiro，L. D.具有大主要内存的数据库系统中的联接处理

  • David J. Dewitt，主内存数据库系统的实现技术

  • Jimmy Lin 和 Chris Dyer 使用 MapReduce 进行数据密集型文本处理