Blage's Coding
phan
2023-07-09
目录

join

# join

使用join存在什么问题？下面围绕join语句的执行流程，使用前面学过的索引知识展开。

# join语句执行流程

场景：t1和t2表同时都有主键id，索引字段a，无索引字段b。t2表插入了1000行数据，t1表中插入了100行数据。

# 1.索引join查询(NLJ)

使用straight_join显示指定t1作为驱动表，t2作为被驱动表。整个语句执行过程如下：

select * from t1 straight_join t2 on (t1.a=t2.a);
1
  1. 首先对t1会进行全表查询，然后将每一行扫描的数据放到t2表中进行比较。因此t1总共扫描100行数据。
  2. 由于是对t2的a字段进行匹配，可以走索引。因此每行t1的行记录都会取出a字段值，在t2的a字段索引树进行比对，然后回表拿到t2的行记录并和t1的行记录拼接。
  3. 这里假设t1表中的数据和t2唯一对应。因此t2也会扫描100行数据。总共扫描行数为200。

可以发现在这种条件下的join语句有如下特点：

  • 走了索引的join语句比拆成多个单表语句的执行性能好。如果选择拆成单表的语句，首先从t1拿到全表扫描结果，然后每次取出a字段的值，接着执行100次SQL语句拼接where a=$t1.a。扫描行数虽然和join相同，但是执行了101条SQL语句。
  • 驱动表会走全表扫描，因此尽量让小表作为驱动表。

# 2.不走索引的join查询(BNL)

如果join字段不走索引，那么不适合使用join查询，应该拆成单表。

# 2.1不分块

如果是被驱动表没有走索引又会怎么样？t2会扫描100*1000行数据么？实际算法流程如下：

select * from t1 straight_join t2 on (t1.a=t2.b);
1
  1. 将t1表的所有行数据读入线程的内存join_buffer当中。扫描行数100
  2. t2表进行全表扫描，取出扫描到的每行数据，与内存join_buffer中的t1表数据进行比对，满足连接条件的与t2表记录拼接作为其中一个结果集。扫描行数1000，总共扫描行数1100。比较判断次数100*1000=十万次。
  3. 相比于t2表直接扫描十万行，时间复杂度相同。但是比较判断操作是在内存进行，因此速度上会快很多。

此时驱动表无论是大表还是小表，比较次数和扫描次数都没有区别。

# 2.2分块

这里如果join_buffer一次性放不下表t1(假设只能放进60行记录)，那么需要将t1表分块放进join_buffer：

  1. 先将t1表前60行记录放入内存join_buffer。
  2. 扫描t2表的所有行记录，并进行比较。此时扫描行数1000条。
  3. 清空join_buffer，然后将t1表后40行记录放入join_buffer当中。
  4. 再次扫描t2表所有记录，并进行比较判断。总比较次数不变还是十万次，而总扫描函数翻倍变为2000条。

根据计算，分块join场景应该让小表作为驱动表，并且应该将join_buffer_size设大一些，从而降低总扫描次数，提高join语句执行效率。

# 3.BNL(分块不走索引)算法对buffer pool的影响

前面提到如果buffer pool分为old区域和young区域，如果old区域的数据页超过1s如果再次被访问就会被放到young区域。对于使用了BNL算法的join语句，在以下情况可能会影响到buffer pool：

  • 被驱动表是冷数据表。在BNL算法中驱动表被分块，因此被驱动表会被扫描多次与每个块进行比较,而对于大被驱动表第二次扫描的时间间隔很可能会超过1s。从而导致冷表数据都进入young区域。
  • 被驱动冷表是一个大表。这种情况下，会导致正常业务的数据页没法进入young区域。假设此时业务数据页还在old区域，在执行join语句时，因为当前被驱动大表数据页放不下old区域，导致old区域需要淘汰内存页(包括业务的数据页)。

因此大表join不仅对磁盘IO有影响，同时也会对内存命中率造成影响。所以这种情况下，只能够增大join_buffer内存大小，尽可能的减少被驱动表的扫描次数。

# 4.总结

小表

对于表t1与t2来说，经过where条件筛选后，参与join的行数越小的，以及根据select字段和on字段判断参与join连接的行数据量越小的表称之为”小表“。

NLJ中驱动表是取出一行行进行比较的表，BNL中驱动表是被一行行记录比较的表。

  • 什么情况下使用join语句？

    • 如果被驱动表使用了索引(explain查看Extra字段为Index Nested-Loop)，则可以使用join
    • 如果join的字段都用不上索引(explain查看Extra字段为Block Nested-Loop)，则不能够使用join。需要拆分成单表SQL语句，避免过多的行扫描。

  • 查询语句使用join的情况下，应该尽量保证”小表“作为驱动表。

# join语句优化

接下来谈论上面两种join算法(使用索引NLJ和不使用索引分块BNL)的优化。

场景：t1表插入了1000行数据，其中每行的a=1001-id，也就是id的逆序结果。t2表插入了100万行数据。

# 1.Muti-Range Read优化

Muti-Range Read(MRR)优化：在多值查询下，尽量使用顺序读盘。具体来说，多行记录拿到id值进行回表时，如果按照主键递增的顺序查询的话，对磁盘读可以近似于顺序读，从而提高性能。

select * from t1 where a>=1 and a<=100;
1

上述SQL语句对于表t1来说，根据a字段进行回表时每个id值都是倒序存储(id随机读性能查)，因此InnoDB会对a字段取到的id值进行MRR优化(explain分析后Extra字段出现using MRR)，具体如下：

  1. 根据a索引定位到所有满足条件的值，并将所有id值放入到read_rnd_buffer当中。
  2. 在read_rnd_buffer里对id值进行递增排序。
  3. 根据read_rnd_buffer内有序的id，从聚簇索引树中查叶子节点记录，并添加到结果集当中。

另外要想稳定使用MRR，则MySQL需要设置如下参数：

set optimizer_switch="mrr_cost_based=off";
1

# 2.NLJ优化——Batched Key Access

Batched Key Access(BKA)算法：本质上是NLJ算法+MRR优化。

select * from t1 straight_join t2 on (t1.a=t2.a);
1

在NLJ算法中，驱动表t1每次只会从磁盘拿一行数据到内存，与整个被驱动表中的所有行记录进行比对最后回表，因此t2表每次只会匹配一行记录并回表一次，这时如果使用MRR优化就没有任何优势。

要使用MRR关键要保证被驱动表的回表时，能够批量的回表，如果一行一行进行回表那就不能保证每次回表id的递增有序性了。

具体来说，在NLJ算法前，先把驱动表数据放到join_buffer当中，然后再从内存中批量往t2表传入多个t1表的行记录，此时就能用上MRR优化。

另外，要启用BKA算法，需要在执行SQL语句之前进行设置：

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

# 3.BNL优化——建立索引

前面提到BNL算法性能比较差，因此在join语句应该尽量避免使用BNL。核心做法就是建立索引转化为BKA。

select * from t1 join t2 on (t1.b=t2.b) where t2.b>=1 and t2.b<=2000;
1

①最直接的方法就是在被驱动表上建立索引，从而将BNL转化为BKA算法。

②如果是一个低频SQL，那么建立索引比较浪费。可以考虑使用临时表，在临时表上建立索引：

  1. 首先将表t2满足where筛选条件的数据放在临时表tmp_t当中，扫描行数为100万

  2. 然后给临时表tmp_t上的b字段建立索引

  3. t1表与临时表tmp_t做join操作，扫描行数为t1 1000次+临时表tmp_t满足条件记录数。比较次数上因为临时表含有索引所以会很快。

    临时表方案对应的SQL语句：

    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);
    1
    2
    3

# 4.哈希join

分块BNL算法要比较十亿次，原因在于join_buffer中的行记录是无序的，每行记录都要与join_buffer里t1表所有的数据一一比较。而如果t1表数据不是一个无序数组，而是一个哈希表，那么只需要100万次(t2表大小)哈希查找。

因为MySQL不支持哈希join，因此可以在业务端实现：

  1. 执行select * from t1拿到t1表所有1000行数据，并在业务端放入一个哈希结构
  2. 执行select * from t2 where b>=1 and b<=2000拿到符合条件的数据。这里扫描行数100万行
  3. 在业务端把2000行数据一行一行取出来，拿到t1哈希表中进行比对。总共进行2000次哈希查找

理论上效果要比临时表方案好。因为基于哈希的比较要快于基于索引比较。

# 5.三表join优化

对于多表的join语句，驱动表只有一个，被驱动表会有多个。执行过程会嵌套进行❓采用BKA进行优化时，每多一个join，就会多一个join_buffer。假设按照t1>t2>t3连接顺序，具体如下：

  1. 首先t1表、t2表取出所有满足条件的行数据放入到join_buffer1和join_buffer2当中
  2. 从join_buffer1当中取出一行数据，与t2表进行比较判断。
  3. 从join_buffer2中取出上一步满足要求的t2行数据，与t3表进行比较判断。
  4. 如果把上述满足条件的记录拼接起来作为结果集。
  5. 此时t1相当于执行完了一条行数据，重复执行步骤2，3，4直到所有t1行数据比较完。

假设三个表的结构相同，分别只建立了id主键，试分析以下SQL语句如何优化更高效：

select * from t1 join t2 on(t1.a=t2.a) join t3 on (t2.b=t3.b) where t1.c>=X and t2.c>=Y and t3.c>=Z;
1

优化时首先需要尽可能使用BKA算法，然后使用小表作为驱动表。先确定小表再确定索引，小表需要根据X、Y、Z满足条件的行数判断：

  • 如果t3表为小表，则连接顺序t3>t2>t1，在t2.b和t1.a建立索引。同时需要在每个表c字段加索引，目的是为了快速通过where条件筛选拿到实际参与join的行记录。
  • 如果t1表为小表，则连接顺序t1>t2>t3，在t2.a和t3.b建立索引。同时需要在每个表c字段加索引，目的是为了快速通过where条件筛选拿到实际参与join的行记录。
  • 而如果是t2表为小表 ，则需要进一步评估另外两个条件的过滤效果。

# join语句写法(left join与on,where选择)

实验场景：

create table a(f1 int, f2 int, index(f1))engine=innodb;
create table b(f1 int, f2 int)engine=innodb;
insert into a values(1,1),(2,2),(3,3),(4,4),(5,5),(6,6);
insert into b values(3,3),(4,4),(5,5),(6,6),(7,7),(8,8);
1
2
3
4

💡原则：NULL与任何值执行等值判断和不等值判断的结果，都是NULL。

💡left join语义：左表匹配的行记录也加入到结果集以外，未匹配的行记录也需要加入到结果集(此时右表字段用NULL补充)。

💡explain后Extra字段没有显示使用哪种join算法，则默认表示当前使用的是NLJ索引算法。

分析如下四条条SQL语句：

select * from a left join b on(a.f1=b.f1) and (a.f2=b.f2); /*Q1*/
select * from a left join b on(a.f1=b.f1) where (a.f2=b.f2); /*Q2*/

select * from a join b on(a.f1=b.f1) and (a.f2=b.f2); /*Q3*/
select * from a join b on(a.f1=b.f1) where (a.f2=b.f2);/*Q4*/
1
2
3
4
5

# Q1

执行流程如下：

  1. a为驱动表，b为被驱动表。显然因为b表的字段都不存在索引，所以直接走分块BNL算法。
  2. 首先将a表的所有数据都放入到join_buffer
  3. 然后拿出b表的每一行记录与join_buffer中的每一行记录进行比较，匹配则加入到结果集中
  4. 最后join_buffer中还剩下两条记录(1，1)和(2，2)没有被匹配，根据left join语义也一并加入结果集。B表字段使用NULL填充。得到的结果集有6条。

# Q2

观察Extra字段可以得出整个join语句使用NLJ算法，没有使用上join_buffer，并且a的f1索引字段被使用上了。执行流程如下：

  1. NLJ算法中a表的索引被使用，那么显然b表是驱动表，而a表是被驱动表。
  2. 每次从b表中取出一条数据，首先先用b.f1字段去查，如果匹配，那么再判断该条记录的f2是否等于b.f2。如果都满足则作为结果集一部分返回。
    • 根据上面提到的规则，假设先不考虑where条件，仅仅只是on筛选后，那么得到的所有未匹配的a表记录上的b表字段都是NULL；接着where筛选时，b.f2的null字段与a.f2非空字段比较肯定不能通过筛选。所以整个语句虽然用了left join，但因为存在where筛选规则限制，所以无论如何最终都不可能出现a表未匹配+b表字段null补齐的行记录。
    • 也就是说left join的语义失效，整个语句改写退化为join。这样就可以使用上NLJ算法了。
  3. 重复步骤2，知道b表所有行记录都筛选过。最后得到的结果集有4条。

# Q3&Q4

show warnings经过优化器优化后，两条语句都被改写为：

select * from a join b where (a.f1=b.f1) and (a.f2=b.f2);
1

# 总结

①如果使用left join，那么当前左边的表不一定是驱动表。

②如果需要join left的语义，那么右表的字段不能放入到where中进行等值判断或不等值判断，必须全部写在on当中。否则会退化为普通join。

③如果不需要left join的语义，那么使用join连接的过滤查询条件写在on和where没有区别，最终都会被优化到where条件上。

# Simple NLJ算法性能问题

Simple NLJ：指的是NLJ算法被驱动表没用上索引，需要全表扫描的一种情况。

Simple NLJ算法的被驱动是在磁盘当中，每行驱动表的行记录都会与整个磁盘表(“被比较表”)进行全表扫描匹配。

BNL算法的“被比较表”放在join_buffer，每行被驱动表行记录都会与join_buffer进行全扫描匹配。

很显性能上BNL会更好于Simple NLJ算法，从以下几个方面来看：

  1. 比较时，被比较表的磁盘IO开销：

    • BNL的“被比较表”稳定就在内存join_buffer中。

    • Simple NLJ如果驱动表第k条记录比较时，buffer pooi上的“被比较表”的数据页恰巧被淘汰了，那么就需要重新等待一次磁盘IO，开销更大。

      另外SNLJ算法被比较表天然会被多次访问比较，移到young区的head后还会影响正常页面的数据页命中率。

  2. “查找下一条记录”操作成本：

    • BNL在join_buffer数组上进行遍历，成本更低。
    • SNLJ内存数据页通过类似于指针操作，成本更高。
编辑 (opens new window)
#数据库
上次更新: 2023/12/15, 15:49:57
全表扫描与内存占用
临时表与内存表

← 临时表与内存表→

Theme by Vdoing | Copyright © 2023-2024 blageCoder