Mysql 关联算法

MySQL 表关联的算法是 Nest Loop Join，是通过驱动表的结果集作为循环基础数据，然后一条一条地通过该结果集中的数据作为过滤条件到下一个表中查询数据，然后合并结果。

例: user表10000条数据，class表20条数据

select * from user u left join class c u.userid=c.userid

这样则需要用user表循环10000次才能查询出来，而如果用class表驱动user表则只需要循环20次就能查询出来。

• Classic Hash Join（CHJ）

MySQL 数据库虽然提供了 BKA 来优化传统的 JOIN 算法，的确在一定程度上可以提升 JOIN 的速度。但不可否认的是，仍然有许多用户对于 Hash Join 算法有着强烈的需求。Hash Join 不需要任何的索引，通过扫描表就能快速地进行 JOIN 查询，通过利用磁盘的带宽带最大程度的解决大数据量下的 JOIN 问题。

• Simple Nested-Loops Join（SNLJ，简单嵌套循环联接）

Simple Nested-Loops Join算法相当简单、直接。即驱动表中的每一条记录与被驱动表中的记录进行比较判断。对于两表联接来说，驱动表只会被访问一遍，但被驱动表却要被访问到好多遍，具体访问几遍取决于对驱动表执行单表查询后的结果集中的记录条数。对于内联接来说，选取哪个表为驱动表都没关系，而外联接的驱动表是固定的，也就是说左（外）联接的驱动表就是左边的那个表，右（外）联接的驱动表就是右边的那个表（这个只是一般情况，也有左联接驱动表选择右边的表）。

• Index Nested-Loops Join（INLJ，基于索引的嵌套循环联接）

SNLJ算法虽然简单明了，但是也是相当的粗暴，需要多次访问被驱动表（每一次都是全表扫描）。因此，在Join的优化时候，通常都会建议在被驱动表建立索引，以此降低Nested-Loop Join算法的开销，减少被驱动表扫描次数，MySQL数据库中使用较多的就是这种算法，以下称为INLJ

• Block Nested-Loops Join（BNL，基于块的嵌套循环联接）

扫描一个表的过程其实是先把这个表从磁盘上加载到内存中，然后从内存中比较匹配条件是否满足。但内存里可能并不能完全存放的下表中所有的记录，所以在扫描表前边记录的时候后边的记录可能还在磁盘上，等扫描到后边记录的时候可能内存不足，所以需要把前边的记录从内存中释放掉。我们前边又说过，采用 Simple Nested-Loop Join 算法的两表联接过程中，被驱动表可是要被访问好多次的，如果这个被驱动表中的数据特别多而且不能使用索引进行访问，那就相当于要从磁盘上读好几次这个表，这个 I/O 代价就非常大了，所以我们得想办法：尽量减少访问被驱动表的次数。

• Batched Key Access Join（BKA，批量键访问联接）

Index Nested-Loop Join 虽好，但是通过辅助索引进行联接后需要回表，这里需要大量的随机 I/O 操作。若能优化随机 I/O，那么就能极大的提升 Join 的性能。为此，MySQL 5.6（MariaDB 5.3）开始支持 Batched Key Access Join 算法（简称 BKA），该算法通过常见的空间换时间，随机 I/O 转顺序 I/O，以此来极大的提升 Join 的性能。