mysql中的join操作算法介绍

Posted on |

本篇主要介绍mysql在join操作上采用的一些算法，以及如何做优化。主要分为Index Nested-Loop Join（NLJ）算法和Block Nested-Loop Join（BLJ）算法，基于Multi-Range Read优化的Batched Access Key（BKA）算法。

Block Nested-Loop Join (BNL)

通常在explain执行的extra中会有join_buffer(Block Nested-Loop Join)表示这次join操作使用了BNL算法。算法主要步骤是：

  • 1.从驱动表批量查出数据，放到join_buffer中。
  • 2.根据关联字段从被驱动表全表扫描数据，进行关联。
  • 3.被关联表查到数据之后进行回表。
  • 4.join_buffer中封装最终数据。

存在的性能问题：

  • 1.buffer_pool被占用，降低了缓存命中率。buffer_pool使用LRU(最近最少使用原则)理论上M*N不断的进行全表扫描，被驱动表数据会大量缓存在buffer_pool中。
  • 2.查询操作频繁，耗费大量cpu资源。同时会有大量的磁盘io。

实际运用过程中，如果出现了使用Block Nested-Loop Join(BNL)建议进行优化。对性能影响较大。

Index Nested-Loop Join (NLJ)

在上面的基础之上，采用了对被驱动表加索引的方式，极大的提升了效率，如果explain的结果extra中没有出现join_buffer(Block Nested-Loop Join)就表示这次join操作默认使用了NLJ算法。该算法有相对的优点：

  • 1.采用索引的方式定位磁盘块，减少了io次数和cpu资源的消耗。
  • 2.不会出现BNL算法可能淘汰热点页的问题。只会缓存不同的磁盘块数据。

Multi-Range Read (MRR)

该优化主要针对索引回表，MRR将随机回表读通过join_buffer根据主键id排序改变为顺序回表，一定程度上提升了回表效率，减少了回表次数加快了io读。mysql中可以通过设置参数开启该算法，默认是关闭的。

1
2
-- 通过设置参数开启mrr算法优化。mrr_cost_based=off
set optimizer_switch='mrr=on,mrr_cost_based=off,batched_key_access=on';

Batched Access Key (BKA)

基于Multi-Range Read优化的Batched Access Key（BKA）算法，实际上也是对NLJ算法的优化。执行流程如下：

  • 1.从驱动表中加载数据到join_buffer中得到数据块x，这里如果超出了容量，通过分段的方式加载。（可以通过调整join_buffer的大小改善）。
  • 2.通过索引查到join_buffer中所有的被驱动表上的数据块y，放到join_buffer中。
  • 3.通过join_buffer对数据块y进行主键id排序，得到主键id数据块z。
  • 4.根据排序好的主键id去回表执行顺序读，得到关联查询的数据结果集。
  • 5.在join_buffer中整合数据数据块x和z，返回结果集给客户端。

一般我们如果需要将BNL算法转成BKA算法，只需要在被驱动表上建立一个索引就行了。

特殊情况处理（无法建立索引）

当在被驱动表上建立索引的成本可能比较高的时候，不建议建立索引。例如，当关联的结果集实际上可以精简到一个小结果的时候，我们可以建立一个临时表，在临时表上建立索引。

1
2
3
4
-- 模拟一下，b字段所在的表数据量很大，但是我们只需要两千条，通过create temporary table建立临时表同时建立索引
create temporary table temp_t(id int primary key, a int, b int, index(b))engine=innodb;
insert into temp_t select * from t2 where b>=1 and b<=2000;
select * from t1 join temp_t on (t1.b=temp_t.b);

当然最好的操作方式还是数据引擎如果支持hash join就完美了，但是mysql是不支持的。如果支持hash join可以快速定位到记录，数据结构参考HashMap数据结构。如果数据引擎不支持，可以考虑在程序内存中将被驱动表的数据放在Set或者HashMap这样的数据结构中，进行关联。