0%

MySQL Join算法

Simple Nested-Loop Join

Simple Nested-Loop Join的算法简单粗暴,其通过驱动表中的每一条记录与被驱动表中的记录进行对比,假设有表A和表B,表A有10000条记录,表B有1000条记录,那数据对比的次数就等于10000*1000次,效率是非常低下的。

simple

Block Nested-Loop Join

MySQL当然不会采用Simple Nested-Loop算法,而是使用了Block Nested-Loop Join的算法。该算法的流程是:

  1. 把表A的数据读入线程内存join_buffer中
  2. 扫描表B,把表B的每一行取出来,跟join_buffer中的数据进行对比,满足join条件则作为结果集的一部分返回

block join

在这个过程中,由于join_buffer是无序组织存放的,因此对表B的每一行,都要进行对比,总对比的次数也是表A的行数乘以表B的行数。这与simple Nested-Loop是一样的,但Block Nested-Loop是在内存中完成的,因此性能上会更好。

join_buffer是由参数join_buffer_size控制的,默认为256K。如果数据量较大,一次性放不下表A的数据,这时会采用分段放的方式,简单来说就是在join_buffer写满后立马与表B进行对比返回结果集,再将join_buffer清空进行后面数据的对比,直到对比完成。虽然对比次数不变,但由于进行了分段,驱动表的大小会影响扫描行数,驱动表越大,扫描行数就越多,因此这种情况下应当利用小表作为驱动表。

Index Nested-Loop Join

Index Nested-Loop Join是基于索引进行连接,驱动表通过被驱动表上的索引进行匹配,避免与被驱动表的每条记录都进行对比,减少对比次数,提升Join性能

1
2
3
4
5
6
7
root@test 14:13:  explain select * from t1 straight_join t2 on (t1.a=t2.a);
+----+-------------+-------+------------+------+---------------+------+---------+-----------+------+----------+-------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+-------+------------+------+---------------+------+---------+-----------+------+----------+-------------+
| 1 | SIMPLE | t1 | NULL | ALL | a | NULL | NULL | NULL | 100 | 100.00 | Using where |
| 1 | SIMPLE | t2 | NULL | ref | a | a | 5 | test.t1.a | 1 | 100.00 | NULL |
+----+-------------+-------+------------+------+---------------+------+---------+-----------+------+----------+-------------+

t1是驱动表,t2是被驱动表,t2上的a字段有索引,join使用了该索引,其执行过程如下:

  1. 从表t1中读取一行记录A1
  2. 从数据行A1中取出字段a到t2里去查找
  3. 取出t2中满足条件的行,与A1组成一行作为结果集
  4. 重复上述3个步骤,直到t1遍历完成

index join

这个时候怎么去选择驱动表与被驱动表呢?在上面的例子中,驱动表走的是全表扫描,而被驱动表走的是索引树搜索,应该将小表作为驱动表

Batched Key Access

在正式介绍BKA之前,我们需要先了解MRR优化,这个优化主目的主要是尽量使用顺序IO。MRR在通过二级索引获取到主键ID后,将ID值放入read_rnd_buffer中,然后对其进行排序,利用排序后的ID数组遍历主键索引查找记录并返回结果集,优化了回表性能。

理解了MRR优化后,我们就来看看Batched Key Access(BKA)算法,BKA算法是对INDEX Nested-Loop Join算法的优化。INDEX Nested-Loop的执行逻辑是从驱动表中一行行取出join字段,再到被驱动表去做join,这样每次都是匹配一个值,无法使用MRR优化。这时可以参考Block Nested-Loop算法将驱动表的数据临时存放在Join buffer中,这时就可以通过MRR优化来提升性能。

BKA

如果想要启用BKA优化算法的话,需要进行设置

1
set optimizer_switch='mrr=on,mrr_cost_based=off,batched_key_access=on';

MariaDB Hash Join

MariaDB支持classic hash join,它根据join buffer中的数据创建哈希表,被驱动表通过哈希算法进行查找,从而在Block Nested-Loop Join的基础上进一步减少被驱动表的比较次数,提升Join性能
block hash join

要使用Classic Hash Join,需要将join_cache_level设置为大于等于4的值,并显示打开优化器选项

1
2
set join_cache_join=4;
set optimizer_switch='join_cache_hashed=on';

优化建议

  1. Block Nested-Loop Join算法的性能问题不仅仅是因为会导致IO压力,由于频繁扫描表可能会导致业务数据无法进入LRU链表中的young区,内存命中率降低。这种情况下,建议给被驱动表的join字段添加索引,把Block Nested-Loop Join转换为Batched Key Access
  2. 在使用Join时,应该选择小表作为驱动表