MySQL-JOIN优化

参考文献

• MySQL技术内幕 SQL编程 姜承尧

JOIN算法

• 当联接的表上有索引,Nestd-Loops Join是非常高效的算法.根据B+树的特性,其联接的时间复杂度为$O(N)$,若没有索引,则可视为最坏的情况,时间复杂度为$O(N^2)$

• 在选择JOIN算法时,会有优先级,理论上会优先判断能否使用INLJ、BNLJ(MySQL内部优化后,基本上不会出现Simple Nested-Loop Join)：

  • Index Nested-LoopJoin > Block Nested-Loop Join > Simple Nested-Loop Join

Simple Nested-Loop Join(笛卡尔积)

• 最简单的JOIN算法及外循环读取一行数据，根据关联条件列到内循环中匹配关联，在这种算法中，我们通常称外循环表为驱动表，称内循环表为被驱动表

• 简单嵌套循环连接实际上就是简单粗暴的嵌套循环,如果table1有$N$万条数据,table2有$M$万条数据,那么数据比较的次数=$N*M$​,这种查询效率会非常慢.table 1中的每条记录在比较匹配时,都会去扫描一次table 2 .

• 伪代码

  for each row r in R do
  	for each row s in S do
  		if r and s satisfy the join condition
  			then output the tuple <r,s>

  • 其中R为外部表(Outer Table),S表为内部表(Inner Table).假设在两张表表R和S上进行联接的列都不含索引.这个算法的扫描次数为$R_{n}+R_{n}*S_{n}$,扫描成本为$O(R_{n}*S_{n})$.$R_{n}$和$S_{n}$分别代表$R$表和$S$表中分别含有的记录数.

  

Index Nested-Loop Join(INLJ算法)

• 前提条件,内表的关联字段上有索引

• 时间复杂度计算,假设外层表table1行数为$N$,内层表table2行数为$M$

  • table1需要扫描整个表,$N$行记录
  • 扫描table2二级索引数据$\log_{2}{M}$
  • 回表操作扫描$\log_{2}{M}$
  • 总成本:$N*2\log_{2}{M}$,近似$N*\log_{2}{M}$​

• 伪代码

  for each row r in R do
  	lookup r in S index
  		if found s == r
  			then output the tuple <r,s>

  • 对于联接的列含有索引的情况,外部表的每条记录不再需要扫描整张内部表,只需要扫描内部表上的索引即可得到联接的判断结果.如果内部表联接列的索引高度为$S_{BH}$,那么算法的扫描次数为$R_{n}+S_{BH}*R_{n}$,扫描成本为$O(R_{n})$.而一般B+树的高度为3~4层.
  • 在INNER JOIN中,两张联接表的顺序是可以变换的,即R INNER JOIN S ON Condition P等效于S INNER JOIN R ON Condition P.优化器在一般情况下总是选择将联接列含有索引的表作为内部表.如果两张表$R$和$S$在联接的列上都有索引,并且索引的高度相同,那么优化器会选择将记录少的表作为外部表,这是因为内部表的扫描次数总是索引的高度,与记录的数量无关.

Block Nested-Loop Join(BNLJ算法)

• 在MySQL中, 由于直接使用Simple Nested-Loop Join性能比较差, 索引当不是使用索引列进行join连接查询的时候, 会使用Block Nested-Loop join进行连接查询

• 查询table1符合条件的记录,一次性缓存到join buffer中,然后拿join buffer里的数据批量与内层表table2的数据进行匹配,从而减少了内表的扫描次数(内表扫描一次就可以批量匹配join Buffer里面的外层表数据,即把join buffer当成一条记录看待)。

• 什么是Join Buffer？

  • join Buffer会缓存所有参与查询的列而不是只有join的列。

  • 可以通过调整join_buffer_size缓存大小

  • join_buffer_size的默认值是262K

    mysql> show VARIABLES like '%join_buffer_size%';
    +------------------+--------+
    | Variable_name    | Value  |
    +------------------+--------+
    | join_buffer_size | 262144 |
    +------------------+--------+
    1 row in set (0.01 sec)

  • 使用Block Nested-Loop Join算法需要开启优化器管理配置的optimizer_switch的设置block_nested_loop为on,默认为开启

• 时间复杂度计算

  • 假设外层表table1行数为$N$,内层表table2行数为$M$​
    • table1需要扫描整个表,$N$行记录
    • 对于table2中的每个记录都需要扫描多次, 总共需要扫描$M*P$, 其中$P$​代表的是table1加载到内存Join Buffer的次数
    • 总共的扫描次数是$N+P*M$, 其中$P$是和$N$的一个正相关的比例, $N$越小, $P$越小$P=\frac{N}{join buffer size}$, 所以总的扫描次数$N+\frac{N}{join buffer size} * M$​
    • 通过公式我们可以发现$N$越小, 总的扫描次数越小. 也就是说我们建议用小表驱动大表

• MySQL数据库使用Join Buffer的原则
  • 系统变量join_buffer_size决定了Join Buffer的大小
  • Join Buffer可以被用于联接ALL,index和range的类型
  • 每次联接使用一个Join Buffer,因此多表的联接可以使用多个Join Buffer
  • Join Buffer在联接发生之前进行分配,在SQL语句执行完成后进行释放
  • Join Buffer只存储需要进行查询操作的相关列数据,而不是整行的记录
• 对应EXPLAIN执行计划Extra中的Using join buffer

LEFT JOIN优化

• 在优化关联查询时,只有在被驱动表上建立索引才有效
• 需要注意的是,LEFT JOIN 中左侧的表是驱动表,右侧的表是被驱动表.因此,在进行关联查询时,应该在被驱动表上建立索引,以加速查询.如果在驱动表上建立索引,可能会降低查询效率,因为驱动表的数据通常比较小,全表扫描的代价不高.
• 其次,在 LEFT JOIN 中,如果需要对被驱动表进行过滤,应该使用条件过滤而不是将过滤条件放在ON子句中.这是因为,将过滤条件放在ON子句中可能会导致查询计划的改变,从而影响查询的效率.
• 此外,在 LEFT JOIN 中,如果需要对左侧的表进行过滤,应该在左侧的表上建立索引,否则过滤操作可能会导致全表扫描和性能下降.
• 最后,需要注意的是,在 LEFT JOIN 中,如果被驱动表中的某些字段允许为空,那么在进行关联查询时,需要使用IS NULL 或者 IS NOT NULL 条件来过滤这些值,否则关联查询可能会出现错误或者返回不正确的结果.

INNER JOIN优化

• 对于INNER JOIN,MySQL 会根据实际情况选取一个表作为驱动表,另一个表作为被驱动表.通常情况下,MySQL 会选择小表作为驱动表,大表作为被驱动表.

  • 这是因为,在关联查询中,驱动表的数据会被放入内存中进行缓存,而被驱动表的数据需要从磁盘中读取,因此将小表作为驱动表可以减少磁盘读取的次数,从而提高查询效率.

• 因此,当进行INNER JOIN时,应该将索引建立在大表上,以减少磁盘读取的次数.这样可以避免在内存中缓存大表的数据,同时也可以提高查询效率.

• 另外,还可以使用EXPLAIN命令来查看INNER JOIN的执行计划,从而确定 MySQL 选择的驱动表和被驱动表,以及使用的索引等信息.通过分析执行计划,可以进一步优化查询语句和索引,以提高查询效率.

• 需要注意的是,在进行INNER JOIN优化时,还需要考虑以下几个方面:

  1. 合理利用索引:对关联的列建立索引,使用合适的查询方式来进行关联操作,避免全表扫描和笛卡尔积等低效的操作.
  2. 避免使用SELECT *:只查询需要的字段,可以减少查询的数据量,提高查询效率.
  3. 调整数据类型:使用合适的数据类型存储数据,可以避免数据类型转换和类型不匹配等问题,从而提高查询效率.
  4. 使用合适的缓存:使用缓存可以避免重复查询和磁盘读取,从而提高查询效率

RIGHT JOIN优化

• 优化类型和LEFT JOIN类似,只不过被驱动表变成了左表