暂无图片
暂无图片
暂无图片
暂无图片
暂无图片

列存索引中HashMatch算子设计方案——Probe阶段

芬芳 2023-10-17
135

Build阶段读取左表并构建出散列表,而Probe阶段读取右表数据后查找散列表并根据匹配情况进行输出, 既然Build阶段已经将数据进行分区构建,那Probe阶段也需要按Build阶段所采用的数据分区规则来进行分区处理。

DoFetch

Probe阶段同样采用线程组处理方式,由父结点的Fetch操作来驱动。在DoFetch过程中,HashMatch的每个Worker同样不断fetch右表数据,对于fetch到的每一元组按分区规则到指定分区的HashMap中查找,然后根据匹配情况进行处理,不断重复该probe步骤直到所有Worker取完右表为止。

Probe落盘

若Build阶段中内存无法保存所有分区时,Probe阶段也需要针对内存分区和磁盘分区进行分别处理。

在DoFetch过程中,当Worker取到右表数据后,若该元组对应的分区在内存中则直接查找HashMap进行匹配处理,若该分区在磁盘中,则需要将该元组保存到该Worker所属Partition的chunk中,当该chunk满时则需要刷盘并释放chunk内存。当Worker取完右表并probe完成后,则表示内存中分区数据已经处理完成,可以释放内存中所有分区。

当全部处理完内存中的分区后,开始处理磁盘中的分区,由于磁盘中分区的数据已经按分区保存在不同临时文件中,为了避免锁同步,probe阶段仍采用一个磁盘分区由单独Worker独立完成,由于Partition数目往往远大于Worker数目,因此一般不会存在Worker处理不均问题。

当Worker开始处理磁盘中分区时,主要也是分为build与probe两阶段:

  1. build阶段:先从该分区的临时文件中不断读取左表数据并序列化出chunk,然后根据左表chunk数据不断构建HashMap,不断重复该build步骤直到该Worker读取完左表数据为止。
  2. probe阶段:从该分区的临时文件中不断读取右表数据并序列化出chunk,然后对其每一元组在该HashMap中查找根据匹配情况进行处理,不断重复该probe步骤直到该Worker读取完右表数据为止。

当所有Worker处理完所有磁盘分区后则整个HashMatch结束。虽然文档中按内存分区与磁盘分区进行不同处理说明,但实现时统一到了一套代码中。

Probe流程

HashMatch中probe主要由ProbeMem、ProbeLeft与ProbeDisk等三个步骤组成,但其真正probe处理均由Probe函数完成:

  1. ProbeMem用于从右表读取数据并根据数据分区在内存或磁盘分别进行处理。若在内存中直接调用Probe处理,否则将数据保存到临时文件,以便ProbeDisk处理指定磁盘分区时重新加载后再调用Probe处理。
  2. ProbeLeft主要用于LeftOuter/LeftSemi/LeftAntiSemi等Left类型的Join,其遍历整个HashMap所有KV并过滤出已匹配或未匹配过的元组。
  3. ProbeDisk用于磁盘分区的probe操作,按分区来处理,处理指定磁盘分区时先从该分区的临时文件中加载chunk,然后直接调用Probe处理,若为Left类型的Join,还需要调用ProbeLeft对该分区进行处理。
「喜欢这篇文章,您的关注和赞赏是给作者最好的鼓励」
关注作者
【版权声明】本文为墨天轮用户原创内容,转载时必须标注文章的来源(墨天轮),文章链接,文章作者等基本信息,否则作者和墨天轮有权追究责任。如果您发现墨天轮中有涉嫌抄袭或者侵权的内容,欢迎发送邮件至:contact@modb.pro进行举报,并提供相关证据,一经查实,墨天轮将立刻删除相关内容。

评论