SQL中leftjoin的底层原理（各种JOIN的复杂度探究）
sql left join 多表连接01. 前⾔
写过或者学过 SQL 的⼈应该都知道 left join，知道 left join 的实现的效果，就是保留左表的全部信息，然后把右表往左表上拼接，如果拼不上就是 null。除了 left join 以外，还有 inner join、outer join、right join，这些不同的 join 能达到的什么样的效果，⼤家应该都了解了，如果不了解的可以看看⽹上的帖⼦或者随便⼀本 SQL 书都有讲的。今天我们不讲这些 join 能达到什么效果，我们主要讲这些 join 的底层原理是怎么实现的，也就是具体的效果是怎么呈现出来的。
join 主要有 Nested Loop、Hash Join、Merge Join 这三种⽅式，我们这⾥只讲最普遍的，也是最好的理解的 Nested Loop，Nested Loop 翻译过来就是嵌套循环的意思，那什么⼜是嵌套循环呢？嵌套⼤家应该都能理解，就是⼀层套⼀层；那循环呢，你可以理解成是 for 循环。
Nested Loop ⾥⾯⼜有三种细分的连接⽅式，分别是 Simple Nested-Loop Join、Index Nested-Loop Join、Block Nested-Loop Join，接下来我们就分别去看⼀下这三种细分的连接⽅式。
在正式开始之前，先介绍两个概念：驱动表（也叫外表）和被驱动表（也叫⾮驱动表，还可以叫匹配表，亦可叫内表），简单来说，驱动表就是主表，left join 中的左表就是驱动表，right join 中的右表是驱
动表。⼀个是驱动表，那另⼀个就只能是⾮驱动表了，在 join 的过程中，其实就是从驱动表⾥⾯依次（注意理解这⾥⾯的依次）取出每⼀个值，然后去⾮驱动表⾥⾯进⾏匹配，那具体是怎么匹配的呢？这就是我们接下来讲的这三种连接⽅式。
02.Simple Nested-Loop Join
Simple Nested-Loop Join 是这三种⽅法⾥⾯最简单，最好理解，也是最符合⼤家认知的⼀种连接⽅式，现在有两张表 table A 和 table B，我们让 table A left join table B，如果是⽤第⼀种连接⽅式去实现的话，会是怎么去匹配的呢？直接上图：
上⾯的 left join 会从驱动表 table A 中依次取出每⼀个值，然后去⾮驱动表 table B 中从上往下依次匹配，然后把匹配到的值进⾏返回，最后把所有返回值进⾏合并，这样我们就查到了 table A left join table B 的结果。是不是和你的认知是⼀样的呢？利⽤这种⽅法，如果table A 有10⾏，table B 有10⾏，总共需要执⾏ 10 x 10 = 100 次查询。
这种暴⼒匹配的⽅式在数据库中⼀般不使⽤。
03.Index Nested-Loop Join
Index Nested-Loop Join 这种⽅法中，我们看到了 Index，⼤家应该都知道这个就是索引的意思，这个 Index 是要求⾮驱动表上要有索引，有了索引以后可以减少匹配次数，匹配次数减少了就可以提⾼查询的效率了。
为什么会有了索引以后可以减少查询的次数呢？这个其实就涉及到数据结构⾥⾯的⼀些知识了，给⼤家举个例⼦就清楚了。
上图中左边就是普通列的存储⽅式，右边是树结构索引，什么是树结构呢？就是数据分布的像树这样⼀层⼀层的，树结构有⼀个特点就是左边的数据⼩于顶点的数，右边的数⼤于顶点的数，你看右图中，左边的数3是不是⼩于顶点6，右边的数7是不是⼤于顶点6；左边的数1是不是⼩于顶点3，右边的数4是不是⼤于顶点3。
假如我们现在要匹配数值9，如果是左边这种数据存储⽅式的话，我们需要从第⼀⾏依次匹配到最后⼀⾏才能到数值9，总共需要匹配7次；但是如果我们是⽤右边这种树结构索引的话，我们先拿9和最上层顶点6去匹配，发现9⽐6⼤，我们就去顶点的右边去，再去和7匹配，发现9仍然⽐7⼤，再去7的右边，就到了9，这样我们只匹配了3次就把我们想要的9到了。是不是相⽐匹配7次节省了很多时间。
数据库中的索引⼀般⽤ B+ 树，为了让⼤家更好的理解，我上⾯画的图只是最简单的⼀种树结构，⽽⾮真实的 B+ 树，但是原理是⼀样的。
如果索引是主键的话，效率会更⾼，因为主键必须是唯⼀的，所以如果被驱动表是⽤主键去连接，只会出现多对⼀或者⼀对⼀的情况，⽽不会出现多对多和⼀对多的情况。
04.Block Nested-Loop Join
理想情况下，⽤索引匹配是最⾼效的⼀种⽅式，但是在现实⼯作中，并不是所有的列都是索引列，这个时候就需要⽤到 Block Nested-Loop Join ⽅法了，这种⽅法与第⼀种⽅法⽐较类似，唯⼀的区别就是会把驱动表中 left join 涉及到的所有列（不⽌是⽤来on的列，还有select部分的列）先取出来放到⼀个缓存区域，然后再去和⾮驱动表进⾏匹配，这种⽅法和第⼀种⽅法相⽐所需要的匹配次数是⼀样的，差别就在于驱动表的列数不同，也就是数据量的多少不同。所以虽然匹配次数没有减少，但是总体的查询性能还是有提升的。
Join操作是⼀种常见的数据库操作，通过Join可以将多个表关联起来，根据⽤户的条件共同提供数据。⼀般情况，在数据库中都会内置多种Join算法，优化器在优化的时候会根据SQL语句和表的统计信息选择合适的算法。
Hash Join
在执⾏Hash Join时，1. 会根据Join条件将⼀张表进⾏Hash运算加载到内存中的⼀张Hash表中。Hash表类似与Java中的HashTable；2.遍历另外⼀张表，进⾏Hash运算后在内存中查满⾜条件的记录。
select * from t1 join t2 on t1.a = t2.b；在执⾏这个SQL的时候，先加载表t1的数据，然后根据表t1的a字段作为key构造Hash表。之后，从表t2中逐条取出记录，计算字段b的Hash值，去Hash表中查是否存在满⾜条件的记录。
Hash Join的性能很⾼，但是前提条件是内存中能够存放下其中⼀张表的Hash表。所以⼀般适⽤于⼤⼩表Join。在⼀些⼤数据分析的数据查询引擎中，当内存放不下这种Hash表的时候，会将⼩表进⾏分区保存到磁盘上，之后再执⾏Join。
嵌套循环Join
嵌套循环Join中，⾄少⼀张表存在索引，且Join的条件是对索引列的⽐对。带有索引的表作为被检索表，对不带有索引或者两张都带有索引的表中较⼩的那张表进⾏遍历。这个算法充分利⽤了索引的优势，让Join的时间复杂度从O(m*n)变成了O(n)，其中m为被检索表的⾏数，n 为遍历表的⾏数。
Merge Hash
相对于上述两个算法，这个算法的性能差些，但是使⽤范围更⼴些。在这个算法中，相对两张表中的数据进⾏排序，之后再分别取⼀段进⾏Join。
Semi Join
半连接，对于左边的表输出满⾜条件的记录，⽽对于右边的表则不管是否满⾜条件都不会被输出，也就是，最终的结果是左边表数据记录的⼀个⼦集，类似于in、exists。Semi Join本⾝就是Join的⼀种。在⼤数据跨数据源的查询中，Semi Join是对inner join、left join、right join的⼀种优化。查询跨数据源时，尽量减少从每个数据源出来的数据量是⼀种很有效的优化⽅式，毕竟⽹络传输是要花费时间的。将Join 转化成Semi Join是⼀种有效减⼩数据量的⽅式。
对于：select * from t1 join t2 where t1.a = t2.b，Semi Join的过程如下：
1.将表t1的数据加载到内存；
2.根据t1的数据，改写加载表t2的条件，即将SQL语句改写成in、exists等。假设表t1中，全部记录的a字段只有两个值：aa和bb，那么SQL将被改写为select * from t2 in (‘aa’,‘bb’);
3.对从表t1和t2加载的数据做Join；
第2步中对加载t2数据的SQL的改写，使原本需要加载整个t2表改为仅加载t2中满⾜条件的数据。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。