广州seo技术优化网站seo,包头网站设计公司,建设网站网站,常德制作网站在关系型数据库中#xff0c;表联接是一种常见的操作#xff0c;它使得我们可以根据不同的条件将多个表中的数据进行连接。而MySQL作为一种常用的关系型数据库#xff0c;其表联接算法包括NLJ、BNL、BKA、BNLH等多种#xff0c;在实际应用中选择不同的算法还需要考虑到数据…在关系型数据库中表联接是一种常见的操作它使得我们可以根据不同的条件将多个表中的数据进行连接。而MySQL作为一种常用的关系型数据库其表联接算法包括NLJ、BNL、BKA、BNLH等多种在实际应用中选择不同的算法还需要考虑到数据量、表结构等因素。本文将对MySQL中常见的表联接算法进行浅述包括各个算法的实现原理和适用场景。
SNLJ算法 Simple Nested-Loops Join,简单嵌套循环连接
算法简述
简单嵌套循环连接Simple Nested-Loops Join算法基于一个简单的思想即对于两个输入数据表R和SSimple Nested-Loops Join算法从表R中选取一条记录然后循环遍历表S的所有记录将R和S之间满足联接条件的记录匹配并将匹配后的结果存放在一个新的结果集中。然后算法继续从表R中选取下一条记录重复以上的操作直到R中所有的记录都被遍历过。见下图
优缺点
该算法的一个明显优点是实现简单实现逻辑清晰明了。
但是存在一个关键问题*被驱动表S的被扫描的次数等于驱动表R的记录数*。
当数据表R和S中的记录数Rn和Sn非常大时所需要扫描的记录条数为RnSn即笛卡尔积算法的执行时间会急剧增加。如果两R,S表都有十万条记录那么RnSn将会是100亿条这是无法被接受的。
适用场景
由于上述缺点不能够被接受MYSQL并没有采用该算法而是实现了效率更高的BNL算法。
BNL算法**** Block Nested-Loops Join基于块的嵌套循环联接
算法简述
BNL算法在SNLJ算法上做了优化
首先将驱动表尽量放到内存当中。理想状态下驱动表R全部被放到了内存。然后将被驱动表S表中的每条记录都在内存中与驱动表R表的记录逐个匹配筛选。
这样被驱动表S只需从磁盘扫描1次而驱动表也只需要从磁盘扫描一次。这样相比SNLJ算法扫描被驱动被的次数从Rn次降低到了1次大大降低了磁盘IO的压力从而提高了效率。
如果内存配置不足不能一次性将驱动表R所有记录加到内存Join Buffer那么驱动表会被切分成块再逐块加载到内存中。这也正是算法名称中Block的含义。
这时算法过程如下
将驱动表R分成N块首先将第一块N1的记录加载到内存Join Buffer中然后扫描被驱动表S将被驱动表S中的每条记录逐条加载到内存与内存中的N1记录进行匹配。然后将驱动表R的第二块N2的记录加载到内存中然后扫描被驱动表S将被驱动表S中的每条记录逐条加载到内存与内存中的N2记录进行匹配。重复以上操作直到驱动表的N块记录都添加到内存中并与被驱动表S所有记录匹配完毕。
可以看出上述过程中被驱动表被扫描的次数也只有驱动表R被分的块数N。这相较于SNLJ算法中的被扫描的次数驱动表R的记录数大大减少了。
图示如下
驱动表第一个块加载到内存并与被驱动表逐行比较
驱动表第二个块加载到内存并与被驱动表逐行比较
驱动表的其他块依次加入内存并于被驱动表比较不再画图表示。
适用场景
在被驱动表的联接字段不存在索引时会使用BNL算法。
相关配置
Join Buffer 由join_buffer_size配置控制这个配置在BNL算法中决定了驱动表被分的块数也即是被驱动表被扫描的次数所以对性能的提升尤为重要。
join_buffer_size 默认为256K这对于大量数据的场景很显然是不够的需要手动调大该配置。
join_buffer_size可以全局配置配置文件[mysqld]模块join_buffer_size参数也可以在会话级别配置select /* set_var(join_buffer_size248M) */ * from …;。
在大表使用BNL算法时适当提升该配置将会提升查询效率。
示例
表R和表S的name字段都没有索引。
Explain 时extra字段中存在using join buffer(flat,BNL join)表示用到了BNL算法。
INLJ算法 Index Nested-Loops Join基于索引的嵌套循环联接
算法简述
上述BNL算法尽管使用到了内存不必一遍遍的从磁盘上扫描被驱动表但是没有使用索引所以仍需要在内存中逐行的联接匹配查询所以联接时所需的比较的次数仍然是驱动表行数Rn被驱动表行数Sn即RnSn。
如果在联接时被驱动表存在索引这样就可以利用B树的特性层高固定数层一般3-4层将联接比较次数降为驱动表行数被驱动表B树的层高Rn3或Rn*4唯一索引的场景非唯一索引要加上同值个数这样就大大提高了联接匹配效率。
这就是基于索引的嵌套循环联接INLJ算法的优势。
适用场景
被驱动表的被联接字段有索引这样才可以用到INLJ算法从而使联接效率大大提高。
相关配置
该算法不需要配置就可以使用也是最常用的算法需要注意的是驱动表选择的问题。
*不同的联接语句哪个是驱动表*
使用左联接时left join时左侧表是驱动表。
使用右联接时right join时右侧表是驱动表。
使用内连接时join时由优化器自行选择驱动表。
使用内连接时可以使用straight join代替join从而指定左侧表是驱动表。
*选择驱动表的原则有哪些*
被驱动表的联接字段尽量有索引这样才可以用到高效的INLJ算法。
如果两个表的联接字段索引情况一样都有索引或都没有索引要小表驱动大表在通过where条件过滤后剩余的参与join计算的个字段数据总量小的表作为驱动表。这样无论是INLJ算法还是BNL算法效率都会相对较高。
示例 通过explain可以看到S表关联查询时用到了主键索引Extra中没有其他信息这说明用到了INLJ算法。
BKA算法Batched Key Access Join,批量键访问联接
算法简述
INLJ算法虽然已经用到了被驱动表的索引但是当用到的索引是二级索引且需要回表时就会因回表产生大量的随机IO。如下图 BKA算法就是在INLJ的基础上优化这个问题想办法将回表时的随机IO变成顺序IO。
具体来说BKA算法使用到了join_buffer一次性从驱动表或上次join的结果取出多条记录放到join_buffer中通过引擎的MRR接口得到的顺序的回表主键ID。进而使用有顺序的主键ID回表查询使得回表动作由随机IO变成了顺序IO从而提高效率。
如下图 进一步的可以使用MRR接口进行进一步优化。
在上述联接中查询被驱动表索引时上例中的S.score也是随机顺序的。可以先根据主键id排序然后再查询这就使对被驱动表的索引查询由随机顺序改为了顺序查询进而进一步提高查询效率。这也就是BKA算法中的MRR键排序Key Sorting for Batched Key Access。
适用场景
当被驱动表的联接字段是二级索引且不是覆盖索引需回表获取数据且需查询的数据量巨大可以考虑使用BKA算法进行优化。
相关配置
*开启MRR*
set optimizer_switch‘mrron’;
*开启MRR键排序*
set optimizer_switch‘mrr_sort_keyson’;
*调整join cache级别*
set join_cache_level6;
示例 执行计划中extra字段中有Using join buffer (flat, BKA join); Rowid-ordered scan说明使用到了BKA算法并对主键进行了排序然后扫描数据。
*开启MRR键排序的场景* 可以看到执行计划中extra字段多了Key-ordered说明使用了MRR键排序能力。
BNLH算法Block Nested Loop Hash join,基于块的嵌套循环哈希联接
算法简述
基本思想如下首先将驱动表数据加载到内存并在内存中建立一张哈希表。然后将对于被驱动表的每一条记录依次对做哈希运算将得到哈希值与内存中的驱动表的哈希值比较。这样只需要遍历一遍被驱动表就可以完成联接操作。
跟BNL算法一样如果join buffer 容量不足以一次性加载所有驱动表数据则会分块加载一部分这样被驱动表被扫描的次数就是驱动表所分的块数。
如下图 优缺点
BNLH算法的优势有两点一是不需要被驱动表有索引。二是相比于BNL算法联接在联接比较时每条被驱动表的记录需要遍历join buffer中所有驱动表数据而BHJ算法只需要比较一个哈希桶里的数据这就大大减少了比较的数据量从而提高了效率。
哈希算法虽好但是也有两个弊端。一是该算法只能用于等值联接的场景二是哈希计算本身也会增加一定的消耗。
适用场景
被驱动表联接字段不存在索引且联接查询为等值查询数据量特别大的场景。
相关配置
BHJ算法默认是关闭的需要将join_cache_level设置为大于等于4的值并显示地打开优化器的选项设置过程如下
set join_cache_join4;
set optimizer_switch‘join_cache_hashedon’;
示例 执行计划中extra字段中有Using join buffer (flat, BNLH join)说明使用到了BNLH哈希算法。
总结
本文介绍了MYSQL中常见的多种联接算法不同的算法有不同的适用场景。在SQL问题排查或者优化SQL语句时可以根据不同的场景选用不同的算法提高联接查询语句的执行效率。
其他示例环境说明
1.上文示例中数据库版本为10.9.5-MariaDB-log。
2.上文示例中表结构为如下
CREATE TABLE S (
id int(11) NOT NULL AUTO_INCREMENT,
name varchar(255) DEFAULT NULL,
score int(11) DEFAULT 0,
PRIMARY KEY (id),
KEY score (score)
) ENGINEInnoDB;
CREATE TABLE R (
id int(11) NOT NULL AUTO_INCREMENT,
name varchar(255) DEFAULT NULL,
score int(11) DEFAULT 0,
PRIMARY KEY (id),
KEY score (score)
) ENGINEInnoDB;
name varchar(255) DEFAULT NULL,
score int(11) DEFAULT 0,
PRIMARY KEY (id),
KEY score (score)
) ENGINEInnoDB;
CREATE TABLE R (
id int(11) NOT NULL AUTO_INCREMENT,
name varchar(255) DEFAULT NULL,
score int(11) DEFAULT 0,
PRIMARY KEY (id),
KEY score (score)
) ENGINEInnoDB;
