SQL基础理论篇(七):多表关联的连接算法

文章目录

  • 简介
  • Nested Loops
  • Merge Join
  • Hash Join
  • 总结
  • 参考文献

简介

多表之间基础的关联算法一共有三种:

  • Hash Join
  • Nested Loops
  • Merge Join

还有很多基于这三种基础算法的变体,以Nested Loops为例,就有用于in和exist的半连接(Nested Loops Semi)算法,以及用于not in和not exists的反连接(Nested Loops Anti)算法等等。这里就不展开介绍了,有兴趣可以再专门搜搜。

Nested Loops

中文名叫嵌套循环,这种连接方式可以简单的用下图来展示:

在这里插入图片描述

上图来自参考文献2.

如果内表中的连接列有索引的话,内表就可以做index scan(索引扫描),否则的话,内表就只能做tab scan(全表扫描)了。

假设我们有一个外表outer, 一个内表inner,连接列c,嵌套循环实际上就是:

for i in outer:for j in inner:if i.c = i.c:# do something

这就是利用嵌套查询来做连接的全过程。

如果inner表的c列有索引,那内层循环就很快了,直接走index scan即可,如果没有,那就只能tab scan扫描全表了。如果没有索引的话,outer表有多少行记录,inner表就要 全表扫描多少次。(所以内层没有索引的话是很恐怖的)

至于外层outer表有没有索引,就无所谓了,反正他总是要做tab scan,取出每一行来跟inner表比较的。

有个小问题,嵌套循环中,如果连接条件使用了不等值连接,那内表还能走索引吗?

不等式!=会导致索引失效,使用函数会导致失效,但范围查询一般不会使索引失效,如<、>=之类的。(注意是一般情况, 如果优化器认为通过索引扫描的行记录数超过全表的10%~30%,那么它可能会自动变成全表扫描,放弃走索引

Merge Join

也称合并连接。

merge join实际上就是把两个有序队列(存在索引,或者无索引但是有序)进行连接,需要两端都要有序,所以不像Nested Join一样不断的循环内部的表。另外,Merge Join需要表连接条件中至少有一个等式,查询分析器才会去选择Merge Join。

merge join的过程可以用下面几个图来解释(同样来自参考文献2):

在这里插入图片描述

首先从两个表中各选取一行,比较,如果匹配,则返回匹配行;如果不匹配,则有较小值的表+1行,可认为是拥有较小值的表,指针后移一位。

在这里插入图片描述

但是如果当前两表并不是有序表(但存在索引),你需要显式的sort之后才能merge join的话,那么使用hash join是效率更高的选择。但也并不绝对,如果查询中已经存在了order by、group by、distinct等,那可能会导致查询分析器不得不进行显式排序,既然已经显式sort了,那查询分析器大概率会对sort之后的结果做merge join。

merge join 对不等值连接(除!=、like外)有更好的支持效率。

但是上面的这张图只能说明等式连接下的merge join的执行过程,那不等式连接下的merge join呢?

据说是这样的:

  1. 根据谓词条件访问A表,对A表的结果集按照连接列进行排序,形成R1;
  2. 根据谓词条件访问B表,对B表的结果集按照连接列进行排序,形成R2;
  3. 将R1和R2放入PGA(即SQL内存区);(这也是传说中的,sort merge join的两表只需要做一次扫描的原因,扫一次就写入内存)
  4. R1中取出第一条记录去R2进行匹配,然后取第二条、第三条,直到匹配完R1中的所有记录。由于R1和R2都在内存中,所以这个匹配过程也是在PGA中进行的。

可以发现,这个过程实际上跟嵌套循环很像,但是有个很显著的特点,merge join中内表是排过序的,这意味着,相比嵌套循环,merge join能高效的处理不等值连接

通常情况下,sort merge join并不适合OLTP的系统, 原因是对于OLTP来讲,排序是极其昂贵的操作

Hash Join

哈希连接。

哈希连接在针对大量、无序的数据时,性能均要优于Merge Join和Nested Join。对于连接列没有索引的情况,查询分析器会优先使用Hash Join。所以哈希连接是做大数据集连接时的常用方式。Hash Join只支持等值连接。

哈希连接分为两个阶段:生成和探测阶段

生成阶段,选择其中一个表(一般是量比较小的表)作为输入源,将其每一行都经过散列函数的计算,放入不同的Hash Bucket中。其中用到的Hash Function和Hash Bucket据说是黑盒的。另外,Hash Bucket中的数据无序。

这一阶段可以参照下图:

在这里插入图片描述

探测阶段,对于另一个表,同样针对每一行做散列函数计算,确定其应在的Hash Bucket,然后用这一行跟这个Hash Bucket中的每一行做匹配,匹配成功则返回对应的行。

探测阶段里,用到的表不需要放入内存,只需要把生成阶段里的小表放入内存即可。

由于Hash Join涉及散列函数计算,所以对CPU的消耗会很大,另外其输出的结果也是无序的。如果内存吃紧的话,还会涉及Grace哈希匹配和递归哈希匹配,可能会用到TempDB从而吃掉大量的IO(如果Hash表太大,无法一次构造在内存里,则会分成若干个partition,写入磁盘,所以使用时会多很多的IO)。有兴趣可以自行查找看看。

hash join 如何处理不等式连接问题?

hash join不支持不等值连接,即<>、<、>等,以及like。

事实上,我感觉也是,分成桶也没办法做范围查询之类的。

总结

在这里插入图片描述

出自参考文献2;

需要提一句的是,在MySQL8.0.18发布之前的很长一段时间里,Mysql的连接算法只有一个嵌套循环的变体,被人广为诟病。直到Mysql8.0.18发布后,Mysql才可以使用Hash Join了。

一般来讲,有索引的情况下会优先使用嵌套,没索引的等值连接则优先使用哈希连接。

参考文献

  1. 多表连接的三种方式详解 hash join、merge join、 nested loop
  2. 表的连接方式:NESTED LOOP、HASH JOIN、MERGE JOIN(修改) 写的非常好,推荐看看
  3. 表连接三剑客(嵌套循环连接,哈希连接,排序合并连接)
  4. 实现一个基于嵌套循环策略的两表连接算法_MySQL新特性之哈希连接

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/198255.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

2023.11.17 关于 Spring Boot 日志文件

目录 日志文件作用 常见的日志框架说明 门面模式 日志的使用 日志的级别 六种级别 日志级别的设置 日志的持久化 使用 Lombok 输出日志 实现原理 普通打印和日志的区别 日志文件作用 记录 错误日志 和 警告日志&#xff08;发现和定位问题&#xff09;记录 用户登录…

自动驾驶学习笔记(十)——Cyber通信

#Apollo开发者# 学习课程的传送门如下&#xff0c;当您也准备学习自动驾驶时&#xff0c;可以和我一同前往&#xff1a; 《自动驾驶新人之旅》免费课程—> 传送门 《Apollo Beta宣讲和线下沙龙》免费报名—>传送门 文章目录 前言 Cyber通信 编写代码 编译程序 运行…

Linux网络应用层协议之http/https

文章目录 目录 一、http协议 1.URL 2.http协议格式 3.http的方法 4.http的状态码 5.http常见header 6.实现一个http服务器 二、https协议 1.加密 2.为什么要加密 3.常见的加密方式 对称加密 非对称加密 4.https的工作过程探究 方案1 只使用对称加密 方案2 只使…

C++二分查找算法:有序矩阵中的第 k 个最小数组和

本文涉及的基础知识点 二分查找算法合集 本题的简化 C二分查找算法&#xff1a;查找和最小的 K 对数字 十分接近m恒等于2 题目 给你一个 m * n 的矩阵 mat&#xff0c;以及一个整数 k &#xff0c;矩阵中的每一行都以非递减的顺序排列。 你可以从每一行中选出 1 个元素形成…

mac控制台命令小技巧

shigen日更文章的博客写手&#xff0c;擅长Java、python、vue、shell等编程语言和各种应用程序、脚本的开发。记录成长&#xff0c;分享认知&#xff0c;留住感动。 hello伙伴们&#xff0c;作为忠实的mac骨灰级别的粉丝&#xff0c;它真的给我带来了很多效率上的提升。那作为接…

计算机网络的体系结构

目录 一. 计算机体系结构的形成二. 协议与层次划分2.1 数据传输过程2.2 什么是网络协议2.3 网络协议的三要素2.4 协议有两种形式2.4 各层协议2.5 什么是复用和分用 \quad 一. 计算机体系结构的形成 \quad 计算机网络是一个非常复杂的系统, 相互通信的两个计算机系统必须高度协调…

vim指令

> 作者简介&#xff1a;დ旧言~&#xff0c;目前大二&#xff0c;现在学习Java&#xff0c;c&#xff0c;c&#xff0c;Python等 > 座右铭&#xff1a;松树千年终是朽&#xff0c;槿花一日自为荣。 > 目标&#xff1a;熟练掌握vim&#xff0c;并且能用vim敲出简单的代…

如何看待人工智能行业发展

随着人工智能技术的飞速发展&#xff0c;这个领域的就业前景也日益广阔。人工智能在各行各业都有广泛的应用&#xff0c;包括医疗、金融、制造业、教育等。因此&#xff0c;对于想要追求高薪、高技能职业的人来说&#xff0c;学习人工智能是一个非常有前景的选择。 首先&#x…

高性能音乐流媒体服务Diosic

什么是 Diosic ? Diosic 是一个开源的基于网络的音乐收集服务器和流媒体。主要适合需要部署在硬件规格不高的服务器上的用户。Diosic 是使用 Rust 开发的&#xff0c;具有低内存使用率和高性能以及用于流媒体音乐的非常干净的界面。 安装 在群晖上以 Docker 方式安装。 在注…

程序员告诉你:人工智能是什么?

随着科技的快速发展&#xff0c;人工智能这个词汇已经逐渐融入了我们的日常生活。然而&#xff0c;对于大多数人来说&#xff0c;人工智能仍然是一个相对模糊的概念。 首先&#xff0c;让我们从人工智能的定义开始。人工智能是一种模拟人类智能的技术&#xff0c;它涵盖了多个领…

【Java程序员面试专栏 专业技能篇】Java SE核心面试指引(一):基础知识考察

关于Java SE部分的核心知识进行一网打尽,包括四部分:基础知识考察、面向对象思想、核心机制策略、Java新特性,通过一篇文章串联面试重点,并且帮助加强日常基础知识的理解,全局思维导图如下所示 本篇Blog为第一部分:基础知识考察,子节点表示追问或同级提问 基本概念 …

Ubuntu20.04 安装微信 【wine方式安装】推荐

安装步骤: 第一步:安装 WineHQ 安装包 先安装wine,根据官网指导安装即可。下载 - WineHQ Wikihttps://wiki.winehq.org/Download_zhcn 如果您之前安装过来自其他仓库的 Wine 安装包,请在尝试安装 WineHQ 安装包之前删除它及依赖它的所有安装包(如:wine-mono、wine-gec…

Clickhouse初认识

技术主题-clickhouse 一什么是clickHouse 1&#xff09;本质上就是一款数据库管理系统&#xff0c;能提供海量数据的存储和检索 2&#xff09;基于列存储&#xff0c;数据是按照列进行存储的&#xff08;数据格式一样&#xff0c;方便进行压缩&#xff09; 3&#xff09;具备…

【Flink】窗口(Window)

窗口理解 窗口&#xff08;Window&#xff09;是处理无界流的关键所在。窗口可以将数据流装入大小有限的“桶”中&#xff0c;再对每个“桶”加以处理。 本文的重心将放在 Flink 如何进行窗口操作以及开发者如何尽可能地利用 Flink 所提供的功能。 对窗口的正确理解&#xff…

nn.KLDivLoss,nn.CrossEntropyLoss,nn.MSELoss,Focal_Loss

KL loss&#xff1a;https://blog.csdn.net/qq_50001789/article/details/128974654 https://pytorch.org/docs/stable/nn.html 1. nn.L1Loss 1.1 公式 L1Loss: 计算预测 x和 目标y之间的平均绝对值误差MAE, 即L1损失&#xff1a; l o s s 1 n ∑ i 1 , . . . n ∣ x i…

【C++入门到精通】新的类功能 | 可变参数模板 C++11 [ C++入门 ]

阅读导航 引言一、新的类功能1. 默认成员函数2. 类成员变量初始化3. 强制生成默认函数的关键字default4. 禁止生成默认函数的关键字delete5. override 和 final&#xff08;1&#xff09;override&#xff08;2&#xff09;final 二、可变参数模板递归函数方式展开参数包逗号表…

读像火箭科学家一样思考笔记03_第一性原理(上)

1. 思维的两种障碍 1.1. 为什么知识会成为一种缺陷而非一种美德 1.1.1. 知识是一种美德 1.1.2. 知识同样的特质也会把它变成一种缺点 1.1.3. 知识确实是个好东西&#xff0c;但知识的作用应该是给人们提供信息&#xff0c;而不是起约束作用 1.1.4. 知识应该启发智慧&#…

Git精讲

Git基本操作 创建Git本地仓库 git initgit clone 配置Git git config [--global] user.name "Your Name" git config [--global] user.email "emailexample.com"–global是一个可选项。如果使用了该选项&#xff0c;表示这台机器上所有的Git仓库都会使…

6 Redis的慢查询配置

1、redis的命令执行流程 redis的慢查询只针对步骤3 默认情况下&#xff0c;慢查询的阈值是10ms 在配置文件中进行配置 //这个参数的单位为微秒 //如果将这个值设置为负数&#xff0c;则会禁用慢日志功能 //如果将其设置为0&#xff0c;则会强制记录每个命令 slowlog-log-slow…

【C++历练之路】list的重要接口||底层逻辑的三个封装以及模拟实现

W...Y的主页 &#x1f60a; 代码仓库分享&#x1f495; &#x1f354;前言&#xff1a; 在C的世界中&#xff0c;有一种数据结构&#xff0c;它不仅像一个神奇的瑰宝匣&#xff0c;还像一位能够在数据的海洋中航行的智慧舵手。这就是C中的list&#xff0c;一个引人入胜的工具…