MySQL join 算法初探
最近公司某业务模块需要优化mysql联表数据查询效率，虽然已经给查询字段添加了索引，并且使用临时表减少联表环节，但是由于部分表数据量很大（亿级），查询速度依旧很慢（十几分钟跑不出来结果）
于是想了解一下mysql的join操作原理，下面是mysql官方文档对join操作的说明
MySQL resolves all joins using a nested-loop join method. This means that MySQL reads a row from the first table, and then finds a matching row in the second table, the third table, and so on.
mysql使用的是一种名为Nested-loop Join的算法。
这种算法的最基本的形态是Simple Nested-loop Join，这是一种非常朴素的算法
假设我们有n张表做join，分别为table_1,table_2,table_3...table_n，其中table_k中的每一条记录我们记为row_k_i，那么这个过程用伪代码写出来就是
for(row_1 in table_1){
for(row_2 in table_2){
if(row_1,row_2满足join条件){
...
for(row_n in table_n){
if(row_1,row_2...row_n都满足join条件){
把row_1,row_2...row_n的join结果加到结果集
}
}
}
}
}
这种算法缺陷也很明显，随着join表数量的增加，计算量呈指数上升。如果其中出现了一张数据量很大的表，对整个过程的效率也影响很大。
于是，mysql5.5对这个算法进行了优化，新增了Index Nested-loop Join，Block Nested-loop Join，其中Index Nested-loop Join是针对有索引的情况，而Block Nested-loop Join是针对没有命中索引的情况
由于索引的效率要比逐条循环效率高，所以当使用索引联表时，能大大加快查询速度，但是索引也不是万能的，如果你需要取索引以外的字段，那么依旧需要回到表中查出相应的数据
而对于没有索引的情况，优化的效果就非常有限，只是从逐条匹配变为先读取一批放到缓存中，然后缓存批量匹配，能够一定程度上减少IO操作的开销
在mysql5.6中针对有索引的情况，又进一步做了优化，新增了一种叫Batched Key Access Join算法，该算法对索引也引入了buffer的思想
这种算法不是默认开启的，如果想要使用，就需要修改mysql的配置
mysql> SET global optimizer_switch='mrr=on,mrr_cost_based=off,batched_key_access=on';
这里额外补充一下MRR（Multi-Range Read）相关的说明，MRR也是mysql5.6新增的一个功能，该功能将随机IO转变为顺序IO以提升数据读取效率
下图我们可以看到，在没有开启前，数据的读取是乱序的，对于硬盘来说就是要转好几圈
但是开启MRR后，由于在读取前我们预先对数据区域进行了排序，磁盘只要转一圈就能获取到所有数据
参考资料：
https://blog.csdn.net/u010841296/article/details/89790399
https://blog.csdn.net/csd753111111/article/details/100428559