正文

join的实现原理及优化思路

西伯利亚狼520  西伯利亚狼520  2022-09-18  607

关键词：

前言

前面我们已经了解了MySQLQueryOptimizer的工作原理，学习了Query优化的基本原则和思路，理解了索引选择的技巧，这一节我们将围绕Query语句中使用非常频繁，且随时可能存在性能隐患的Join语句，继续我们的Query优化之旅。

Join 的实现原理

在寻找Join语句的优化思路之前，我们首先要理解在MySQL中是如何来实现Join的，只要理解了实现原理之后，优化就比较简单了。下面我们先分析一下MySQL中Join的实现原理。

在MySQL中，只有一种Join算法，就是大名鼎鼎的NestedLoopJoin，他没有其他很多数据库所提供的HashJoin，也没有SortMergeJoin。顾名思义，NestedLoopJoin实际上就是通过驱动表的结果集作为循环基础数据，然后一条一条的通过该结果集中的数据作为过滤条件到下一个表中查询数据，然后合并结果。如果还有第三个参与Join，则再通过前两个表的Join结果集作为循环基础数据，再一次通过循环查询条件到第三个表中查询数据，如此往复。

下面我们将通过一个三表Join语句示例来说明MySQL的NestedLoopJoin实现方式。

注意：由于要展示Explain中的一个在MySQL5.1.18才开始出现的输出信息（在之前版本中只是没有输出信息，实际执行过程并没有变化），所以下面的示例环境是MySQL5.1.26。

Query 如下：

select m.subject msg_subject, c.content msg_content
from user_group g,group_message m,group_message_content c
where g.user_id = 1

and m.group_id = g.group_id
and c.group_msg_id = m.id

为了便于示例，我们通过如下操作为group_message表增加了一个group_id的索引：

create index idx_group_message_gid_uid on group_message(group_id);

然后看看我们的Query的执行计划：

sky@localhost : example 11:17:04> explain select m.subject msg_subject, c.content

msg_content -> from user_group g,group_message m,group_message_content c -> where g.user_id = 1 -> and m.group_id = g.group_id -> and c.group_msg_id = m.id\G

*************************** 1. row ***************************
id: 1
select_type: SIMPLE
table: g
type: ref
possible_keys: user_group_gid_ind,user_group_uid_ind,user_group_gid_uid_ind
key: user_group_uid_ind
key_len: 4
ref: const

rows: 2
Extra:
*************************** 2. row ***************************
id: 1
select_type: SIMPLE
table: m
type: ref
possible_keys: PRIMARY,idx_group_message_gid_uid
key: idx_group_message_gid_uid
key_len: 4
ref: example.g.group_id
rows: 3
Extra:
*************************** 3. row ***************************
id: 1
select_type: SIMPLE
table: c
type: ref
possible_keys: idx_group_message_content_msg_id
key: idx_group_message_content_msg_id
key_len: 4
ref: example.m.id
rows: 2
Extra:

我们可以看出，MySQLQueryOptimizer选择了user_group作为驱动表，首先利用我们传入的条件user_id通过该表上面的索引user_group_uid_ind来进行const条件的索引ref查找，然后以user_group表中过滤出来的结果集的group_id字段作为查询条件，对group_message循环查询，然后再通过user_group和group_message两个表的结果集中的group_message的id作为条件与group_message_content的group_msg_id比较进行循环查询，才得到最终的结果。

这个过程可以通过如下表达式来表示：

for each record g_rec in table user_group that g_rec.user_id=1{

  for each record m_rec in group_message that m_rec.group_id=g_rec.group_id{

    for each record c_rec in group_message_content that c_rec.group_msg_id=m_rec.id

    pass the (g_rec.user_id, m_rec.subject, c_rec.content) row

    combination to output;

} }

下图可以更清晰的标识出实际的执行情况：

假设我们去掉group_message_content表上面的group_msg_id字段的索引，然后再看看执行计划会变成怎样：

sky@localhost : example 11:25:36> drop index idx_group_message_content_msg_id on
group_message_content;
Query OK, 96 rows affected (0.11 sec)

sky@localhost : example 10:21:06> explain

-> select m.subject msg_subject, c.content msg_content

-> from user_group g,group_message m,group_message_content c

-> where g.user_id = 1

-> and m.group_id = g.group_id

-> and c.group_msg_id = m.id\G

*************************** 1. row *************************** 

id: 1 
select_type: SIMPLE 
table: g 
type: ref 
possible_keys: idx_user_group_uid 
key: idx_user_group_uid 
key_len: 4 
ref: const 
rows: 2 Extra:

*************************** 2. row *************************** 

id: 1 
select_type: SIMPLE 
table: m 
type: ref 
possible_keys: PRIMARY,idx_group_message_gid_uid 
key: idx_group_message_gid_uid 
key_len: 4 
ref: example.g.group_id 
rows: 3 
Extra: *************************** 3. row *************************** 

id: 1 
select_type: SIMPLE 
table: c 
type: ALL 
possible_keys: NULL
key: NULL
key_len: NULL
ref: NULL
rows: 96
Extra: Using where; Using join buffer

我们看到不仅仅user_group表的访问从ref变成了ALL，此外，在最后一行的Extra信息从没有任何内容变成为Usingwhere;Usingjoinbuffer，也就是说，对于从ref变成ALL很容易理解，没有可以使用的索引的索引了嘛，当然得进行全表扫描了，Usingwhere也是因为变成全表扫描之后，我们需要取得的content字段只能通过对表中的数据进行where过滤才能取得，但是后面出现的Usingjoinbuffer是一个啥呢？

实际上，这里的Join正是利用到了我们在之前“MySQLServer性能优化”一章中所提到的一个Cache参数相关的内容，也就是我们通过join_buffer_size参数所设置的JoinBuffer。

实际上，JoinBuffer只有当我们的Join类型为ALL（如示例中），index，rang或者是index_merge的时候才能够使用，所以，在我们去掉group_message_content表的group_msg_id字段的索引之前，由于Join是ref类型的，所以我们的执行计划中并没有看到有使用JoinBuffer。

当我们使用了JoinBuffer之后，我们可以通过下面的这个表达式描述出示例中我们的Join完成过程：

for each record g_rec in table user_group{ 
  for each record m_rec in group_message that m_rec.group_id=g_rec.group_id
  { 
   put (g_rec, m_rec) into the buffer if (buffer is full) flush_buffer();

   } 
}

flush_buffer(){ 
  for each record c_rec in group_message_content that  c_rec.group_msg_id = c_rec.id{
    for each record in the buffer
    pass (g_rec.user_id, m_rec.subject, c_rec.content) row combination to output; } 
    empty the buffer;
}

当然，如果通过类似于上面的图片来展现或许大家会觉得更容易理解一些，如下：

通过上面的示例，我想大家应该对MySQL中NestedJoin的实现原理有了一个了解了，也应该清楚MySQL使用JoinBuffer的方法了。当然，这里并没有涉及到外连接的内容，实际对于外连接来说，可能存在的区别主要是连接顺序以及组合空值记录方面。

Join 语句的优化

在明白了MySQL中Join的实现原理之后，我们就比较清楚的知道该如何去优化一个一个Join语句了。
1.尽可能减少Join语句中的NestedLoop的循环总次数；如何减少NestedLoop的循环总次数？最有效的办法只有一个，那就是让驱动表的结果集尽可能的小，这也正是在本章第二节中的优化基本原则之一“永远用小结果集驱动大的结果集”。

为什么？因为驱动结果集越大，意味着需要循环的次数越多，也就是说在被驱动结果集上面所需要执行的查询检索次数会越多。比如，当两个表（表A和表B）Join的时候，如果表A通过WHERE条件过滤后有10条记录，而表B有20条记录。如果我们选择表A作为驱动表，也就是被驱动表的结果集为20，那么我们通过Join条件对被驱动表（表B）的比较过滤就会有10次。反之，如果我们选择表B作为驱动表，则需要有20次对表A的比较过滤。

当然，此优化的前提条件是通过Join条件对各个表的每次访问的资源消耗差别不是太大。如果访问存在较大的差别的时候（一般都是因为索引的区别），我们就不能简单的通过结果集的大小来判断需要Join语句的驱动顺序，而是要通过比较循环次数和每次循环所需要的消耗的乘积的大小来得到如何驱动更优化。

2.优先优化NestedLoop的内层循环；

不仅仅是在数据库的Join中应该做的，实际上在我们优化程序语言的时候也有类似的优化原则。内层循环是循环中执行次数最多的，每次循环节约很小的资源，在整个循环中就能节约很大的资源。

3.保证Join语句中被驱动表上Join条件字段已经被索引；
保证被驱动表上Join条件字段已经被索引的目的，正是针对上面两点的考虑，只有让被驱动表的Join条件字段被索引了，才能保证循环中每次查询都能够消耗较少的资源，这也正是优化内层循环的实际优化方法。

4.当无法保证被驱动表的Join条件字段被索引且内存资源充足的前提下，不要太吝惜JoinBuffer的设置；

当在某些特殊的环境中，我们的Join必须是All，Index，range或者是index_merge类型的时候，JoinBuffer就会派上用场了。在这种情况下，JoinBuffer的大小将对整个Join语句的消耗起到非常关键的作用。

mapreduce实现两表的join--原理及python和java代码实现

...ff0c;有一些特殊的技巧。本文首先介绍了Hadoop上通常的JOIN实现方法，然后给出了几种针对不同输入数据集的优化方法。 2.常见的join方法介绍假设要进行join的数据分别来自File1和File2. 2.1reducesidejoinreducesidejoin是一种最简单的... 查看详情

mapreduce实现两表的join--原理及python和java代码实现

synchronized的实现原理及锁优化(代码片段)

　　记得刚刚开始学习Java的时候，一遇到多线程情况就是synchronized。对于当时的我们来说，synchronized是如此的神奇且强大。我们赋予它一个名字“同步”，也成为我们解决多线程情况的良药，百试不爽。但是，随着学习的深入... 查看详情

javathread.join的作用和原理

很多人对Thread.join的作用以及实现了解得很少，毕竟这个api我们很少使用。这篇文章仍然会结合使用及原理进行深度分析内容导航Thread.join的作用Thread.join的实现原理什么时候会使用Thread.join Thread.join的作用之前有人问过... 查看详情

jetty最大线程数原理及优化

https://blog.csdn.net/majianxiong_lzu/article/details/90237408 jetty性能优化思路整理http://www.sxrczx.com/pages/gordon-tech.lofter.com/post/481906_24eb191.html 版权Jetty默认的线程池初始化大小为8，最大线程数查看详情

收藏|从sgd到nadamax，十种优化算法原理及实现

...，每一种算法的讲解都附有详细的公式过程以及代码实现。无论是什么优查看详情

收藏|从sgd到nadamax，十种优化算法原理及实现

...，每一种算法的讲解都附有详细的公式过程以及代码实现。无论是什么优查看详情

大表join大表的思路

参考OLTP的优化方式：1：限制输入的行（care条件要写全）2：限制输入的列（无用的列不要select）3：手动先分区再join4：采用map端的预聚合map_sidejoin5：抽取倾斜key然后加随机前缀处理，倍... 查看详情

mysql优化器内部join算法hashjoinnestloopjoin及classichashjoinchj过程详解(代码片段)

...器里的hashjoin算法在SQLServer、Oracle、postgress等数据库早已实现，而Mysql在8.0.18之后才支持。在8.0.18之前mysql只支持嵌套循环关联(nestedloopjoin),这其中最简单就是简易嵌套循环关联simplenestloopjoin&# 查看详情

golang实践录：ssh及scp实现的优化(代码片段)

本文对上文的实现的优化。问题提出上一文章中，基本上已经达到使用了，但为了适应更多场合，需要对上传、下载功能进行优化，本文实现对目录的传输。设计思路主要框架和上文相同，不再赘述。对于目... 查看详情

并查集的原理及实现(代码片段)

...些不相交集合（DisjointSets）的合并及查询问题。二、代码实现　　在并查集结构中，用一个pre[]数组来存储当前结点的父亲结点，有两个函数，found()函数用来寻找根结点，join()函数用来合并两个并查集。初始化　　把每个结... 查看详情

提效7倍，apachespark自适应查询优化在网易的深度实践及改进

本文基于ApahceSpark3.1.1版本，讲述AQE自适应查询优化的原理，以及网易数帆在AQE实践中遇到的痛点和做出的思考。前言自适应查询优化(AdaptiveQueryExecution,AQE)是Spark3.0版本引入的重大特性之一，可以在运行时动态的优化用户的SQL执... 查看详情

synchronized底层实现原理及锁优化(代码片段)

synchronized底层实现原理及锁优化_Medlen-CSDN博客_synchronized底层原理一、概述1、synchronized作用原子性：synchronized保证语句块内操作是原子的可见性：synchronized保证可见性（通过“在执行unlock之前，必须先把此变量同... 查看详情

synchronized底层实现原理及锁优化(代码片段)

wolfe准则(数学原理及matlab实现)——最优化建模算法与理论(代码片段)

文章目录一、前言二、Wolfe准则1.定义2.几何含义三、代码实现四、与Armjio准则的对比五、总结一、前言Goldstein准则能够使得函数值充分下降，但是它可能避开了最优的函数值，如下图所示：一维函数ϕ(α)\\phi(\\alpha)ϕ(... 查看详情

reactnative启动优化实践

参考技术ADiveintoReactNativeperformance阐述了基于RN实现的页面各部分加载时间占比图页面加载流程图（引用）从业务视角可以归纳为四个部分官方推出的FlatList及SectionList的一些问题官方对列表的一些配置推荐和实现建议OptimizingFlatlis... 查看详情

购物车的原理及实现

...（不用数据库）整体的思路图解:接下来就是代码实例来实现购物车的功能了:首先我们看下购物车和购物项两个JavaBean的设计:购物车:buyerCart.java1publicclassBuyerCartimplementsSerializable{23/**4*购物车5*/6privatestaticfinallongseri 查看详情

最优化建模算法理论之goldstein准则（数学原理及matlab实现）(代码片段)

...目录一、前言二、Goldstein准则1.定义2.几何含义三、代码实现四、与Armjio准则的对比五、总结一、前言为了克服Armijo准则的缺陷，我们需要引入其他准则来保证每一步的αk\\alpha^kαk不会太小。既然Armijo准则只要求点(α,ϕ(α))(\\a... 查看详情