TiDB 源码阅读系列文章(十五)Sort Merge Join

2024-04-08 03:18

本文主要是介绍TiDB 源码阅读系列文章(十五)Sort Merge Join,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

什么是 Sort Merge Join

在开始阅读源码之前, 我们来看看什么是 Sort Merge Join (SMJ),定义可以看 wikipedia。简单说来就是将 Join 的两个表,首先根据连接属性进行排序,然后进行一次扫描归并, 进而就可以得出最后的结果。这个算法最大的消耗在于对内外表数据进行排序,而当连接列为索引列时,我们可以利用索引的有序性避免排序带来的消耗, 所以通常在查询优化器中,连接列为索引列的情况下可以考虑选择使用 SMJ。

TiDB Sort Merge Join 实现

执行过程

TiDB 的实现代码在 tidb/executor/merge_join.go 中 MergeJoinExec.NextChunk 是这个算子的入口。下面以 SELECT * FROM A JOIN B ON A.a = B.a 为例,对 SMJ 执行过程进行简述,假设此时外表为 A,内表为 B,join-keys 为 a,A,B 表的 a 列上都有索引:

  1. 顺序读取外表 A 直到 join-keys 中出现另外的值,把相同 keys 的行放入数组 a1,同样的规则读取内表 B,把相同 keys 的行放入数组 a2。如果外表数据或者内表数据读取结束,退出。

  2. 从 a1 中读取当前第一行数据,设为 v1。从 a2 中读取当前第一行数据,设为 v2。

  3. 根据 join-keys 比较 v1,v2,结果分为几种情况:

    • cmpResult > 0, 表示 v1 大于 v2,把当前 a2 的数据丢弃,从内表读取下一批数据,读取方法同 1。重复 2。
    • cmpResult < 0, 表示 v1 小于 v2,说明外表的 v1 没有内表的值与之相同,把外表数据输出给 resultGenerator(不同的连接类型会有不同的结果输出,例如外连接会把不匹配的外表数据输出)。
    • cmpResult == 0, 表示 v1 等于 v2。那么遍历 a1 里面的数据,跟 a2 的数据,输出给 resultGenerator 作一次连接。
  4. 回到步骤 1。

下面的图展示了 SMJ 的过程:

图 1 SMJ 过程.png

读取内表 / 外表数据

我们分别通过 fetchNextInnerRows 或者 fetchNextOuterRows 读取内表和外表的数据。这两个函数实现的功能类似,这里只详述函数 fetchNextInnerRows 的实现。

MergeSortExec 算子读取数据,是通过迭代器 readerIterator 完成,readerIterator 可以顺序读取数据。MergeSortExec 算子维护两个 readerIterator:outerIterinnerIter,它们在 buildMergeJoin 函数中被构造。

真正读取数据的操作是在 readerIterator.nextSelectedRow 中完成, 这里会通过 ri.reader.NextChunk 每次读取一个 Chunk 的数据,关于 Chunk 的相关内容,可以查看我们之前的文章 TiDB 源码阅读系列文章(十)Chunk 和执行框架简介 。

这里值得注意的是,我们通过 expression.VectorizedFilter 对外表数据进行过滤,返回一个 curSelected 布尔数组,用于外表的每一行数据是否是满足 filter 过滤条件。以 select * from t1 left outer join t2 on t1.a=100; 为例, 这里的 filter 是 t1.a=100, 对于没有通过这个过滤条件的行,我们通过 ri.joinResultGenerator.emitToChunk 函数发送给 resultGenerator, 这个 resultGenerator 是一个 interface,具体是否输出这行数据,会由 join 的类型决定,比如外连接则会输出,内连接则会忽略。具体关于 resultGenerator, 可以参考之前的文章:TiDB 源码阅读系列文章(九)Hash Join

rowsWithSameKey 通过 nextSelectedRow 不断读取下一行数据,并通过对每行数据的 join-keys 进行判断是不是属于同一个 join-keys,如果是,会把相同 join-keys 的行分别放入到 innerChunkRowsouterIter4Row 数组中。然后对其分别建立迭代器 innerIter4Row 和 outerIter4Row。在 SMJ 中的执行过程中,会利用这两个迭代器来获取数据进行真正的比较得出 join result。

Merge-Join

实现 Merge-Join 逻辑的代码在函数 MergeJoinExec.joinToChunk, 对内外表迭代器的当前数据根据各自的 join-keys 作对比,有如下几个结果:

  • cmpResult > 0,代表外表当前数据大于内表数据,那么通过 fetchNextInnerRows 直接读取下一个内表数据,然后重新比较即可。

  • cmpResult < 0,代表外表当前数据小于内表数据,这个时候就分几种情况了,如果是外连接,那么需要输出外表数据 + NULL,如果是内连接,那么这个外表数据就被忽略,对于这个不同逻辑的处理,统一由 e.resultGenerator 来控制,我们只需要把外表数据通过 e.resultGenerator.emitToChunk 调用它即可。然后通过 fetchNextOuterRows 读取下一个外表数据,重新比较。

  • cmpResult == 0,代表外表当前数据等于内表当前数据,这个时候就把外表数据跟内表当前数据做一次连接,通过 e.resultGenerator.emitToChunk 生成结果。之后外表跟内表分别获取下一个数据,重新开始比较。

重复上面的过程,直到外表或者内表数据被遍历完,退出 Merge-Join 的过程。

更多

我们上面的分析代码基于 Source-code 分支,可能大家已经发现了一些问题,比如我们会一次性读取内外表的 Join group(相同的 key)。这里如果相同的 key 比较多,是有内存 OOM 的风险的。针对这个问题,我们在最新的 master 分支做了几个事情来优化:

  1. 外表其实不需要把相同的 keys 一次性都读取上来, 它只需要按次迭代外表数据,再跟内表逐一对比作连接即可。这里至少可以减少外表发生 OOM 的问题,可以大大减少 OOM 的概率。

  2. 对于内表,我们对 OOM 也不是没有办法,我们用 memory.Tracker 这个内存追踪器来记录当前内表已经使用的中间结果的内存大小,如果它超过我们设置的阈值,我们会采取输出日志或者终止 SQL 继续运行的方法来规避 OOM 的发生。关于 memory.Tracker 我们不在此展开,可以留意我们后续的源码分析文章。

后续我们还会在 Merge-Join 方面做一些优化, 比如我们可以做多路归并,中间结果存外存等等,敬请期待。

作者:姚维

这篇关于TiDB 源码阅读系列文章(十五)Sort Merge Join的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/884428

相关文章

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门(一):登录与退出》 《Spring-Security-入门(二):基于数据库验证》 《Spring-Security-入门(三):密码加密》 《Spring-Security-入门(四):自定义-Filter》 《Spring-Security-入门(五):在 Sprin

JAVA智听未来一站式有声阅读平台听书系统小程序源码

智听未来,一站式有声阅读平台听书系统 🌟&nbsp;开篇:遇见未来,从“智听”开始 在这个快节奏的时代,你是否渴望在忙碌的间隙,找到一片属于自己的宁静角落?是否梦想着能随时随地,沉浸在知识的海洋,或是故事的奇幻世界里?今天,就让我带你一起探索“智听未来”——这一站式有声阅读平台听书系统,它正悄悄改变着我们的阅读方式,让未来触手可及! 📚&nbsp;第一站:海量资源,应有尽有 走进“智听

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

科研绘图系列:R语言扩展物种堆积图(Extended Stacked Barplot)

介绍 R语言的扩展物种堆积图是一种数据可视化工具,它不仅展示了物种的堆积结果,还整合了不同样本分组之间的差异性分析结果。这种图形表示方法能够直观地比较不同物种在各个分组中的显著性差异,为研究者提供了一种有效的数据解读方式。 加载R包 knitr::opts_chunk$set(warning = F, message = F)library(tidyverse)library(phyl

【生成模型系列(初级)】嵌入(Embedding)方程——自然语言处理的数学灵魂【通俗理解】

【通俗理解】嵌入(Embedding)方程——自然语言处理的数学灵魂 关键词提炼 #嵌入方程 #自然语言处理 #词向量 #机器学习 #神经网络 #向量空间模型 #Siri #Google翻译 #AlexNet 第一节:嵌入方程的类比与核心概念【尽可能通俗】 嵌入方程可以被看作是自然语言处理中的“翻译机”,它将文本中的单词或短语转换成计算机能够理解的数学形式,即向量。 正如翻译机将一种语言

Java ArrayList扩容机制 (源码解读)

结论:初始长度为10,若所需长度小于1.5倍原长度,则按照1.5倍扩容。若不够用则按照所需长度扩容。 一. 明确类内部重要变量含义         1:数组默认长度         2:这是一个共享的空数组实例,用于明确创建长度为0时的ArrayList ,比如通过 new ArrayList<>(0),ArrayList 内部的数组 elementData 会指向这个 EMPTY_EL

如何在Visual Studio中调试.NET源码

今天偶然在看别人代码时,发现在他的代码里使用了Any判断List<T>是否为空。 我一般的做法是先判断是否为null,再判断Count。 看了一下Count的源码如下: 1 [__DynamicallyInvokable]2 public int Count3 {4 [__DynamicallyInvokable]5 get

工厂ERP管理系统实现源码(JAVA)

工厂进销存管理系统是一个集采购管理、仓库管理、生产管理和销售管理于一体的综合解决方案。该系统旨在帮助企业优化流程、提高效率、降低成本,并实时掌握各环节的运营状况。 在采购管理方面,系统能够处理采购订单、供应商管理和采购入库等流程,确保采购过程的透明和高效。仓库管理方面,实现库存的精准管理,包括入库、出库、盘点等操作,确保库存数据的准确性和实时性。 生产管理模块则涵盖了生产计划制定、物料需求计划、

flume系列之:查看flume系统日志、查看统计flume日志类型、查看flume日志

遍历指定目录下多个文件查找指定内容 服务器系统日志会记录flume相关日志 cat /var/log/messages |grep -i oom 查找系统日志中关于flume的指定日志 import osdef search_string_in_files(directory, search_string):count = 0

论文阅读笔记: Segment Anything

文章目录 Segment Anything摘要引言任务模型数据引擎数据集负责任的人工智能 Segment Anything Model图像编码器提示编码器mask解码器解决歧义损失和训练 Segment Anything 论文地址: https://arxiv.org/abs/2304.02643 代码地址:https://github.com/facebookresear