TiDB 源码阅读系列文章(九)Hash Join

in 编程
关注公众号【好便宜】( ID:haopianyi222 ),领红包啦~
阿里云,国内最大的云服务商,注册就送数千元优惠券:https://t.cn/AiQe5A0g
腾讯云,良心云,价格优惠: https://t.cn/AieHwwKl
搬瓦工,CN2 GIA 优质线路,搭梯子、海外建站推荐: https://t.cn/AieHwfX9

作者:张建

什么是 Hash Join

Hash Join 的基本定义可以参考维基百科:Hash join。简单来说,A 表和 B 表的 Hash Join 需要我们选择一个 Inner 表来构造哈希表,然后对 Outer 表的每一行数据都去这个哈希表中查找是否有匹配的数据。

我们不用 “小表” 和 “大表” 这两个术语是因为:对于类似 Left Outer Join 这种 Outer Join 来说,如果我们使用 Hash Join,不管 Left 表相对于 Right 表而言是大表还是小表,我们都只能使用 Right 表充当 Inner 表并在之上建哈希表,使用 Left 表来当 Outer 表,也就是我们的驱动表。使用 Inner 和 Outer 更准确,没有迷惑性。在 Build 阶段,对 Inner 表建哈希表,在 Probe 阶段,对由 Outer 表驱动执行 Join 过程。

TiDB Hash Join 实现

TiDB 的 Hash Join 是一个多线程版本的实现,主要任务有:

接下来我们细致的介绍 Hash Join 的各个阶段。

Main Thread 读 Inner 表数据

读 Inner 表数据的过程由 fetchInnerRows 这个函数完成。这个过程会不断调用 Child 的 NextChunk 接口,把每次函数调用所获取的 Chunk 存储到 innerResult 这个 List 中供接下来的计算使用。

Main Thread 构造哈希表

构造哈希表的过程由 buildHashTableForList 这个函数完成。

我们这里使用的哈希表(存储在变量 hashTable 中)本质上是一个 MVMap。MVMap 的 Key 和 Value 都是 []byte 类型的数据,和普通 map 不同的是,MVMap 允许一个 Key 拥有多个 Value。这个特性对于 Hash Join 来说非常方便和实用,因为表中同一个 Join Key 可能对应多行数据。

构造哈希表的过程中,我们会遍历 Inner 表的每行数据(上文提到,此时所有的数据都已经存储在了 innerResult 中),对每行数据做如下操作:

Outer Fetcher

Outer Fetcher 是一个后台 goroutine,他的主要计算逻辑在 fetchOuterChunks 这个函数中。

它会不断的读大表的数据,并将获得的 Outer 表的数据分发给各个 Join Worker。这里多线程之间的资源交互可以用下图表示:

上图中涉及到了两个 channel:

所以,整体上 Outer Fetcher 的计算逻辑是:

  1. outerChkResourceCh 中获取一个 outerChkResource,存储在变量 outerResource 中;

  2. 从 Child 拉取数据,将数据写入到 outerResourcechk 字段中;

  3. 将这个 chk 发给需要 Outer 表的数据的 Join Worker 的 outerResultChs[i] 中去,这个信息记录在了 outerResourcedest 字段中。

Join Worker

每个 Join Worker 都是一个后台 goroutine,主要计算逻辑在 runJoinWorker4Chunk 这个函数中。Join Worker 的数量由 tidb_hash_join_concurrency 这个 session 变量来控制,默认是 5 个。

上图中涉及到两个 channel:

所以,整体上 Join Worker 的计算逻辑是:

  1. 获取一个 Outer Chunk;

  2. 获取一个 Join Chunk Resource;

  3. 查哈希表,将匹配的 Outer Row 和 Inner Rows 写到 Join Chunk 中;

  4. 将写满了的 Join Chunk 发送给 Main Thread。

Main Thread

主线程的计算逻辑由 NextChunk 这个函数完成。主线程的计算逻辑非常简单:

  1. joinResultCh 中获取一个 Join Chunk;

  2. 将调用方传下来的 chk 和 Join Chunk 中的数据交换;

  3. 把 Join Chunk 还给对应的 Join Worker。

Hash Join FAQ

如何确定 Inner 和 Outer 表?

Join Key 中 NULL 值的问题

NULLNULL 不等,所以:

Join 中的 4 种 Filter

Join 方式的实现

目前 TiDB 支持的 Join 方式有 7 种,我们使用 joinResultGenerator 这个接口来定义两行数据的 Join 方式,实现一种具体的 Join 方式需要特殊的去实现 joinResultGenerator 这个接口,目前有 7 种实现:

关注公众号【好便宜】( ID:haopianyi222 ),领红包啦~
阿里云,国内最大的云服务商,注册就送数千元优惠券:https://t.cn/AiQe5A0g
腾讯云,良心云,价格优惠: https://t.cn/AieHwwKl
搬瓦工,CN2 GIA 优质线路,搭梯子、海外建站推荐: https://t.cn/AieHwfX9
扫一扫关注公众号添加购物返利助手,领红包
Comments are closed.

推荐使用阿里云服务器

超多优惠券

服务器最低一折,一年不到100!

朕已阅去看看