MySQL常用关键字实现原理
dd
  2023-07-10 18:52:55 2023-07-10 18:52   2023-08-05 18:57:16      4.1k 字  14 分钟  

group by

MySQL中group by实现方式有三种：松散索引、紧凑索引、临时文件。其中松散索引和紧凑索引是利用现有的索引来完成，临时文件是在完全无法使用索引的场景下使用的

松散索引

当MySQL完全利用索引扫描实现GROUP BY时，并不需要扫描所有满足条件的索引键即可完成操作得出结果

举例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
create index idx_gid_uid_gc
on group_message(group_id,user_id,gmt_create);

EXPLAIN SELECT user_id,max(gmt_create) 
FROM group_message 
WHERE group_id < 10 
GROUP BY group_id,user_id\G
只列重点：

*************************** 1. row ***************************

key: idx_gid_uid_gc 

Extra: Using where; Using index for group-by

Extra 信息中有信息显示“Using index for group-by”，表示使用松散索引扫描实现GROUP BY 操作

利用松散索引实现GROUP BY 条件：

  • GROUP BY条件字段必须在同一个索引中最前面的连续位置（最左前缀原则）
  • 在使用GROUP BY的时候只能使用MAX或MIN这两个聚合函数（由于索引的有序性只需要扫描到一条就可以了，不需要扫描全部）
  • 如果引用到了该索引中GROUP BY条件之外的字段条件，必须以常量形式存储（保证查询的准确性和索引的有效性）
    • 当在查询中提供非常量的条件值时，数据库无法通过直接访问索引来确定匹配的行，而可能需要扫描整个数据表来找到符合条件的行

比如有一个联合索引包含order_id、customer_id、order_date 和 total_amount

SQL语句

1
2
3
4
5
SELECT customer_id, SUM(total_amount) as total_sum
FROM orders
WHERE order_date >= DATE_SUB(NOW(), INTERVAL 1 WEEK)
GROUP BY customer_id
HAVING total_sum > 100;

order_date 字段作为 WHERE 条件的限制，由于 order_date 不是 GROUP BY 条件之一，它属于 GROUP BY 条件之外的字段条件

此时，如果我们以非常量形式提供条件值，比如使用一个变量来表示查询的起始日期，那么数据库无法通过直接访问索引来确定匹配的行，而可能需要扫描整个数据表来找到符合条件的行。这样会导致查询效率低下

因此，在这种情况下，我们需要将条件值限制为常量形式，如使用具体的日期值或函数表达式来表示。这样，数据库可以直接通过索引定位到满足条件的数据行，提高查询性能

松散索引扫描的效率比较高：

因为不需要扫描所有满足条件的行，可以提前返回

紧凑索引

在扫描索引时读取所有满足条件的索引键，然后再根据读取的数据完成GROUP BY操作得到相应的结果

1
2
3
4
5
6
7
8
9
10
11
EXPLAIN SELECT max(gmt_create) 
FROM group_message 
WHERE group_id = 2 
GROUP BY user_id\G
只列重点：

*************************** 1. row ***************************

key: idx_gid_uid_gc

Extra: Using where; Using index

执行计划的 Extra 信息中已经没有“Using index for group-by”了，但并不是说 MySQL 的 GROUP BY 操作并不是通过索引完成的，只不过是需要访问 WHERE 条件所限定的所有索引键信息之后才能得出结果

MySQL Query Optimizer 首先会选择尝试通过松散索引扫描来实现 GROUP BY 操作， 当发现某些情况无法满足松散索引扫描实现 GROUP BY 的要求之后，才会尝试通过紧凑索引扫描来实现

当 GROUP BY 条件字段并不连续或者不是索引前缀部分的时候，MySQL Query Optimizer 无法使用松散索引扫描，因为缺失的索引键信息无法得到。但是， 如果 Query 语句中存在一个常量值来引用缺失的索引键，因为常量填充了搜索关键字中的“差距”，可以形成完整的索引前缀。这些索引前缀可以用于索引查找。那么此时mysql的执行过程为先根据where语句进行一次选择，对选出来的结果集，可以利用索引。这种方式，从整体上来说，group by并没有利用索引，但是从过程来说，在选出的结果中利用了索引，这种方式就是紧凑索引

临时表

当 MySQL Query Optimizer 无法找到合适的索引可以利用的时候，就不得不先读取需要的数据，然后通过临时表和排序来完成 GROUP BY 操作

1
2
3
4
5
6
7
8
XPLAIN SELECT max(gmt_create) FROM group_message WHERE group_id > 1 and group_id < 10 GROUP BY user_id\G
只列重点：

*************************** 1. row ***************************

key: idx_gid_uid_gc

Extra: Using where; Using index; Using temporary; Using filesort

采用哈希算法进行group by将相同的数值存放在一起，快速得到分组的结果，之后再进行排序，但是内存消耗会比较大

  • 哈希表需要分配内存空间存储分组结果
  • 哈希冲突的时候需要额外的内存空间存储冲突的值

因此如果数据量太大，可以使用 SQL_BIG_RESULT 这个hint，来告诉优化器直接使用排序算法（归并排序）得到 group by 的结果

优化思路

  • 尽可能让 MySQL 可以利用索引来完成 GROUP BY 操作，最好是松散索引扫描的方式
  • 当无法使用索引完成 GROUP BY 的时候，由于要使用到临时表且需要 filesort，所以我们必须要有足够的 sort_buffer_size 来供 MySQL 排序的时候使用，而且尽量不要进行大结果集的 GROUP BY 操作，因为如果超出系统设置的临时表大小的时候会出现将临时表数据 copy 到磁盘上面再进行操作，这时候的排序分组操作性能将是成数量级的下降
  • 如果对 group by 语句的结果没有排序要求，要在语句后面加 order by null

JOIN

JOIN类型

  • INNER JOIN：将两个表中符合条件的行组合在一起。返回的结果集只包含满足连接条件的行，也就是两个表中都存在的行
  • LEFT JOIN：返回左表中所有行以及符合条件的右表中的行。如果右表中没有匹配的行则用NULL填充
  • RIGHT JOIN：返回右表中所有行以及符合条件的左表中的行。如果左表中没有匹配的行则用NULL填充
  • FULL OUTER JOIN：返回左表和右表中所有行，如果一个表中没有匹配的行，则用NULL填充
  • CROSS JOIN：返回两个表中所有可能的组合，也就是第一个表的每一行和第二个表的每一行进行组合（笛卡尔积）

JOIN算法

Netsted-Loop Join算法（NLJ）

两张表的user_code都是索引

1
mysql> SELECT u.`name`, u.user_code, o.order_name FROM `user` u JOIN `order` o ON u.user_code = o.user_code;
  1. 从order中读入一行记录
  2. 在记录中取出user_code字段到user中查找
  3. user表根据索引找到满足条件的行字段，和上面的记录组成一行
  4. 重复1~3，直到user表遍历结束

从一个表中取出一行，然后在另一个表中扫描所有行，查找与之匹配的行

时间复杂度：O(M * N)

为什么需要小表驱动大表：

假设被驱动表的行数是M。 每次在被驱动表查一行数据， 需要先搜索索引a， 再搜索主键索引。每次搜索一棵树近似复杂度是logM， 所以在被驱动表上查一行的时间复杂度是 2∗logM

假设驱动表的行数是N， 执行过程就要扫描驱动表N行， 然后对于每一行， 到被驱动表上匹配一次。因此整个执行过程， 近似复杂度是N * 2 * logM

N对扫描行数的影响更大， 因此应该让小表来做驱动表

Block Netsted-Loop Join算法（BNL）

两张表的user_code都没有索引

1
EXPLAIN SELECT u.`name`, u.user_code, o.order_name FROM `user` u JOIN `order` o ON u.user_code = o.user_code

explain时Extral列会出现Using join buffer (Block Nested Loop)

  1. 从user表中读入name,user_code字段数据存放到线程内存join_buffer中
  2. 扫描order表，将order表中的每一行取出和join_buffer中的数据做对比，满足join条件的作为结果集的一部分返回

Join Buffer是线程内存，在查询结束后会是否。大小有限制，默认是256K，当不够存放数据时会分段查询（也就是在user表中取出一部分，扫描order表，然后继续从user表中取出一部分，扫描order表……）

时间复杂度：O（M + M * N）

没有索引时优化的NLJ算法：

  • 减少磁盘IO与在内存中操作：传统的 NLJ 算法在每次比较时需要从磁盘读取内部表的一行数据。而 BNL 算法将内部表分成多个块，并且将一个块的数据加载到内存，这样就可以减少频繁的磁盘 I/O 操作，提高查询效率
  • 适应内存限制：当内存有限时，BNL 算法可以根据可用内存大小灵活调整块的大小，以适应内存限制。这使得 BNL 算法更具可扩展性，可以在不同的硬件配置下工作
  • 减少比较次数：BNL 算法通过将内部表分成多个块，每次只加载一个块进行比较，减少了比较的次数
    • 数据分块：BNL 算法将内部表划分为多个块，并逐个加载到内存中进行处理。每次只加载一个块的数据，并与外部表进行比较。这样可以避免一次性加载整个内部表并与外部表的每一行进行比较，从而减少了比较次数
    • 提前结束比较：在 BNL 算法中，如果已经找到了与外部表一行匹配的内部表行，就可以提前结束当前块的比较过程。因为在当前块内，已经找到了匹配的行，后续的比较不再需要执行。这样可以节省计算资源，进一步减少比较次数

Hash Join

MySQL8.0.20开始使用Hash Join替代BNL算法

1
SELECT given_name,country_name FROM persons JOIN countries ON persons.country_id = countries.country_id;

hash join分为两个阶段：

  • build构建阶段：使用Join字段作为哈希表key，在内存中构建Hash表（会选择结果集比较小的去构建（以字节为单位进行比较）
  • probe探测阶段：逐行遍历被驱动表，计算join条件的hash值并在hash表中查找，如果匹配则记录下来，直到被驱动表遍历完成

内存****中hash表的大小是由参数join_buffer_size控制的如果构建的hash表内存大于可用内存怎么办？

服务器会将多余的构建写入磁盘的多个文件中，并且数值文件的数量，确保最大的文件大小和join_buffer_size一致

每行数据写入哪个块文件是通过计算 join 属性的哈希来确定的。但是此时使用的哈希函数与内存中生成阶段使用的哈希函数不同

在探测阶段，服务器对于另一张表每一行数据使用同样的hash算法进行分区。这样就可以确定两个输入之间的匹配行将位于同一对文件中

探测阶段完成后，开始从磁盘读取文件。首先会将build构建阶段的第一个文件加载到内存中哈希表中（解释了为什么希望最大的文件大小与内存一致），接着读取在探测阶段生成的文件，在内存哈希表中进行匹配

因此可以得出对两个操作使用相同的哈希函数，那么在将构建文件加载到哈希表中时，我们会得到一个非常糟糕的哈希表，因为同一个文件中的所有行都将哈希为相同的值

时间复杂度：O（M + N）

为什么替换BNL：

  • 笛卡尔积问题：当两个表进行连接操作时，如果没有合适的连接谓词或者数据分布不均匀，BNL 可能会生成巨大的笛卡尔积结果，导致性能低下。而 Hash Join 则可以通过哈希算法将连接条件相符的行分配到同一个哈希桶中，避免了笛卡尔积问题

优化思路

NLJ算法优化：小表驱动大表，在join的时候如果明确知道哪张表是小表时可以使用straight_join写法固定连接驱动方式

BNL算法优化：

  • 给被驱动表的join字段加上索引，把BNL算法转成NLJ算法
  • 无法设置索引的情况可以通过设置join_buffer_size参数来控制Join Buffer的大小，以减少分段查询次数

Hash Join算法优化：增加 join_buffer_size值避免生成文件

in & exists

in

in执行流程：查询子查询的表且内外表有关联时，先执行内层表的子查询，然后将内表和外表做一个笛卡尔积，然后按照条件进行筛选，得到结果集。所以相对内表比较小的时候，in的速度较快

in列表的处理：

  • 小列表：将列表中的值硬编码为条件，通过or运算符连接起来
  • 大列表：看成是范围区间，比如in（a,b），会看成是[a,a]、[b,b]，方便后续进行范围查询操作

重复值会自动提出

参数即使乱序也会重新排序

MySQL 在执行 IN 运算符时有以下几种实现方式：

  • 线性搜索：当IN列表比较小或没有合适的所有时，MySQL会逐个比较列的值
  • 排序和二分查找：如果 IN 列表是有序的，并且存在合适的索引，MySQL 可以通过排序列表并使用二分查找算法来快速定位匹配的值
  • 哈希表查找：对于大型的 IN 列表，MySQL 可以将列表中的值构建成一个哈希表，并使用哈希函数将列的值映射到哈希表中的桶。然后，MySQL 可以通过查找哈希表来判断值是否存在，从而加快查询速度

系统变量eq_range_index_dive_limit对IN子句的影响

MySQL优化器需要去分析一下如何执行查询，需要判断键值在范围区间的记录共有多少条，然后通过一定方式计算出成本，与全表扫描的成本相对比，选取成本更低的那种方式执行查询

对于包含IN子句条件的查询来说，需要依次分析一下每一个范围区间中的记录数量是多少。MySQL优化器针对IN子句对应的范围区间的多少而指定了不同的策略：

  • 如果IN子句对应的范围区间比较少，那么将率先去访问一下存储引擎，看一下每个范围区间中的记录有多少条（如果范围区间的记录比较少，那么统计结果就是精确的，反之会采用一定的手段计算一个模糊的值），这种在查询真正执行前优化器就率先访问索引来计算需要扫描的索引记录数量的方式称之为index dive
  • 如果IN子句对应的范围区间比较多，这样就不能采用index dive的方式去真正的访问二级索引idx_key1（因为那将耗费大量的时间），而是需要采用之前在背地里产生的一些统计数据去估算匹配的二级索引记录有多少条（很显然根据统计数据去估算记录条数比index dive的方式精确性差了很多）

当范围区间个数小于eq_range_index_dive_limit时，将采用index dive的统计方式，否则将采用index statistic的统计方式

exists

exists执行流程：指定一个子查询，检测行的存在。遍历循环外表，然后看外表中的记录有没有和内表的数据一样的，匹配上就将结果放入结果集中

参考文章

MySQL中GROUP BY的实现与优化

MySQL——JOIN详解与优化

MySQL中包含IN子句的语句是怎样执行的

  • 本文标题：MySQL常用关键字实现原理
  • 本文作者：dd
  • 创建时间：2023-07-10 18:52:55
  • 本文链接：2023/07/10/MySQL常用关键字实现原理/
  • 版权声明：本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
  1. group by
    1. 松散索引
    2. 紧凑索引
    3. 临时表
    4. 优化思路
  2. JOIN
    1. JOIN类型
    2. JOIN算法
      1. Netsted-Loop Join算法（NLJ）
      2. Block Netsted-Loop Join算法（BNL）
      3. Hash Join
    3. 优化思路
  3. in & exists
    1. in
    2. exists
  4. 参考文章