当前位置: 首页 > news >正文

MySQL中JOIN连接的实现算法

目录

嵌套循环算法(NLJ)

简单嵌套循环(SNLJ)

索引嵌套循环(INLJ)

块嵌套循环(BNLJ)

三种算法比较

哈希连接算法(Hash Join)

注意事项:

工作原理:

优点:

缺点:

排序合并链接(SORT MERGE JOIN)

工作流程:

优点:

缺点:

总结


我们都知道SQL的join关联表的使用方式,但是这次聊的是实现join的算法,join有三种算法,分别是Nested Loop Join,Hash join,Sort Merge Join。

嵌套循环算法(NLJ)

嵌套循环算法(Nested-Loop Join,NLJ)是通过两层循环,用第一张表做Outter Loop,第二张表做Inner Loop,Outter Loop的每一条记录跟Inner Loop的记录作比较,符合条件的就输出。而NLJ又有3种细分的算法:嵌套循环算法又可以分为简单嵌套循环、索引嵌套循环、块嵌套循环。

简单嵌套循环(SNLJ)

    // 伪代码for (r in R) {for (s in S) {if (r satisfy condition s) {output <r, s>;}}}

SNLJ就是两层循环全量扫描连接的两张表,得到符合条件的两条记录则输出,这也就是让两张表做笛卡尔积,比较次数是R * S,是比较暴力的算法,会比较耗时。

索引嵌套循环(INLJ)

    // 伪代码for (r in R) {for (si in SIndex) {if (r satisfy condition si) {output <r, s>;}}}

INLJ是在SNLJ的基础上做了优化,通过连接条件确定可用的索引,在Inner Loop中扫描索引而不去扫描数据本身,从而提高Inner Loop的效率。
而INLJ也有缺点,就是如果扫描的索引是非聚簇索引,并且需要访问非索引的数据,会产生一个回表读取数据的操作,这就多了一次随机的I/O操作。

块嵌套循环(BNLJ)

    // 伪代码for (r in R) {for (sbu in SBuffer) {if (r satisfy condition sbu) {output <r, s>;}}}

扫描一个表的过程其实是先把这个表从磁盘上加载到内存中,然后在内存中比较匹配条件是否满足。但内存里可能并不能完全存放的下表中所有的记录。为了减少访问被驱动表的次数,我们可以首先将驱动表的数据批量加载到 Join Buffer(连接缓冲),然后当加载被驱动表的记录到内存时,就可以一次性和多条驱动表中的记录做匹配,这样可大大减少被驱动表的扫描次数,这就是 BNLJ 算法的思想。

三种算法比较

算法比较(外表大小R,内表大小S):

                   \algorithm
comparison\
Simple Nested Loop JoinBlock Nested Loop Join
外表扫描次数111
内表扫描次数R0
读取记录次数
R + R * S
R + RS_Matches
比较次数
R * S
R * IndexHeight
R * S
回表次数0
RS_Matches
0

整体效率比较:INLJ > BNLJ > SNLJ

哈希连接算法(Hash Join)

MySQL 8.0.18支持在optimizer_switch中设置hash_join标志,以及优化器提示HASH_JOIN和NO_HASH_JOIN。在MySQL 8.0.19和更高版本中,这些都不再有任何效果。

从MySQL 8.0.20开始,对块嵌套循环的支持被删除,并且服务器在以前使用块嵌套循环的地方使用哈希连接。

hash join的实现分为build table也就是被用来建立hash map的小表和probe table,首先依次读取小表的数据,对于每一行数据根据连接条件生成一个hash map中的一个元組,数据缓存在内存中,如果内存放不下需要dump到外存。依次扫描探测表拿到每一行数据根据join condition生成hash key映射hash map中对应的元組,元組对应的行和探测表的这一行有着同样的hash key, 这时并不能确定这两行就是满足条件的数据,需要再次过一遍join condition和filter,满足条件的数据集返回需要的投影列。

// 伪代码
// 算法复杂度:O(M + N)
// 假设用户表有M条记录, 订单表有N条记录
func HashJoin(users []TradeUser, orders []TradeOrder) []*UserOrderView {var userOrderViews []*UserOrderView = make([]*UserOrderView, 0)// 将用户表以用户ID为Key,用户为Value转换为Hash表// 算法复杂度:O(M)userTable := make(map[int]TradeUser)for _, user := range users {userTable[user.Id] = user}// 遍历订单表,查找用户// 算法复杂度:O(N)for _, order := range orders {// 复杂度,接近:O(1)if user, exists := userTable[order.UserId]; exists {// 添加视图结果userOrderViews = append(userOrderViews, &UserOrderView{UserId:      user.Id,UserName:    user.Name,OrderId:     order.Id,OrderAmount: order.Amount,})}}return userOrderViews
}

注意事项:

  1. hash join本身的实现不要去判断哪个是小表,优化器生成执行计划时就已经确定了表的连接顺序,以左表为小表建立hash table,那对应的代价模型就会以左表作为小表来得出代价,这样根据代价生成的路径就是符合实现要求的。
  2. hash table的大小、需要分配多少个桶这个是需要在一开始就做好的,那分配多少是一个问题,分配太大会造成内存浪费,分配太小会导致桶数过小开链过长性能变差,一旦超过这里的内存限制,会考虑dump到外存,不同数据库有它们自身的实现方式。
  3. 如何对数据hash,不同数据库有着自己的方式,不同的哈希方法也会对性能造成一定的影响。

工作原理:

构建阶段(Build Phase)

  1. 选择构建表(Build Table):算法通常会选择数据量较小的表作为构建表,以减少哈希表的构建时间和所需内存。但这不是绝对的,实际选择会根据统计信息和成本估算来决定。
  2. 创建哈希表:对构建表中的每一行记录,取其连接列(即用于JOIN的列)的值,应用哈希函数计算出一个哈希码(hash code)。然后,根据这个哈希码将记录存储在一个哈希桶(hash bucket)中。如果有多个记录的连接列值经过哈希后得到相同的哈希码,这些记录会被组织成链表或其他数据结构存储在同一哈希桶内。

探测阶段(Probe Phase)

  1. 扫描探测表(Probe Table):对另一个较大的表(探测表)进行扫描。
  2. 哈希计算与匹配:对于探测表中的每一行,同样对其连接列值应用相同的哈希函数计算哈希码,然后在这个预先构建好的哈希表中查找对应的哈希桶。
  3. 匹配与输出:如果找到匹配的哈希桶,就进一步检查桶内的链表或数据结构,进行精确的等值比较,以确保连接列的值确实相等。一旦找到匹配项,就结合两个表的相关字段生成结果集的行并输出。

优点:

  • 性能优势:在数据量大时,哈希连接可以显著减少磁盘I/O和CPU时间,因为它避免了嵌套循环的多次扫描和排序-合并连接中的排序开销。
  • 并行处理友好:哈希连接天然适合并行化处理,因为哈希表可以在不同的处理器或节点上并行构建和查询。
  • 内存依赖:哈希连接的效率高度依赖于可用内存,因为需要在内存中存储整个哈希表。如果内存不足,部分或全部哈希表可能需要溢写到磁盘,这会大大降低效率。

缺点:

  • 内存消耗:如前所述,构建哈希表需要足够的内存空间,特别是当构建表较大时。
  • 非等值连接不适用:哈希连接主要用于等值连接,对于非等值连接(如大于、小于等条件)不适用。
  • 预读取与优化:为了效率,数据库系统需要有效管理内存使用,并可能实施预读取策略来优化性能。

排序合并链接(SORT MERGE JOIN)

排序合并连接是嵌套循环连接的变种。如果两个数据集还没有排序,那么数据库会先对它们进行排序,这就是所谓的sort join操作。对于数据集里的每一行,数据库会从上一次匹配到数据的位置开始探查第二个数据集,这一步就是Merge join操作。

// 伪代码
// 算法复杂度:O(M log M + N log N)
// 假设用户表有M条记录, 订单表有N条记录
func SortJoin(users []TradeUser, orders []TradeOrder) []*UserOrderView {var userOrderViews []*UserOrderView = make([]*UserOrderView, 0)// 排序user表// 算法复杂度:O(M log M)sort.Slice(users, func(i, j int) bool {return users[i].Id < users[j].Id})// 排序order表// 算法复杂度:O(N log N)sort.Slice(orders, func(i, j int) bool {return orders[i].Id < orders[j].Id})// 遍历订单表,查找用户// 算法复杂度:O(M)userIdx := 0for _, order := range orders {// 在user.id为主键的情况下,这里还可以执行二分查找for idx < len(users) && users[userIdx].Id < order.UserId {userIdx++}// 如果找到用户,添加到结果集合if userIdx < len(users) && users[userIdx].id == order.UserId {// Join条件满足添加视图结果userOrderViews = append(userOrderViews, &UserOrderView{UserId:      user.Id,UserName:    user.Name,OrderId:     order.Id,OrderAmount: order.Amount,})}}return userOrderViews
}

工作流程:

  1. 排序阶段

    • 数据排序:首先,算法会对参与连接的两个表根据连接键进行排序。这一步骤是关键,因为只有排序后的数据才能有效地进行归并操作。如果表已经按照连接键排序,这一步可以省略。
    • 索引利用:如果表上有适合的索引(如聚集索引或覆盖索引),数据库引擎可能会直接利用这些索引来避免全表排序。
  2. 合并阶段

    • 双指针扫描:一旦两个表的数据都按连接键排序好了,算法会使用两个指针(或游标)分别指向两个表的开始。每个指针逐步向后移动,比较两个指针所指记录的连接键值。
    • 匹配与输出:当两个指针指向的记录的连接键相等时,说明这两个记录应该被连接起来,此时就会输出(或累积到结果集中)这对匹配的记录。如果一个表的指针达到末尾,而另一个表还有剩余记录,则剩余的记录被视为不匹配,如果有外连接的情况,则可能作为NULL扩展输出。
    • 推进指针:匹配后,指针会根据排序顺序向后移动,继续寻找下一个匹配的记录。

优点:

  • 效率:对于大表连接,特别是当连接键分布均匀,且数据已经排序或可以低成本排序时,SMJ比Nested-Loop Join更高效,因为它减少了不必要的比较次数。
  • 稳定性:由于是基于排序的,Sort Merge Join保证了输出结果的稳定性,即具有相同键值的记录保持原有的相对顺序。
  • 可预测性能:时间复杂度主要取决于排序操作,通常是O(n log n),对于大规模数据集来说,性能较为可预测。

缺点:

  • 内存和I/O开销:排序操作可能需要额外的内存空间,并且如果数据不能完全放入内存,还需要磁盘I/O操作,这可能会成为性能瓶颈。
  • 预处理时间:排序是预处理步骤,可能增加整体处理时间,尤其是在数据已经接近有序或只需要执行一次连接操作的情况下。

总结

算法名称时间复杂度描述
Nested Loop JoinO(M*N)适合小数据集,大数据集很慢
Sort Merge JoinO(M log M + N log N + M + N)适合于当内存不足以存放整个数据集,需要小的分区上进行排序和合并
Hash JoinO(M+N)适用于大数据集

相关文章:

MySQL中JOIN连接的实现算法

目录 嵌套循环算法&#xff08;NLJ&#xff09; 简单嵌套循环&#xff08;SNLJ&#xff09; 索引嵌套循环&#xff08;INLJ&#xff09; 块嵌套循环&#xff08;BNLJ&#xff09; 三种算法比较 哈希连接算法&#xff08;Hash Join&#xff09; 注意事项&#xff1a; 工…...

[力扣题解] 216. 组合总和 III

题目&#xff1a;216. 组合总和 III 思路 回溯法 代码 class Solution { private:vector<vector<int>> result;vector<int> path;public:void function(int k, int n, int startindex, int sum){int i;// 剪枝// 超过了, 不用找了;if(sum > n){return…...

Spring Security Oauth2 JWT 添加额外信息

目录 一、问题描述 二、实现步骤 1、自定义TokenEnhancer 2、配置授权服务器 3、自定义UserDetails的User类 三、参考文档 一、问题描述 Oauth2里默认生成的JWT信息并没有用户信息&#xff0c;在认证授权后一般会返回这一部分信息&#xff0c;我对此进行了改造。 Oauth…...

蜜蜂收卡系统 加油卡充值卡礼品卡自定义回收系统源码 前后端开源uniapp可打包app

本文来自&#xff1a;蜜蜂收卡系统 加油卡充值卡礼品卡自定义回收系统源码 前后端开源uniapp可打包app - 源码1688 卡券绿色循环计划—— 一项旨在构建卡券价值再利用生态的社会责任感项目。在当前数字化消费日益普及的背景下&#xff0c;大量礼品卡、优惠券因各种原因未能有效…...

三星硬盘好还是西数硬盘好?硬盘数据丢失怎么找回

在数字化时代&#xff0c;硬盘作为数据存储的核心组件&#xff0c;其品质与性能直接关系到用户的数据安全与使用体验。在众多硬盘品牌中&#xff0c;三星与西数无疑是两个备受关注的名字。那么&#xff0c;究竟是三星硬盘更胜一筹&#xff0c;还是西数硬盘更受用户青睐&#xf…...

企业微信hook接口协议,ipad协议http,设置是否自动同意

设置是否自动同意 参数名必选类型说明uuid是String每个实例的唯一标识&#xff0c;根据uuid操作具体企业微信 请求示例 {"uuid":"bc4800492083fdec4c1a7e5c94","state":1 //1 是需要验证同意&#xff08;需要手动点击同意&#xff09; 0关闭验证…...

自动化测试的成本高效果差,那么自动化测试的意义在哪呢?

有人问&#xff1a;自动化测试的成本高效果差&#xff0c;那么自动化测试的意义在哪呢&#xff1f; 我觉得这个问题带有很强的误导性&#xff0c;是典型的逻辑陷阱之一。“自动化测试的成本高效果差”是真的吗&#xff1f;当然不是。而且我始终相信&#xff0c;回答问题的最…...

h5页面用js判断机型是安卓还是ios,判断有app安装没app跳转应用商店app stroe或者安卓应用商店

用vue3写的wep页面。亲测好使。 疑惑&#xff1a; 微信跳转和浏览器跳转不一样&#xff0c;需要控制定时器的时间&#xff0c;android在没下载的情况下点击没反应&#xff0c;ios在没下载的情况下会跳404&#xff0c;就是定时器2000&#xff0c;不知道有没有别的办法&#xff0…...

算法人生(17):从“课程学习”到“逐步暴露心理疗法”

课程学习&#xff08;Curriculum Learning&#xff09;是一种机器学习里常用的策略&#xff0c;它的灵感来源于人类学习方式&#xff1a;学习从简单的概念开始&#xff0c;逐步过渡到更复杂的问题。它通过模仿教育领域中课程安排的思想&#xff0c;设计了一系列有序的任务或数据…...

C++仿函数周边及包装器

我最近开了几个专栏&#xff0c;诚信互三&#xff01; > |||《算法专栏》&#xff1a;&#xff1a;刷题教程来自网站《代码随想录》。||| > |||《C专栏》&#xff1a;&#xff1a;记录我学习C的经历&#xff0c;看完你一定会有收获。||| > |||《Linux专栏》&#xff1…...

改进灰狼算法优化随机森林回归预测

灰狼算法&#xff08;Grey Wolf Optimization&#xff0c;GWO&#xff09;是一种基于自然界灰狼行为的启发式优化算法&#xff0c;在2014年被提出。该算法模仿了灰狼群体中不同等级的灰狼间的优势竞争和合作行为&#xff0c;通过不断搜索最优解来解决复杂的优化问题。 灰狼算法…...

Hadoop生态系统的核心组件探索

理解大数据和Hadoop的基本概念 当我们谈论“大数据”时&#xff0c;我们指的是那些因其体积、速度或多样性而难以使用传统数据处理软件有效管理的数据集。大数据可以来自多种来源&#xff0c;如社交媒体、传感器、视频监控、交易记录等&#xff0c;通常包含了TB&#xff08;太…...

命令行方式将mysql数据库迁移到达梦数据库(全步骤)

因项目需求&#xff0c;需要将mysql数据库转换为国产达梦数据库&#xff0c;但由于安全问题&#xff0c;正式环境只能用命令行方式连接&#xff0c;下列是操作全步骤 目录 一、操作逻辑二、操作步骤1、本地安装达梦相关工具2、将服务器mysql导出到本地a) 服务器命令行导出mysql…...

旅游系列之:庐山美景

旅游系列之&#xff1a;庐山美景 一、路线二、住宿二、庐山美景 一、路线 庐山北门乘坐大巴上山&#xff0c;住在上山的酒店东线大巴游览三叠泉&#xff0c;不需要乘坐缆车&#xff0c;步行上下三叠泉即可&#xff0c;线路很短 二、住宿 长江宾馆庐山分部 二、庐山美景...

杭州恒生面试,社招,3年经验

你好&#xff0c;我是田哥 一位朋友节前去恒生面试&#xff0c;其实面试问题大部分都是八股文&#xff0c;但由于自己平时工作比较忙&#xff0c;完全没有时间没有精力去看八股文&#xff0c;导致面试结果不太理想&#xff0c;HR说节后通知面试结果&#xff08;估计是凉了&…...

python virtualenv 创建虚拟环境指定python版本,pip 从指定地址下载某个包

一、安装 pip install virtualenv是python3 的话 换成 pip3 如果下载过慢可以从国内链接下载 如下从阿里云下载 pip3 install -i https://mirrors.aliyun.com/pypi/simple virtualenv二、创建指定python版本的虚拟环境 virtualenv venv --pythonpython3.12这里的venv 为创…...

open feign支持调用form-data的接口

增加 consumes {MediaType.MULTIPART_FORM_DATA_VALUE}) 示例 PostMapping(value "/ocr", consumes {MediaType.MULTIPART_FORM_DATA_VALUE})DataResponse ocr(RequestPart("file") MultipartFile multipartFile,RequestPart("fileType") Str…...

ESD静电问题 | TypeC接口整改

【转自微信公众号&#xff1a;深圳比创达EMC】...

基于springboot+mybatis+vue的项目实战之前端

步骤&#xff1a; 1、项目准备&#xff1a;新建项目&#xff0c;并删除自带demo程序&#xff0c;修改application.properties. 2、使用Apifox准备好json数据的mock地址 3、编写基于vue的静态页面 4、运行 整个的目录结构如下&#xff1a; 0、项目准备 新建项目&#xff0…...

开源软件托管平台gogs操作注意事项

文章目录 一、基本说明二、gogs私有化部署三、设置仓库git链接自动生成参数四、关闭新用户注册入口 私有化部署gogs托管平台&#xff0c;即把gogs安装在我们自己的电脑或者云服务器上。 一、基本说明 系统环境&#xff1a;ubuntu 20.4docker安装 二、gogs私有化部署 前期准…...

SpringBoot-17-MyBatis动态SQL标签之常用标签

文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...

谷歌浏览器插件

项目中有时候会用到插件 sync-cookie-extension1.0.0&#xff1a;开发环境同步测试 cookie 至 localhost&#xff0c;便于本地请求服务携带 cookie 参考地址&#xff1a;https://juejin.cn/post/7139354571712757767 里面有源码下载下来&#xff0c;加在到扩展即可使用FeHelp…...

MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例

一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...

JavaScript 中的 ES|QL:利用 Apache Arrow 工具

作者&#xff1a;来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗&#xff1f;了解下一期 Elasticsearch Engineer 培训的时间吧&#xff01; Elasticsearch 拥有众多新功能&#xff0c;助你为自己…...

CentOS下的分布式内存计算Spark环境部署

一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架&#xff0c;相比 MapReduce 具有以下核心优势&#xff1a; 内存计算&#xff1a;数据可常驻内存&#xff0c;迭代计算性能提升 10-100 倍&#xff08;文档段落&#xff1a;3-79…...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

高危文件识别的常用算法:原理、应用与企业场景

高危文件识别的常用算法&#xff1a;原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件&#xff0c;如包含恶意代码、敏感数据或欺诈内容的文档&#xff0c;在企业协同办公环境中&#xff08;如Teams、Google Workspace&#xff09;尤为重要。结合大模型技术&…...

C++中string流知识详解和示例

一、概览与类体系 C 提供三种基于内存字符串的流&#xff0c;定义在 <sstream> 中&#xff1a; std::istringstream&#xff1a;输入流&#xff0c;从已有字符串中读取并解析。std::ostringstream&#xff1a;输出流&#xff0c;向内部缓冲区写入内容&#xff0c;最终取…...

C++ 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

Map相关知识

数据结构 二叉树 二叉树&#xff0c;顾名思义&#xff0c;每个节点最多有两个“叉”&#xff0c;也就是两个子节点&#xff0c;分别是左子 节点和右子节点。不过&#xff0c;二叉树并不要求每个节点都有两个子节点&#xff0c;有的节点只 有左子节点&#xff0c;有的节点只有…...