首页 > 数据库 > MySQL

面试无忧：源码+实践，讲到MySQL调优的底层算法实现

来源：SegmentFault

时间：2023-02-20 08:34:42 266浏览收藏

小伙伴们有没有觉得学习数据库很有意思？有意思就对了！今天就给大家带来《面试无忧：源码+实践，讲到MySQL调优的底层算法实现》，以下内容将会涉及到MySQL、Java、数据库、后端、程序员，若是在学习中对其中部分知识点有疑问，或许看了本文就能帮到你！

不知道大家有没有参与过系统重构或者代码调优的工作，有幸，最近我接触了一个公司N久前的一个项目的重构工作，目的就是为了提升一下响应速度，然后我们小组拿到这个项目的源代码之后，大呼：WC，这NM谁写的代码啊，太不讲究了吧，这SQL都写了些什么玩意啊，其实在这些年的工作中，这样的问题已经不是第一次遇见了，老是被提需求说性能有问题，拿到代码之后发现问题很简单，90%都是SQL的问题，当时赶进度，能查询出来结果就可以，稍微一优化SQL性能就能提升很多，虽然现在有很多SQL审核平台，但是，在面试的过程中，需要你回答的更加深入一些，那这里，我就结合代码给你讲解到算法的层次，在遇到优化，不在惧怕任何挑战

公众号：Java架构师联盟，每日更新技术好文

SQL优化基础概念

说到SQL优化，大家首先想到的就是创建索引，但创建索引需要了解相关基础概念。

1. 索引

我们知道，MySQL中的索引通常采用B-Tree结构，那么首先就要清楚B-Tree和B+Tree 结构的区别

在InnoDB中索引是B+Tree结构的，在该结构中叶子节点包含了非叶子节点的所有数据，并且叶子节点之间会通过指针连接。

之所以采用B+Tree结构，是因为数据库中有>、

2. 聚集索引（主键索引）

InnoDB的所有的表都是索引组织表，主键与数据存放在一起。InnoDB选择聚集索引遵循以下原则：

• 在创建表时，如果指定了主键，则将其作为聚集索引。

• 如果没有指定主键，则选择第一个NOT NULL的唯一索引作为聚集索引。

• 如果没有唯一索引，则内部会生成一个6字节的rowid作为主键。

聚集索引是将主键与行记录存储在一起的，当根据主键进行查询时，可直接在表中获取到数据，不用回表查询。

3. 二级索引（也称辅助索引）

二级索引的叶子节点存储了索引值+rowid（主键值）。熟悉MySQL 的读者在MySQL中创建表时最好自己指定一个显式的自增主键，这样做的好处是：显式指定的主键可以是普通的int类型，这样存储的空间就是4字节，在二级索引的叶子节点中存储主键值所占用的空间就会变小。这时可能有人会问：二级索引的叶子节点为何不存储主键的指针呢？原因是：如果主键位置发生了变化，则需要修改二级索引的叶子节点对应存储的指针；但是如果二级索引的叶子节点本身存储的是主键的值，则不会出现这种情况。

4. 基数、选择性、回表

• 基数是字段distinct后的值，主键或非NULL的唯一索引的基数等于表的总行数。

• 选择性是指基数与总行数的比值乘以100%，选择性通常表示在字段上是否适合创建索引。

• 当要查询的字段不能在索引中完全获得时，则需要回表查询取出所需要的数据。这几点很重要，因为SQL优化最重要的就是要减少SQL语句的扫描行数，看下面这个例子。

mysql> create table t1 (id int , cl char(20)，c2 chaz(20),c3 char(20)) ;
Query OK,0 rows affected （0.02 sec)

mysql> insert into t1 values (10,'a','b', 'C');
Query OK,1 row affected (0.01 sec)

mysql> insert into t1 values (10,'a','b', 'c');
Query OK,1 row affected (0.01 sec)

mysql> insert into t1 values (10,'a', 'b' , 'c');
Query OK,1 row affected (0.01 sec)

mysql> insert into t1 values (10，'a','b', 'c');
Query OK, 1 row affected (0.01 sec)

mysql> insert into t1 values (10,'a', 'b', 'c');
Query OK, 1 row affected (0.01 sec)

mysql> insert into t1 values (10,'a', 'b', 'c');
Query OK,1 row affected (0.01 sec)

mysql> create index idx_c1 on t1 (c1);
Query OK,o rows affected (0.02 sec)
Records: 0 Duplicates: 0 warnings: o

创建表，在c1字段插入重复数据，并在c1字段创建索引，我们通过执行计划看一下

cost值的消耗。

mysql> explain format=json select * from t1 where c1 = 'a';
"query_block" :{
"select_id": 1,"cost_info":{
"query_cost": "1.10"
)

删除索引，并通过执行计划查看cost值的消耗。

mysql> drop index idx_c1 on t1;
Query OK,0 rows affected (0.02sec)Records: 0 Duplicates: 0 warnings: o
mysql> explain format=json select * from t1 where c1 = 'a';(
"query_block":{
"select_id":1,"cost_info" :{
"query_cost":"0.85"
)
)

两次查询的cost值不同，通过索引查询的cost值比全表扫描的cost值大。这是因为当通过索引查询时索引数据都是重复的（基数很低），所以要做一个索引全扫描；还因

为“SELECT *”扫描完索引后要回表查询id, c2,c3这几个字段。就好比你要读完一本书，不会先把目录全部读一遍，然后再把后面的内容都读一遍。

如果将c1字段的值改成不重复的，我们再来看一下。

mysql> insert into t1 values (10, 'a', 'b', 'c');
Query OK, 1 row affected (0.01 sec)
mysql> insert into t1 values (10，'b'，'b','c');
Query OK,1 row affected （0.01 sec)
mysql> insert into t1 values (10，'c','b','c');
Query OK, 1 row affected (0.01 sec)
mysql> insert into t1 values (10，'d'，'b', 'c');
Query OK, 1 row affected (0.00 sec)
mysql> insert into t1 values (10,'e', 'b','c');
Query OK,1 row affected (0.01 sec)

mysql> explain format=json select * from t1 where c1 = 'a';
"query_block" :{
"select_id": 1,"cost_info":{
"query_cost": "0.35"
}

mysql> drop index idx_c1 on t1;
Query OK,0 rows affected （0.02 sec)
Records: 0 Duplicates: 0 warnings:0
mysql>explain format=json select * from t1 where c1 = 'a';
"query_block": {
"select_id": 1,"cost_info":(
"query_cost":"0.75"
)

这次c1字段的值不重复（基数较高），则通过索引查询的cost值比全表扫描的cost值小。

这里可能没有体现出选择性，我们说基数高比较好，但是要有一个衡量目标。例如，某一字段的基数是几十万条，但是表中数据有几十亿条，在这个字段上创建索引就不是很合适，因为选择性比较低，通过索引查询在索引中可能就要扫描上亿条数据。

通常在创建索引时要考虑以上内容（回表、基数、选择性），在MySQL中可以通过系统表innodb_index_stats来查看索引选择性如何，并且可以看到组合索引中每一个字段的选择性如何，还可以计算索引的大小

SELECT stat_value AS pages, index_name
, stat_value * @@innodb_page_size / 1024/ 1024 AS size
FROM mysql.innodb_index_stats
WHERE(table_name = 'sbtest1'
AND database_name = 'sbtest'
AND stat_description = 'Number of pages in the index'
AND stat_name = 'size')
GROUP BY index_name;

如果是分区表，则使用下面的语句。

SELECT stat_value AS pages, index_name
，SUM(stat_value)* @@innodb_page_size / 1024 / 1024 AS size
FROM mysql .innodb_index_stats
WHERE(table_name LIKE 't#P%'
AND database_name = 'test'
AND stat_description = 'Number of pages in the index'
AND stat_name = 'size')
GROUP BY index_name;

也可以通过show index from table_name 查看Cardinality字段的值，以及字段的基数是多少。

MySQL中的Join算法

这是一个世纪难题，很多文章或者文档或者公司规范都是说尽量不要使用join方法，但是原因讲解都比较粗一些，今天就来看一下他的算法实现是怎么样的，为什么要尽量减少使用频率

1. Nested-Loop Join Algorithm（嵌套循环Join算法）

最简单的Join算法及外循环读取一行数据，根据关联条件列到内循环中匹配关联，在这种算法中，我们通常称外循环表为驱动表，称内循环表为被驱动表。

Nested-Loop Join算法的伪代码如下:

for each row in t1 matching range {
for each row in t2 matching reference key {
for each row in t3 {
if row satisfies join conditions,send to client)
)

2. Block Nested-Loop Join Algorithm（块嵌套循环Join算法，即BNL算法）

BNL算法是对Nested-Loop Join算法的优化。

具体做法是将外循环的行缓存起来，读取缓冲区中的行，减少内循环表被扫描的次数。例如，外循环表与内循环表均有100行记录，普通的嵌套内循环表需要扫描100次，如果使用块嵌套循环，则每次外循环读取10行记录到缓冲区中，然后把缓冲区数据传递给下一个内循环，将内循环读取到的每行和缓冲区中的10行进行比较，这样内循环表只需要扫描10次即可完成，使用块嵌套循环后内循环整体扫描次数少了一个数量级。使用块嵌套循环，内循环表扫描方式应是全表扫描，因为是内循环表匹配Join Buffer中的数据的。使用块嵌套循环连接，MySQL会使用连接缓冲区（Join Buffer），且会遵循下面一些原则：

• 连接类型为ALL、index、range，会使用到Join Buffer。

• Join Buffer是由join_buffer_size 变量控制的。

• 每次连接都使用一个Join Buffer，多表的连接可以使用多个Join Buffer。

• Join Buffer只存储与查询操作相关的字段数据，而不是整行记录。

BNL算法的伪代码如下：

for each row in t1 matching range {
for each row in t2 matching reference key {
store used columns from t1, t2 in join buffer
if buffer is full {
for each row in t3 {
for each t1,t2 combination in join buffer {
if row satisfies join conditions,send to client
}
}
empty join buffer
}
}
}
if buffer is not empty{for each row in t3{
for each t1, t2 combination in join buffer {
if row satisfies join conditions,send to client
}
}
}