MySQL中Nested-Loop Join算法小结
不知不觉的玩了两年多的MySQL，发现很多人都说MySQL对比Oracle来说，优化器做的比较差，其实某种程度上来说确实是这样，但是毕竟MySQL才到5.7版本，Oracle都已经发展到12c了，今天我就看了看MySQL的连接算法，嗯，现在来说还是不支持HashJoin，只有Nested-LoopJoin，那今天就总结一下我学习的心得吧。
Nested-LoopJoin基本算法实现，伪代码是这样：
foreachrowint1matchingrange{
foreachrowint2matchingreferencekey{
foreachrowint3{
ifrowsatisfiesjoinconditions,
sendtoclient
}
}
}
这段代码很简单，虽然我也不怎么会写代码，但是我还是看得懂的。这里假设有三张表，t1,t2,t3，这段代码，分别会展现出explain计划里的range,ref和ALL，表现在SQL执行计划层里，t3就会进行一次全表扫描，我今天在这个地方看到了一个很妖的优化SQL方法，Straight-join：http://hidba.ga/2014/09/26/join-query-in-mysql/，其中提到了驱动表的概念，那么对应过来，驱动表就是伪代码里的t3表，博文里说MySQL会自动选择结果集最小的表作为驱动表，作为算法分析，这样选择驱动表确实是消耗最小的办法。那么这里还提到了，通过缩小驱动表结果集进行连接优化，那么根据这个算法来看，结果集较小的驱动表确实可以使循环次数减少。
当然了，MySQL自己在这个算法基础上，演进出了BlockNested-Loopjoin算法，其实基本上和上面的算法没有区别，伪代码如下：
foreachrowint1matchingrange{
foreachrowint2matchingreferencekey{
storeusedcolumnsfromt1,t2injoinbuffer
ifbufferisfull{
foreachrowint3{
foreacht1,t2combinationinjoinbuffer{
ifrowsatisfiesjoinconditions,
sendtoclient
}
}
emptybuffer
}
}
}
ifbufferisnotempty{
foreachrowint3{
foreacht1,t2combinationinjoinbuffer{
ifrowsatisfiesjoinconditions,
sendtoclient
}
}
}
这个算法，将外层循环的数据缓存在joinbuffer中，内层循环中的表回合buffer中的数据进行对比，从而减少循环次数，这样便可以提高效率。官网上有个example，我有点没有看明白：如果有10行被缓存到了buffer里，这10行被传给了内层循环，内层循环的所有行都会和buffer中的这10行进行对比。原文是这样的：
Forexample,if10rowsarereadintoabufferandthebufferispassedtothenextinnerloop,eachrowreadintheinnerloopcanbecomparedagainstall10rowsinthebuffer
如果S指的是t1,t2组合在缓存中的大小，C是这些组合在buffer中的数量，那么t3表被扫描的次数应该是：
(S*C)/join_buffer_size+1
根据这个算式，join_buffer_size越大，扫描的次数越小，如果join_buffer_size到了能缓存所有之前的行组合，那么这时就是性能最好的时候，之后再增大也就没有什么效果了。
在有索引的情况下，MySQL会尝试去使用IndexNested-LoopJoin算法，在有些情况下，可能Join的列就是没有索引，那么这时MySQL的选择绝对不会是最先介绍的SimpleNested-LoopJoin算法，因为那个算法太粗暴，不忍直视。数据量大些的复杂SQL估计几年都可能跑不出结果，如果你不信，那就是tooyoungtoosimple。或者Inside君可以给你些SQL跑跑看。
SimpleNested-LoopJoin算法的缺点在于其对于内表的扫描次数太多，从而导致扫描的记录太过庞大。BlockNested-LoopJoin算法较SimpleNested-LoopJoin的改进就在于可以减少内表的扫描次数，甚至可以和HashJoin算法一样，仅需扫描内表一次。