一.Join连接算法的意义1.为什么我们需要连接操作因为我们通常不会把所有相关信息都塞进一张表而是把不同类型的信息分开存储当查询需要同时使用这些信息时就必须把它们“连接”起来。比如我们有一张学生表学号姓名专业1张三计算机2李四软件工程3王五网络工程还有一张成绩表学号课程成绩1数据库902数据库853数据库78当我们需要查询每个学生的姓名和数据库课程时我们就需要把Student.学号和Score.学号对应起来这就是join。那为什么我们不把所有信息都放在一张大表里这样看起来确实方便但如果一个学生有很多门课怎么办例如张三有数据库 90 操作系统 88 计算机网络 92 数据结构 95此时这张表就会变成学号姓名专业课程成绩1张三计算机数据库901张三计算机操作系统881张三计算机计算机网络921张三计算机数据结构95这样以来姓名列和专业列就会出现大量重复数据“张三”和“计算机”而且如果张三的专业发生改变就需要我们修改很多行这就容易产生数据冗余和数据不一致。所以我们就需要把数据库的信息拆开设计成Student学号姓名专业Course课程号课程名称学分Score学号课程号成绩这样每种信息只保存一次。当我们需要查询一个人的成绩时由于数据分散在多张表里这时就需要把他们连接起来。2.join的本质Join 是根据两个关系之间的关联属性把分散在不同表中的相关信息重新组合起来。整体可理解为数据分开存储→需要一起使用→通过关联字段连接→得到完整信息3.低效查询倒逼技术优化在专门的连表算法出现之前数据库要把两张表关联起来用的是最笨的办法先把两张表的所有行两两配对生成一张超级大的中间表再从里面挑出符合关联条件的数据。这个办法有个致命问题两张表的数据量会直接相乘。比如一张表 1 万行、另一张表 10 万行中间就会生出 10 亿条配对数据这里面绝大多数都是没用的。这会让磁盘读写量、计算量都爆炸式增长数据量一大就完全跑不动。所以后来学术界和工业界才陆续研究出各种高效的连表算法靠排序、哈希分桶、分块读取这些思路大幅降低了多表关联的资源消耗。4.连接算法连接算法研究的问题两个表的数据量很大时数据库如何快速找到满足连接条件的记录对。我们主要聚焦于基于相等条件的两表内连接算法即基于相等条件的两表连接。这类算法的实现逻辑稍作调整就可以支持外连接、半连接等其他类型的连接操作。在连接中通常会把较小的表作为左表外表这是数据库优化器在生成物理计划时会重点考虑的优化策略以减少内层循环的次数。二.核心逻辑与实现方法主流Join算法原理详解1.朴素嵌套循环连接嵌套循环连接是最基础的连接算法核心逻辑为双层遍历匹配通过外层遍历一张表、内层遍历另一张表可以理解为拿左表的一条记录去右表从头到尾找匹配项找完以后再拿左表下一条。我们可以用C语言中的for循环类比for(Student中的每一条记录){for(Score中的每一条记录){if(Student.idScore.sid){输出连接结果;}}}核心就是外层循环遍历外表内层循环扫描内表。但朴素嵌套循环连接效率可能很低假设学生表有1000条数据成绩表有10000条数据。在最简单情况下要进行1000*1000010000000次匹配判断如果数据量更大效率就会很低很低。所以朴素嵌套循环连接的问题就是如果外表和内表都很大需要大量重复扫描内表性能输在磁盘I/O2.分块嵌套循环连接朴素嵌套循环连接是一条一条的处理数据但是数据库有内存池所以一次性可以装很多页于是就可以一块一块的处理。本质就是把朴素版「一行扫一遍内表」的笨办法改成了「一块扫一遍内表」靠大幅减少内表的扫描次数来省磁盘 IO。优化内表扫描次数嵌套循环里最大的开销就是反复扫内表。分块之后内表的扫描次数从「外表的行数」变成了「外表的分块数」块越大扫描次数越少。用内存换 IO把外表的一批数据先缓存到内存里扫内表的时候一次性和这批数据匹配本质就是用少量内存空间换大量的磁盘读取开销。适配大外表场景如果外表太大、整个装不进内存就用分块的方式分批加载既不爆内存又比一行一行扫高效得多。3.索引嵌套循环连接核心思想索引嵌套循环连接 嵌套循环连接 内表上的索引用索引快速找到匹配记录而不是每次扫描整个内表。普通嵌套循环外表记录→扫描内表索引嵌套循环外表记录→查一个目录→直接找到内表记录这个目录就是索引这个索引通常用B树实现速度比普通嵌套循环快时间复杂度为O(logn。4.排序合并连接核心思想先把两个表按照连接键排序然后利用两个有序序列像拉拉链一样扫描匹配。嵌套循环连接张三 → 扫描Score全部李四 → 扫描Score全部王五 → 扫描Score全部如果两个表很大就会变得非常慢那有没有办法让两个表按照id排好然后直接匹配这就是排序合并连接。它主要分为两个阶段阶段1排序基于连接键通过外部分归并排序分别对表R、表S进行全局排序阶段2合并为两张有序表分别设置游标逐行比对游标所在元组的连接键键相等则拼接输出键不相等则移动较小值的游标直至遍历完任意一张表。5.哈希连接核心思想利用哈希函数把两个表中连接键相同的数据映射到同一个位置然后快速匹配。哈希连接分为两个阶段**Build建立阶段**选取小表为构建表通过哈希函数对连接键哈希在内存中构建哈希表存储元组或记录ID**Probe探测阶段**遍历大表探测表对每条元组的连接键执行相同哈希运算定位哈希表对应桶比对真实键值完成匹配。但如果表非常大不能全部放进内存这时就需要分区哈希连接。核心先分区再分别连接。6.五种算法对比算法核心思想是否需要索引适合场景复杂度Nested Loop双层循环匹配否小表O(MN)Block Nested Loop批量扫描否减少I/O较低Index Nested LoopB树查找是小表大表O(MlogN)Sort-Merge Join排序后合并否/可利用索引大表、有序数据O(NlogN)Hash Join哈希匹配否大规模等值连接O(MN)