MySQL_执行原理_(索引合并&链接查询&查询成本计算)

5.1. 单表访问之索引合并

我们前边说过 MySQL 在一般情况下执行一个查询时最多只会用到单个二级索引,但存在有特殊情况,在这些特殊情况下也可能在一个查询中使用到多个二级索引,MySQL 中这种使用到多个索引来完成一次查询的执行方法称之为:索引合并/index merge,具体的索引合并算法有下边三种。

5.1.1. Intersection 合并

Intersection 翻译过来的意思是交集。这里是说某个查询可以使用多个二级索引,将从多个二级索引中查询到的结果取交集,比方说下边这个查询:

SELECT * FROM order_exp WHERE order_no = 'a' AND expire_time = 'b';

假设这个查询使用 Intersection 合并的方式执行的话,那这个过程就是这样的:

  • 从 idx_order_no 二级索引对应的 B+树中取出 order_no= 'a’的相关记录。
  • 从 idx_insert_time 二级索引对应的 B+树中取出 insert_time= 'b’的相关记录。

二级索引的记录都是由索引列 + 主键构成的,所以我们可以计算出这两个结果集中 id 值的交集。
按照上一步生成的 id 值列表进行回表操作,也就是从聚簇索引中把指定 id 值的完整用户记录取出来,返回给用户。

为啥不直接使用 idx_order_no 或者 idx_insert_time 只根据某个搜索条件去读取一个二级索引,然后回表后再过滤另外一个搜索条件呢?这里要分析一下两种查询执行方式之间需要的成本代价。

  • 只读取一个二级索引的成本:
    按照某个搜索条件读取一个二级索引,根据从该二级索引得到的主键值进行 回表操作,然后再过滤其他的搜索条件

  • 读取多个二级索引之后取交集成本:
    按照不同的搜索条件分别读取不同的二级索引,将从多个二级索引得到的主 键值取交集,然后进行回表操作。
    虽然读取多个二级索引比读取一个二级索引消耗性能,但是大部分情况下读取二级索引的操作是顺序 I/O,而回表操作是随机 I/O,所以如果只读取一个二级索引时需要回表的记录数特别多,而读取多个二级索引之后取交集的记录数非常少,当节省的因为回表而造成的性能损耗比访问多个二级索引带来的性能损耗更 高时,读取多个二级索引后取交集比只读取一个二级索引的成本更低。
    MySQL 在某些特定的情况下才可能会使用到 Intersection 索引合并,哪些情况呢?

5.1.1.1. 情况一:等值匹配

二级索引列是等值匹配的情况,对于联合索引来说,在联合索引中的每个列 都必须等值匹配,不能出现只匹配部分列的情况。
而下边这两个查询就不能进行 Intersection 索引合并:

SELECT * FROM order_exp WHERE order_no> 'a' AND insert_time = 'a' AND order_status = 'b' AND expire_time = 'c';
SELECT * FROM order_exp WHERE order_no = 'a' AND insert_time = 'a';

第一个查询是因为对 order_no 进行了范围匹配,第二个查询是因为联合索引 u_idx_day_status 中的 order_status 和 expire_time 列并没有出现在搜索条件中, 所以这两个查询不能进行 Intersection 索引合并。

5.1.1.2. 情况二:主键列可以是范围匹配

下边这个查询可能用到主键和 u_idx_day_status 进行 Intersection 索引 合并的操作:

SELECT * FROM order_exp WHERE id > 100 AND insert_time = 'a';

对于 InnoDB 的二级索引来说,记录先是按照索引列进行排序,如果该二级索引是一个联合索引,那么会按照联合索引中的各个列依次排序。而二级索引的用户记录是由索引列 + 主键构成的,二级索引列的值相同的记录可能会有好多条,这些索引列的值相同的记录又是按照主键的值进行排序的。
所以重点来了,之所以在二级索引列都是等值匹配的情况下才可能使用 Intersection 索引合并,是因为只有在这种情况下根据二级索引查询出的结果集是按照主键值排序的。
Intersection 索引合并会把从多个二级索引中查询出的主键值求交集,如果从各个二级索引中查询的到的结果集本身就是已经按照主键排好序的,那么求交集的过程就很容易。
假设某个查询使用 Intersection 索引合并的方式从 idx_order_no 和 idx_expire_time 这两个二级索引中获取到的主键值分别是:
从 idx_order_no 中获取到已经排好序的主键值:1、3、5
从 idx_expire_time 中获取到已经排好序的主键值:2、3、4
那么求交集的过程就是这样:逐个取出这两个结果集中最小的主键值,如果两个值相等,则加入最后的交集结果中,否则丢弃当前较小的主键值,再取该丢弃的主键值所在结果集的后一个主键值来比较,直到某个结果集中的主键值用完了,时间复杂度是 O(n)。
但是如果从各个二级索引中查询出的结果集并不是按照主键排序的话,那就要先把结果集中的主键值排序完再来做上边的那个过程,就比较耗时了。
按照有序的主键值去回表取记录有个专有名词,叫:Rowid Ordered Retrieval, 简称 ROR。
另外,不仅是多个二级索引之间可以采用 Intersection 索引合并,索引合并也可以有聚簇索引参加,也就是我们上边写的情况二:在搜索条件中有主键的范围匹配的情况下也可以使用 Intersection 索引合并。为啥主键这就可以范围匹配了?还是得回到应用场景里:

SELECT * FROM order_exp WHERE id > 100 AND insert_time = 'a';

假设这个查询可以采用 Intersection 索引合并,我们理所当然的以为这个查询会分别按照 id > 100 这个条件从聚簇索引中获取一些记录,在通过 insert_time= 'a’这个条件从 idx_order_no 二级索引中获取一些记录,然后再求交集,其实这样就把问题复杂化了,没必要从聚簇索引中获取一次记录。别忘了二级索引的记录中都带有主键值的,所以可以在从 idx_order_no 中获取到的主键值上直接运用条 件id > 100 过滤就行了,这样多简单。所以涉及主键的搜索条件只不过是为了从别的二级索引得到的结果集中过滤记录罢了,是不是等值匹配不重要。
当然,上边说的情况一和情况二只是发生 Intersection 索引合并的必要条件,不是充分条件。也就是说即使情况一、情况二成立,也不一定发生 Intersection 索引合并,这得看优化器的心情。优化器只有在单独根据搜索条件从某个二级索引中获取的记录数太多,导致回表开销太大,而通过 Intersection 索引合并后需要回表的记录数大大减少时才会使用 Intersection 索引合并。

5.1.2. Union 合并

我们在写查询语句时经常想把既符合某个搜索条件的记录取出来,也把符合另外的某个搜索条件的记录取出来,我们说这些不同的搜索条件之间是 OR 关系。 有时候 OR 关系的不同搜索条件会使用到不同的索引,比方说这样:
SELECT * FROM order_exp WHERE order_no = ‘a’ OR expire_time = ‘b’
Intersection 是交集的意思,这适用于使用不同索引的搜索条件之间使用 AND 连接起来的情况;Union 是并集的意思,适用于使用不同索引的搜索条件之间使用 OR 连接起来的情况。与 Intersection 索引合并类似,MySQL 在某些特定的情况下才可能会使用到 Union 索引合并:

5.1.2.1. 情况一:等值匹配

分析同 Intersection 合并

5.1.2.2. 情况二:主键列可以是范围匹配

分析同 Intersection 合并

5.1.2.3. 情况三:使用 Intersection 索引合并的搜索条件

就是搜索条件的某些部分使用 Intersection 索引合并的方式得到的主键集合和其他方式得到的主键集合取交集,比方说这个查询:

SELECT * FROM order_exp WHERE insert_time = 'a' AND order_status = 'b' AND expire_time = 'c' OR (order_no = 'a' AND expire_time = 'b');

优化器可能采用这样的方式来执行这个查询:
先按照搜索条件 order_no = ‘a’ AND expire_time = 'b’从索引 idx_order_no 和 idx_expire_time 中使用 Intersection 索引合并的方式得到一个主键集合。
再按照搜索条件 insert_time=‘a’ AND order_status = ‘b’ AND expire_time=‘c’ 从联合索引 u_idx_day_status 中得到另一个主键集合。
采用 Union 索引合并的方式把上述两个主键集合取并集,然后进行回表操作, 将结果返回给用户。
当然,查询条件符合了这些情况也不一定就会采用 Union 索引合并,也得看优化器的心情。优化器只有在单独根据搜索条件从某个二级索引中获取的记录数比较少,通过 Union 索引合并后进行访问的代价比全表扫描更小时才会使用 Union 索引合并。

5.1.3. Sort-Union 合并

Union 索引合并的使用条件太苛刻,必须保证各个二级索引列在进行等值匹配的条件下才可能被用到,比方说下边这个查询就无法使用到 Union 索引合并:

SELECT * FROM order_exp WHERE order_no< 'a' OR expire_time> 'z'

这是因为根据 order_no< 'a’从 idx_order_no 索引中获取的二级索引记录的主键值不是排好序的,根据 expire_time> 'z’从 idx_expire_time 索引中获取的二级索引记录的主键值也不是排好序的,但是 order_no< 'a’和 expire_time> ‘z’'这两个条件又特别让我们动心,所以我们可以这样:
先根据 order_no< 'a’条件从 idx_order_no 二级索引中获取记录,并按照记录的主键值进行排序。
再根据 expire_time> 'z’条件从 idx_expire_time 二级索引中获取记录,并按照记录的主键值进行排序。
因为上述的两个二级索引主键值都是排好序的,剩下的操作和 Union 索引合并方式就一样了。
上述这种先按照二级索引记录的主键值进行排序,之后按照 Union 索引合并方式执行的方式称之为 Sort-Union 索引合并,很显然,这种 Sort-Union 索引合并比单纯的 Union 索引合并多了一步对二级索引记录的主键值排序的过程。

5.1.4. 联合索引替代 Intersection 索引合并

SELECT * FROM order_exp WHERE order_no= 'a' And expire_time= 'z';

这个查询之所以可能使用 Intersection 索引合并的方式执行,还不是因为 idx_order_no 和 idx_expire_time 是两个单独的 B+树索引,要是把这两个列搞一个联合索引,那直接使用这个联合索引就把事情搞定了,何必用啥索引合并呢,就像这样:

ALTER TABLE order_exp drop index idx_order_no, idx_expire_time,
add index idx_order_no_expire_time(order_no, expire_time);

这样我们把 idx_order_no, idx_expire_time 都干掉,再添加一个联合索引 idx_order_no_expire_time,使用这个联合索引进行查询简直是又快又好,既不用多读一棵 B+树,也不用合并结果。

5.2. 连接查询

搞数据库一个避不开的概念就是 Join,翻译成中文就是连接。使用的时候常常陷入下边两种误区:
误区一:业务至上,管他三七二十一,再复杂的查询也用在一个连接语句中搞定。
误区二:敬而远之,上次慢查询就是因为使用了连接导致的,以后再也不敢用了。
所以我们来学习一下连接的原理,才能在工作中用好 SQL 连接。

5.2.1. 连接简介

5.2.1.1. 连接的本质

为了方便讲述,我们建立两个简单的演示表并给它们写入数据:

CREATE TABLE e1 (m1 int, n1 char(1));
CREATE TABLE e2 (m2 int, n2 char(1));
INSERT INTO e1 VALUES(1, 'a'), (2, 'b'), (3, 'c');
INSERT INTO e2 VALUES(2, 'b'), (3, 'c'), (4, 'd');

连接的本质就是把各个连接表中的记录都取出来依次匹配的组合加入结果集并返回给用户。
所以我们把 e1 和 e2 两个表连接起来的过程如下图所示:
MySQL_执行原理_(索引合并&链接查询&查询成本计算)
这个过程看起来就是把 e1 表的记录和 e2 的记录连起来组成新的更大的记录, 所以这个查询过程称之为连接查询。连接查询的结果集中包含一个表中的每一条记录与另一个表中的每一条记录相互匹配的组合,像这样的结果集就可以称之为笛卡尔积。因为表 e1 中有 3 条记录,表 e2 中也有 3 条记录,所以这两个表连接之后的笛卡尔积就有 3×3=9 行记录。
在 MySQL 中,连接查询的语法很随意,只要在 FROM 语句后边跟多个表名 就好了,比如我们把 e1 表和 e2 表连接起来的查询语句可以写成这样:

mysql> select * from e1,e2;
+------+------+------+------+
| m1   | n1   | m2   | n2   |
+------+------+------+------+
|    3 | c    |    2 | b    |
|    2 | b    |    2 | b    |
|    1 | a    |    2 | b    |
|    3 | c    |    3 | c    |
|    2 | b    |    3 | c    |
|    1 | a    |    3 | c    |
|    3 | c    |    4 | d    |
|    2 | b    |    4 | d    |
|    1 | a    |    4 | d    |
+------+------+------+------+
9 rows in set (0.00 sec)

5.2.1.2. 连接过程简介
我们可以连接任意数量张表,但是如果没有任何限制条件的话,这些表连接起来产生的笛卡尔积可能是非常巨大的。比方说 3 个 100 行记录的表连接起来产生的笛卡尔积就有 100×100×100=1000000 行数据!所以在连接的时候过滤掉特定记录组合是有必要的,在连接查询中的过滤条件可以分成两种,比方说下边这个查询语句:

mysql> SELECT * FROM e1, e2 WHERE e1.m1 > 1 AND e1.m1 = e2.m2 AND e2.n2 < 'd'; 
+------+------+------+------+
| m1   | n1   | m2   | n2   |
+------+------+------+------+
|    2 | b    |    2 | b    |
|    3 | c    |    3 | c    |
+------+------+------+------+
2 rows in set (0.00 sec)
  • 涉及单表的条件
    比如 e1.m1 > 1 是只针对 e1 表的过滤条件,e2.n2 < 'd’是只针对 e2 表的过滤条件。
  • 涉及两表的条件
    比如类似 e1.m1 = e2.m2、e1.n1 > e2.n2 等,这些条件中涉及到了两个表。
    看一下携带过滤条件的连接查询的大致执行过程在这个查询中我们指明了
    这三个过滤条件:
    e1.m1 > 1
    e1.m1 = e2.m2
    e2.n2 < ‘d’
    那么这个连接查询的大致执行过程如下:
  1. 步骤一:首先确定第一个需要查询的表,这个表称之为驱动表。单表中执行查询语句只需要选取代价最小的那种访问方法去执行单表查询语句就好了(就是 说从 const、ref、ref_or_null、range、index、all 等等这些执行方法中选取代价最小的去执行查询)。
    此处假设使用 e1 作为驱动表,那么就需要到 e1 表中找满足 e1.m1 > 1 的记录,因为表中的数据太少,我们也没在表上建立二级索引,所以此处查询 e1 表 的访问方法就设定为 all,也就是采用全表扫描的方式执行单表查询。
    很明显,e1 表中符合 e1.m1 > 1 的记录有两条。
  2. 步骤二:针对上一步骤中从驱动表产生的结果集中的每一条记录,分别需要到 e2 表中查找匹配的记录,所谓匹配的记录,指的是符合过滤条件的记录。因为是根据 e1 表中的记录去找 e2 表中的记录,所以 e2 表也可以被称之为被驱动表。上一步骤从驱动表中得到了 2 条记录,所以需要查询 2 次 e2 表。此时涉及两个表的列的过滤条件 e1.m1 = e2.m2 就派上用场了:
    当 e1.m1 = 2 时,过滤条件 e1.m1 = e2.m2 就相当于 e2.m2 = 2,所以此时 e2 表相当于有了 e2.m2 = 2、e2.n2 < 'd’这两个过滤条件,然后到 e2 表中执行单表查询。
    当 e1.m1 = 3 时,过滤条件 e1.m1 = e2.m2 就相当于 e2.m2 = 3,所以此时 e2 表相当于有了 e2.m2 = 3、e2.n2 < 'd’这两个过滤条件,然后到 e2 表中执行单表查询。
    所以整个连接查询的执行过程就如下图所示:
    MySQL_执行原理_(索引合并&链接查询&查询成本计算)
    也就是说整个连接查询最后的结果只有两条符合过滤条件的记录;
    从上边两个步骤可以看出来,这个两表连接查询共需要查询 1 次 e1 表,2 次 e2 表。当然这是在特定的过滤条件下的结果,如果我们把 e1.m1 > 1 这个条件 去掉,那么从 e1 表中查出的记录就有 3 条,就需要查询 3 次 e2 表了。也就是说在两表连接查询中,驱动表只需要访问一次,被驱动表可能被访问多次。

5.2.1.3. 内连接和外连接

为了大家更好理解后边内容,我们创建两个有现实意义的表,并插入一些数据:

CREATE TABLE `score` (
  `number` int NOT NULL COMMENT '学号',
  `subject` varchar(30) CHARACTER SET utf8 COLLATE utf8_general_ci NOT NULL COMMENT '科目',
  `score` tinyint DEFAULT NULL COMMENT '成绩',
  PRIMARY KEY (`number`,`subject`) USING BTREE
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb3 ROW_FORMAT=DYNAMIC COMMENT='学生成绩表';

INSERT INTO `score` VALUES ('20200901', '数据结构和算法', '88'), ('20200901', '网络通信原理', '90'), ('20200902', '数据结构和算法', '95'), ('20200902', '网络通信原理', '89'), ('20200903', '离散数学', '70');

CREATE TABLE `student` (
  `number` int NOT NULL AUTO_INCREMENT COMMENT '学号',
  `name` varchar(5) CHARACTER SET utf8 COLLATE utf8_general_ci DEFAULT NULL COMMENT '姓名',
  `major` varchar(30) CHARACTER SET utf8 COLLATE utf8_general_ci DEFAULT NULL COMMENT '专业',
  PRIMARY KEY (`number`) USING BTREE
) ENGINE=InnoDB AUTO_INCREMENT=20200905 DEFAULT CHARSET=utf8mb3 ROW_FORMAT=DYNAMIC COMMENT='学生信息表';

INSERT INTO `student` VALUES ('20200901', 'Jack', '网络工程'), ('20200902', 'Mark', '计算机科学'), ('20200903', 'James', '计算机科学'), ('20200904', 'King', '软件工程');
mysql> select * from student;
+----------+-------+-----------------+
| number   | name  | major           |
+----------+-------+-----------------+
| 20200901 | Jack  | 网络工程        |
| 20200902 | Mark  | 计算机科学      |
| 20200903 | James | 计算机科学      |
| 20200904 | King  | 软件工程        |
+----------+-------+-----------------+
4 rows in set (0.00 sec)
mysql> select * from score;
+----------+-----------------------+-------+
| number   | subject               | score |
+----------+-----------------------+-------+
| 20200901 | 数据结构和算法        |    88 |
| 20200901 | 网络通信原理          |    90 |
| 20200902 | 数据结构和算法        |    95 |
| 20200902 | 网络通信原理          |    89 |
| 20200903 | 离散数学              |    70 |
+----------+-----------------------+-------+
5 rows in set (0.00 sec)

现在我们想把每个学生的考试成绩都查询出来就需要进行两表连接了(因为 score 中没有姓名信息,所以不能单纯只查询 score 表)。连接过程就是从 student 表中取出记录,在 score 表中查找 number 相同的成绩记录,所以过滤条件就是 student.number = socre.number,整个查询语句就是这样:

mysql> SELECT s1.number, s1.name, s2.subject, s2.score FROM student AS s1, score AS s2 WHERE s1.number = s2.number;
+----------+-------+-----------------------+-------+
| number   | name  | subject               | score |
+----------+-------+-----------------------+-------+
| 20200901 | Jack  | 数据结构和算法        |    88 |
| 20200901 | Jack  | 网络通信原理          |    90 |
| 20200902 | Mark  | 数据结构和算法        |    95 |
| 20200902 | Mark  | 网络通信原理          |    89 |
| 20200903 | James | 离散数学              |    70 |
+----------+-------+-----------------------+-------+
5 rows in set (0.00 sec)

从上述查询结果中我们可以看到,各个同学对应的各科成绩就都被查出来了,可是有个问题,King 同学,也就是学号为 20200904 的同学因为某些原因没有参加考试,所以在 score 表中没有对应的成绩记录。
如果老师想查看所有同学的考试成绩,即使是缺考的同学也应该展示出来, 但是到目前为止我们介绍的连接查询是无法完成这样的需求的。我们稍微思考一下这个需求,其本质是想:驱动表中的记录即使在被驱动表中没有匹配的记录,也仍然需要加入到结果集。为了解决这个问题,就有了内连接和外连接的概念:
对于内连接的两个表,驱动表中的记录在被驱动表中找不到匹配的记录,该记录不会加入到最后的结果集,我们上边提到的连接都是所谓的内连接。
对于外连接的两个表,驱动表中的记录即使在被驱动表中没有匹配的记录,也仍然需要加入到结果集。
在 MySQL 中,根据选取驱动表的不同,外连接仍然可以细分为 2 种:

  • 左外连接,选取左侧的表为驱动表。
  • 右外连接,选取右侧的表为驱动表。

可是这样仍然存在问题,即使对于外连接来说,有时候我们也并不想把驱动表的全部记录都加入到最后的结果集。
这就犯难了,怎么办?把过滤条件分为两种就可以就解决这个问题了,所以放在不同地方的过滤条件是有不同语义的:

  1. WHERE 子句中的过滤条件
    WHERE 子句中的过滤条件就是我们平时见的那种,不论是内连接还是外连接,凡是不符合 WHERE 子句中的过滤条件的记录都不会被加入最后的结果集。
  2. ON 子句中的过滤条件
    对于外连接的驱动表的记录来说,如果无法在被驱动表中找到匹配 ON 子句中的过滤条件的记录,那么该记录仍然会被加入到结果集中,对应的被驱动表记录的各个字段使用 NULL 值填充。
    需要注意的是,这个 ON 子句是专门为外连接驱动表中的记录在被驱动表找不到匹配记录时应不应该把该记录加入结果集这个场景下出的,所以如果把ON 子句放到内连接中,MySQL 会把它和 WHERE 子句一样对待,也就是说:内连接中的 WHERE 子句和 ON 子句是等价的。
    一般情况下,我们都把只涉及单表的过滤条件放到 WHERE 子句中,把涉及两表的过滤条件都放到 ON 子句中,我们也一般把放到 ON 子句中的过滤条件也称之为连接条件。
左(外)连接的语法

左(外)连接的语法还是挺简单的,比如我们要把 e1 表和 e2 表进行左外连接查询可以这么写:
SELECT * FROM e1 LEFT [OUTER] JOIN e2 ON 连接条件 [WHERE 普通过滤条件];
其中中括号里的 OUTER 单词是可以省略的。对于 LEFT JOIN 类型的连接来说,我们把放在左边的表称之为外表或者驱动表,右边的表称之为内表或者被驱动表。 所以上述例子中 e1 就是外表或者驱动表,e2 就是内表或者被驱动表。需要注意的是,对于左(外)连接和右(外)连接来说,必须使用 ON 子句来指出连接条件。了解了左(外)连接的基本语法之后,再次回到我们上边那个现实问题中来, 看看怎样写查询语句才能把所有的客户的成绩信息都查询出来,即使是缺考的考生也应该被放到结果集中:

mysql> SELECT s1.number, s1.name, s2.subject, s2.score FROM student AS s1 LEFT JOIN score AS s2 ON s1.number = s2.number;
+----------+-------+-----------------------+-------+
| number   | name  | subject               | score |
+----------+-------+-----------------------+-------+
| 20200901 | Jack  | 数据结构和算法        |    88 |
| 20200901 | Jack  | 网络通信原理          |    90 |
| 20200902 | Mark  | 数据结构和算法        |    95 |
| 20200902 | Mark  | 网络通信原理          |    89 |
| 20200903 | James | 离散数学              |    70 |
| 20200904 | King  | NULL                  |  NULL |
+----------+-------+-----------------------+-------+
6 rows in set (0.01 sec)

从结果集中可以看出来,虽然 King 并没有对应的成绩记录,但是由于采用的是连接类型为左(外)连接,所以仍然把她放到了结果集中,只不过在对应的成绩记录的各列使用 NULL 值填充而已。

右(外)连接的语法

右(外)连接和左(外)连接的原理是一样的,语法也只是把 LEFT 换成 RIGHT 而已:
SELECT*FROMe1RIGHT[OUTER]JOINe2ON 连接条件 [WHERE 普通过滤条件];
只不过驱动表是右边的表 e2,被驱动表是左边的表 e1。

内连接的语法

内连接和外连接的根本区别就是在驱动表中的记录不符合 ON 子句中的连接条件时不会把该记录加入到最后的结果集,一种最简单的内连接语法,就是直接把需要连接的多个表都放到 FROM 子句后边。其实针对内连接,MySQL 供了 好多不同的语法:
SELECT * FROM e1 [INNER | CROSS] JOIN e2 [ON 连接条件] [WHERE 普通过滤条件];
也就是说在 MySQL 中,下边这几种内连接的写法都是等价的:

SELECT * FROM e1, e2;
SELECT * FROM e1 JOIN e2;
SELECT * FROM e1 INNER JOIN e2;
SELECT * FROM e1 CROSS JOIN e2;

再说一次,由于在内连接中 ON 子句和 WHERE 子句是等价的,所以内连接中不要求强制写明 ON 子句。
我们前边说过,连接的本质就是把各个连接表中的记录都取出来依次匹配的组合加入结果集并返回给用户。不论哪个表作为驱动表,两表连接产生的笛卡尔积肯定是一样的。而对于内连接来说,由于凡是不符合 ON 子句或 WHERE 子句中的条件的记录都会被过滤掉,其实也就相当于从两表连接的笛卡尔积中把不符合过滤条件的记录给踢出去,所以对于内连接来说,驱动表和被驱动表是可以互换的,并不会影响最后的查询结果。
但是对于外连接来说,由于驱动表中的记录即使在被驱动表中找不到符合ON 子句条件的记录时也要将其加入到结果集,所以此时驱动表和被驱动表的关系就很重要了,也就是说左外连接和右外连接的驱动表和被驱动表不能轻易互换。

5.2.2. MySQL 对连接的执行

复习了连接、内连接、外连接这些基本概念后,我们需要理解 MySQL 怎么样来进行表与表之间的连接,才能明白有的连接查询运行的快,有的却慢。

5.2.2.1. 嵌套循环连接(Nested-Loop Join)

我们前边说过,对于两表连接来说,驱动表只会被访问一遍,但被驱动表却要被访问到好多遍,具体访问几遍取决于对驱动表执行单表查询后的结果集中的记录条数。
对于内连接来说,选取哪个表为驱动表都没关系,而外连接的驱动表是固定的,也就是说左(外)连接的驱动表就是左边的那个表,右(外)连接的驱动表就是右边的那个表。
如果有 3 个表进行连接的话,那么首先两表连接得到的结果集就像是新的驱动表,然后第三个表就成为了被驱动表,可以用伪代码表示一下这个过程就是这样:

for each row in e1 { #此处表示遍历满足对 e1 单表查询结果集中的每一条记录,N 条
	for each row in e2 { #此处表示对于某条 e1 表的记录来说,遍历满足对 e2 单表查询结果集中的每一条记录,M 条
		for each row in t3 { #此处表示对于某条 e1 和 e2 表的记录组合来说,对 t3 表进行单表查询,L 条
			if row satisfies join conditions, send to client 
		}
	} 
}

这个过程就像是一个嵌套的循环,所以这种驱动表只访问一次,但被驱动表却可能被多次访问,访问次数取决于对驱动表执行单表查询后的结果集中的记录条数的连接执行方式称之为嵌套循环连接(Nested-Loop Join),这是最简单, 也是最笨拙的一种连接查询算法,时间复杂度是 O(NML)。

5.2.2.2. 使用索引加快连接速度

我们知道在嵌套循环连接的步骤 2 中可能需要访问多次被驱动表,如果访问被驱动表的方式都是全表扫描的话,那酸爽不敢想象!
但是查询 e2 表其实就相当于一次单表查询,我们可以利用索引来加快查询速度。回顾一下最开始介绍的 e1 表和 e2 表进行内连接的例子:

SELECT * FROM e1, e2 WHERE e1.m1 > 1 AND e1.m1 = e2.m2 AND e2.n2 < 'd';

我们使用的其实是嵌套循环连接算法执行的连接查询,再把上边那个查询执行过程表回顾一下:
查询驱动表 e1 后的结果集中有两条记录,嵌套循环连接算法需要对被驱动表查询 2 次:

当 e1.m1 = 2 时,去查询一遍 e2 表,对 e2 表的查询语句相当于:

SELECT * FROM e2 WHERE e2.m2 = 2 AND e2.n2 < 'd';

当 e1.m1 = 3 时,再去查询一遍 e2 表,此时对 e2 表的查询语句相当于:

SELECT * FROM e2 WHERE e2.m2 = 3 AND e2.n2 < 'd';

可以看到,原来的 e1.m1 = e2.m2 这个涉及两个表的过滤条件在针对 e2 表做查询时关于 e1 表的条件就已经确定了,所以我们只需要单单优化对 e2 表的查询了,上述两个对 e2 表的查询语句中利用到的列是 m2 和 n2 列,我们可以:
在 m2 列上建立索引,因为对 m2 列的条件是等值查找,比如 e2.m2 = 2、e2.m2 = 3 等,所以可能使用到 ref 的访问方法,假设使用 ref 的访问方法去执行对 e2 表的查询的话,需要回表之后再判断 e2.n2 < d 这个条件是否成立。

这里有一个比较特殊的情况,就是假设 m2 列是 e2 表的主键或者唯一二级索引列,那么使用 e2.m2 = [常数值] 这样的条件从 e2 表中查找记录的过程的代价就是常数级别的。我们知道在单表中使用主键值或者唯一二级索引列的值进行等值查找的方式称之为 const,而 MySQL 把在连接查询中对被驱动表使用主键值或者唯一二级索引列的值进行等值查找的查询执行方式称之为:eq_ref。 在 n2 列上建立索引,涉及到的条件是 e2.n2 < ‘d’,可能用到 range 的访问方法,假设使用 range 的访问方法对 e2 表的查询的话,需要回表之后再判断在 m2 列上的条件是否成立。

假设 m2 和 n2 列上都存在索引的话,那么就需要从这两个里边儿挑一个代价更低的去执行对 e2 表的查询。当然,建立了索引不一定使用索引,只有在二级索引 + 回表的代价比全表扫描的代价更低时才会使用索引。

另外,有时候连接查询的查询列表和过滤条件中可能只涉及被驱动表的部分列,而这些列都是某个索引的一部分,这种情况下即使不能使用 eq_ref、ref、 ref_or_null 或者 range 这些访问方法执行对被驱动表的查询的话,也可以使用索引扫描 ,也就是 index(索引覆盖)的访问方法来查询被驱动表。

5.2.2.3. 基于块的嵌套循环连接(Block Nested-Loop Join)

扫描一个表的过程其实是先把这个表从磁盘上加载到内存中,然后从内存中比较匹配条件是否满足。
现实生活中的表成千上万条记录都是少的,几百万、几千万甚至几亿条记录的表到处都是。内存里可能并不能完全存放的下表中所有的记录,所以在扫描表前边记录的时候后边的记录可能还在磁盘上,等扫描到后边记录的时候可能内存不足,所以需要把前边的记录从内存中释放掉。

而采用嵌套循环连接算法的两表连接过程中,被驱动表可是要被访问好多次的,如果这个被驱动表中的数据特别多而且不能使用索引进行访问,那就相当于要从磁盘上读好几次这个表,这个 I/O 代价就非常大了,所以我们得想办法:尽量减少访问被驱动表的次数

当被驱动表中的数据非常多时,每次访问被驱动表,被驱动表的记录会被加载到内存中,在内存中的每一条记录只会和驱动表结果集的一条记录做匹配,之后就会被从内存中清除掉。然后再从驱动表结果集中拿出另一条记录,再一次把 被驱动表的记录加载到内存中一遍,周而复始,驱动表结果集中有多少条记录,就得把被驱动表从磁盘上加载到内存中多少次。

所以我们可不可以在把被驱动表的记录加载到内存的时候,一次性和多条驱动表中的记录做匹配,这样就可以大大减少重复从磁盘上加载被驱动表的代价了。 所以 MySQL 出了一个 join buffer 的概念,join buffer 就是执行连接查询前申请的一块固定大小的内存,先把若干条驱动表结果集中的记录装在这个 join buffer 中,然后开始扫描被驱动表,每一条被驱动表的记录一次性和 join buffer 中的多条驱动表记录做匹配,因为匹配的过程都是在内存中完成的,所以这样可以显著减少被驱动表的 I/O 代价。使用 join buffer 的过程如下图所示:
MySQL_执行原理_(索引合并&链接查询&查询成本计算)
最好的情况是 join buffer 足够大,能容纳驱动表结果集中的所有记录。 这种加入了 join buffer 的嵌套循环连接算法称之为基于块的嵌套连接(Block Nested-Loop Join)算法。
这个 join buffer 的大小是可以通过启动参数或者系统变量join_buffer_size 进行配置,默认大小为 262144 字节(也就是 256KB),最小可以设置为 128 字节;

mysql> show variables like 'join_buffer_size' ;
+------------------+--------+
| Variable_name    | Value  |
+------------------+--------+
| join_buffer_size | 262144 |
+------------------+--------+
1 row in set (0.01 sec)

当然,对于优化被驱动表的查询来说,最好是为被驱动表加上效率高的索引, 如果实在不能使用索引,并且自己的机器的内存也比较大可以尝试调大 join_buffer_size 的值来对连接查询进行优化。
另外需要注意的是,驱动表的记录并不是所有列都会被放到 join buffer 中,只有查询列表中的列和过滤条件中的列才会被放到 join buffer 中,所以再次醒 我们,最好不要把*作为查询列表,只需要把我们关心的列放到查询列表就好了, 这样还可以在 join buffer 中放置更多的记录。

5.3. MySQL的查询成本

5.3.1. 什么是成本

MySQL 执行一个查询可以有不同的执行方案,它会选择其中成本最低,或者说代价最低的那种方案去真正的执行查询。不过我们之前对成本的 述是非常模糊的,其实在 MySQL 中一条查询语句的执行成本是由下边这两个方面组成的:

  • I/O 成本
    我们的表经常使用的 MyISAM、InnoDB 存储引擎都是将数据和索引都存储到磁盘上的,当我们想查询表中的记录时,需要先把数据或者索引加载到内存中然 后再操作。这个从磁盘到内存这个加载的过程损耗的时间称之为 I/O 成本。
  • CPU 成本
    读取以及检测记录是否满足对应的搜索条件、对结果集进行排序等这些操作损耗的时间称之为 CPU 成本。
    对于 InnoDB 存储引擎来说,页是磁盘和内存之间交互的基本单位,MySQL 规定读取一个页面花费的成本默认是 1.0,读取以及检测一条记录是否符合搜索条件的成本默认是 0.2。1.0、0.2 这些数字称之为成本常数,这两个成本常数我们最常用到,当然还有其他的成本常数。
    注意,不管读取记录时需不需要检测是否满足搜索条件,其成本都算是0.2。

5.3.2. 单表查询的成本

5.3.2.1. 基于成本的优化步骤实战

在一条单表查询语句真正执行之前,MySQL 的查询优化器会找出执行该语句所有可能使用的方案,对比之后找出成本最低的方案,这个成本最低的方案就是所谓的执行计划,之后才会调用存储引擎提供的接口真正的执行查询,这个过程总结一下就是这样:

  1. 根据搜索条件,找出所有可能使用的索引
  2. 计算全表扫描的代价
  3. 计算使用不同索引执行查询的代价
  4. 对比各种执行方案的代价,找出成本最低的那一个下边我们就以一个实例来分析一下这些步骤,单表查询语句如下:
SELECT
	*
FROM
	order_exp
WHERE
	order_no IN ('DD00_6S', 'DD00_9S', 'DD00_10S')
AND expire_time > '2021-03-22 18:28:28'
AND expire_time <= '2021-03-22 18:35:09'
AND insert_time > expire_time
AND order_note LIKE '%7 排 1%'
AND order_status = 0

乍看上去有点儿复杂,我们一步一步分析一下。

  1. 根据搜索条件,找出所有可能使用的索引
    我们前边说过,对于 B+树索引来说,只要索引列和常数使用=、<=>、IN、NOT IN、IS NULL、IS NOT NULL、>、<、>=、<=、BETWEEN、!=(不等于也可以写 成<>)或者 LIKE 操作符连接起来,就可以产生一个所谓的范围区间(LIKE 匹配字符串前缀也行),MySQL 把一个查询中可能使用到的索引称之为 possible keys。

我们分析一下上边查询中涉及到的几个搜索条件:
order_no IN (‘DD00_6S’,‘DD00_9S’,‘DD00_10S’) ,这个搜索条件可以使用二级索引 idx_order_no。
expire_time> ‘2021-03-22 18:28:28’ AND expire_time<= ‘2021-03-22 18:35:09’, 这个搜索条件可以使用二级索引 idx_expire_time。
insert_time> expire_time,这个搜索条件的索引列由于没有和常数比较,所以并不能使用到索引。
order_note LIKE ‘%hello%’,order_note 即使有索引,但是通过 LIKE 操作符和以通配符开头的字符串做比较,不可以适用索引。 order_status = 0,由于该列上只有联合索引,而且不符合最左前缀原则,所以不会用到索引。
综上所述,上边的查询语句可能用到的索引,也就是 possible keys 只有 idx_order_no,idx_expire_time。

mysql> EXPLAIN SELECT
    -> *
    -> FROM
    -> order_exp
    -> WHERE
    -> order_no IN ('DD00_6S', 'DD00_9S', 'DD00_10S')
    -> AND expire_time > '2021-03-22 18:28:28'
    -> AND expire_time <= '2021-03-22 18:35:09'
    -> AND insert_time > expire_time
    -> AND order_note LIKE '%7 排 1%'
    -> AND order_status = 0 \G;
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: order_exp
   partitions: NULL
         type: range
possible_keys: idx_order_no,idx_expire_time
          key: idx_expire_time
      key_len: 5
          ref: NULL
         rows: 39
     filtered: 0.13
        Extra: Using index condition; Using where
1 row in set, 1 warning (0.00 sec)
  1. 计算全表扫描的代价
    对于 InnoDB 存储引擎来说,全表扫描的意思就是把聚簇索引中的记录都依次和给定的搜索条件做一下比较,把符合搜索条件的记录加入到结果集,所以需要将聚簇索引对应的页面加载到内存中,然后再检测记录是否符合搜索条件。由于查询成本=I/O 成本+CPU 成本,所以计算全表扫描的代价需要两个信息:
  • 聚簇索引占用的页面数
  • 该表中的记录数

这两个信息从哪来呢?MySQL 为每个表维护了一系列的统计信息,关于这些统计信息是如何收集起来的我们放在后边再说,现在看看怎么查看这些统计信息。
MySQL 给我们供了 SHOW TABLE STATUS 语句来查看表的统计信息,如果要看指定的某个表的统计信息,在该语句后加对应的 LIKE 语句就好了,比方说 我们要查看 order_exp 这个表的统计信息可以这么写:

mysql> SHOW TABLE STATUS LIKE 'order_exp'\G
*************************** 1. row ***************************
           Name: order_exp
         Engine: InnoDB
        Version: 10
     Row_format: Dynamic
           Rows: 10367
 Avg_row_length: 153
    Data_length: 1589248
Max_data_length: 0
   Index_length: 1212416
      Data_free: 4194304
 Auto_increment: 10819
    Create_time: 2021-11-18 17:28:19
    Update_time: 2021-11-18 17:28:22
     Check_time: NULL
      Collation: utf8_general_ci
       Checksum: NULL
 Create_options: row_format=DYNAMIC
        Comment: 
1 row in set (0.00 sec)

出现了很多统计选项,但我们目前只需要两个:

  • Rows
    本选项表示表中的记录条数。对于使用 MyISAM 存储引擎的表来说,该值是准确的,对于使用 InnoDB 存储引擎的表来说,该值是一个估计值。从查询结果我们也可以看出来,由于我们的 order_exp 表是使用 InnoDB 存储引擎的,所以虽然实际上表中有 10567 条记录,但是 SHOW TABLE STATUS 显示的 Rows 值只有 10350 条记录。
  • Data_length
    本选项表示表占用的存储空间字节数。使用 MyISAM 存储引擎的表来说,该值就是数据文件的大小,对于使用 InnoDB 存储引擎的表来说,该值就相当于聚簇索引占用的存储空间大小,也就是说可以这样计算该值的大小:
    Data_length= 聚簇索引的页面数量 x 每个页面的大小
    我们的 order_exp 使用默认 16KB 的页面大小,而上边查询结果显示 Data_length 的值是 1589248,所以我们可以反向来推导出聚簇索引的页面数量:
    聚簇索引的页面数量 =1589248 ÷ 16 ÷ 1024=97
    我们现在已经得到了聚簇索引占用的页面数量以及该表记录数的估计值,所以就可以计算全表扫描成本了。

现在可以看一下全表扫描成本的计算过程:

  • I/O 成本
    97x1.0+1.1=98.1
    97 指的是聚簇索引占用的页面数,1.0 指的是加载一个页面的成本常数,后边的 1.1 是一个微调值。

TIPS:MySQL 在真实计算成本时会进行一些微调,这些微调的值是直接硬编码到代码里的,没有注释而且这些微调的值十分的小,并不影响我们分析。

CPU 成本
10367x 0.2 + 1.0 = 2073

10350 指的是统计数据中表的记录数,对于 InnoDB 存储引擎来说是一个估 计值,0.2 指的是访问一条记录所需的成本常数,后边的 1.0 是一个微调值。
总成本:
98.1 + 2073 = 2171.1
综上所述,对于 order_exp 的全表扫 所需的总成本就是 2171.1。

TIPS:我们前边说过表中的记录其实都存储在聚簇索引对应 B+树的叶子节点中,所以只要我们通过根节点获得了最左边的叶子节点,就可以沿着叶子节点组成的双向链表把所有记录都查看一遍。
也就是说全表扫描这个过程其实有的 B+树非叶子节点是不需要访问的,但是 MySQL 在计算全表扫描成本时直接使用聚簇索引占用的页面数作为计算 I/O 成本的依据,是不区分非叶子节点和叶子节点的。

  1. 计算使用不同索引执行查询的代价
    从第 1 步分析我们得到,上述查询可能使用到 idx_order_no,idx_expire_time这两个索引,我们需要分别分析单独使用这些索引执行查询的成本,最后还要分析是否可能使用到索引合并。这里需要一点的是,MySQL 查询优化器先分析使用唯一二级索引的成本,再分析使用普通索引的成本,我们这里两个索引都是普通索引,先算哪个都可以。我们先分析 idx_expire_time 的成本,然后再看使用 idx_order_no 的成本。
  • 使用 idx_expire_time 执行查询的成本分析
    idx_expire_time 对应的搜索条件是:expire_time> ‘2021-03-22 18:28:28’ AND expire_time<=‘2021-03-2218:35:09’ ,也就是说对应的范围区间就是: (‘2021-03-22 18:28:28’ , ‘2021-03-22 18:35:09’ )。

思考题:扫描区间怎么样从我们复杂的 SQL 语句里取出来?前面已经讲过 了,不记得的话请回看一下《深入思考索引在查询中的使用》。

使用 idx_expire_time 搜索会使用用二级索引 + 回表方式的查询,MySQL 计算这种查询的成本依赖两个方面的数据:

  • 1、范围区间数量
    不论某个范围区间的二级索引到底占用了多少页面,查询优化器认为读取索引的一个范围区间的 I/O 成本和读取一个页面是相同的。本例中使用 idx_expire_time 的范围区间只有一个,所以相当于访问这个范围区间的二级索引付出的 I/O 成本就是:1 x 1.0 = 1.0
  • 2、需要回表的记录数
    优化器需要计算二级索引的某个范围区间到底包含多少条记录,对于本例来说就是要计算 idx_expire_time 在(‘2021-03-22 18:28:28’ ,‘2021-03-22 18:35:09’) 这个范围区间中包含多少二级索引记录,计算过程是这样的:

步骤 1:先根据 expire_time> ‘2021-03-22 18:28:28’这个条件访问一下 idx_expire_time 对应的 B+树索引,找到满足 expire_time> ‘2021-03-22 18:28:28’ 这个条件的第一条记录,我们把这条记录称之为区间最左记录。我们前面说过在 B+数树中定位一条记录的过程是很快的,是常数级别的,所以这个过程的性能消耗是可以忽略不计的。

步骤 2:然后再根据 expire_time<= ‘2021-03-22 18:35:09’这个条件继续从 idx_expire_time 对应的 B+树索引中找出最后一条满足这个条件的记录,我们把这条记录称之为区间最右记录,这个过程的性能消耗也可以忽略不计的。

步骤 3:如果区间最左记录和区间最右记录相隔不太远(在 MySQL 5.7 这个版本里,只要相隔不大于 10 个页面即可),那就可以精确统计出满足 expire_time> ‘2021-03-22 18:28:28’ AND expire_time<= ‘2021-03-22 18:35:09’条件的二级索引记录条数。否则只沿着区间最左记录向右读 10 个页面,计算平均每个页面中包含多少记录,然后用这个平均值乘以区间最左记录和区间最右记录之间的页面数量就可以了。那么问题又来了,怎么估计区间最左记录和区间最右记录之间有多少个页面呢?解决这个问题还得回到 B+树索引的结构中来。

我们假设区间最左记录在页 b 中,区间最右记录在页 c 中,那么我们想计算区间最左记录和区间最右记录之间的页面数量就相当于计算页 b 和页 c 之间有多少页面,而它们父节点中记录的每一条目录项记录都对应一个数据页,所以计算页 b 和页 c 之间有多少页面就相当于计算它们父节点(也就是页 a)中对应的目录项记录之间隔着几条记录。在一个页面中统计两条记录之间有几条记录的成本就很小了。

不过还有问题,如果页 b 和页 c 之间的页面实在太多,以至于页 b 和页 c 对应的目录项记录都不在一个父页面中怎么办?既然是树,那就继续递归,之前我们说过一个 B+树有 4 层高已经很了不得了,所以这个统计过程也不是很耗费性能。
知道了如何统计二级索引某个范围区间的记录数之后,就需要回到现实问题中来,MySQL 根据上述算法测得 idx_expire_time 在区间(‘2021-03-22 18:28:28’ , ‘2021-03-22 18:35:09’)之间大约有 39 条记录。

mysql> explain SELECT * FROM order_exp WHERE expire_time> '2021-03-22 18:28:28' AND expire_time<= '2021-03-22 18:35:09';
+----+-------------+-----------+------------+-------+-----------------+-----------------+---------+------+------+----------+-----------------------+
| id | select_type | table     | partitions | type  | possible_keys   | key             | key_len | ref  | rows | filtered | Extra                 |
+----+-------------+-----------+------------+-------+-----------------+-----------------+---------+------+------+----------+-----------------------+
|  1 | SIMPLE      | order_exp | NULL       | range | idx_expire_time | idx_expire_time | 5       | NULL |   39 |   100.00 | Using index condition |
+----+-------------+-----------+------------+-------+-----------------+-----------------+---------+------+------+----------+-----------------------+
1 row in set, 1 warning (0.00 sec)

读取这 39 条二级索引记录需要付出的 CPU 成本就是:
39x0.2+0.01=7.81
其中 39 是需要读取的二级索引记录条数,0.2 是读取一条记录成本常数,0.01 是微调。
在通过二级索引获取到记录之后,还需要干两件事儿:

1、根据这些记录里的主键值到聚簇索引中做回表操作
MySQL 评估回表操作的 I/O 成本依旧很简单粗暴,他们认为每次回表操作都相当于访问一个页面,也就是说二级索引范围区间有多少记录,就需要进行多少次回表操作,也就是需要进行多少次页面 I/O。我们上边统计了使用 idx_expire_time 二级索引执行查询时,预计有 39 条二级索引记录需要进行回表操作,所以回表操作带来的 I/O 成本就是:
39x1.0=39.0
其中 39 是预计的二级索引记录数,1.0 是一个页面的 I/O 成本常数。

2、回表操作后得到的完整用户记录,然后再检测其他搜索条件是否成立
回表操作的本质就是通过二级索引记录的主键值到聚簇索引中找到完整的用户记录,然后再检测除 expire_time> ‘2021-03-22 18:28:28’ AND expire_time< '2021-03-22 18:35:09’这个搜索条件以外的搜索条件是否成立。
因为我们通过范围区间获取到二级索引记录共 39 条,也就对应着聚簇索引中 39 条完整的用户记录,读取并检测这些完整的用户记录是否符合其余的搜索条件的 CPU 成本如下:

39 x 0.2 =7.8
其中 39 是待检测记录的条数,0.2 是检测一条记录是否符合给定的搜索条件的成本常数。

所以本例中使用 idx_expire_time 执行查询的成本就如下所示:

I/O 成本:
1.0 + 39 x 1.0 = 40 .0 (范围区间的数量 + 预估的二级索引记录条数会标成本)

CPU 成本:
39 x 0.2 + 0.01 + 39 x 0.2 = 15.61 (读取二级索引记录的成本 + 读取并检测 回表后聚簇索引记录的成本)
综上所述,使用 idx_expire_time 执行查询的总成本就是: 40 .0 + 15.61 = 55.61

  • 使用 idx_order_no 执行查询的成本分析
    idx_order_no 对应的搜索条件是:order_no IN (‘DD00_6S’, ‘DD00_9S’, ‘DD00_10S’),也就是说相当于 3 个单点区间。
    与使用 idx_expire_time 的情况类似,我们也需要计算使用 idx_order_no 时需要访问的范围区间数量以及需要回表的记录数,计算过程与上面类似,我们不详 列所有计算步骤和说明了。
    范围区间数量
    使用 idx_order_no 执行查询时很显然有 3 个单点区间,所以访问这 3 个范围区间的二级索引付出的 I/O 成本就是:
    3x1.0=3.0
    需要回表的记录数
    由于使用 idx_expire_time 时有 3 个单点区间,所以每个单点区间都需要查找一遍对应的二级索引记录数,三个单点区间总共需要回表的记录数是 58。
mysql> explain SELECT * FROM order_exp WHERE order_no IN ('DD00_6S', 'DD00_9S', 'DD00_10S');
+----+-------------+-----------+------------+-------+---------------+--------------+---------+------+------+----------+-----------------------+
| id | select_type | table     | partitions | type  | possible_keys | key          | key_len | ref  | rows | filtered | Extra                 |
+----+-------------+-----------+------------+-------+---------------+--------------+---------+------+------+----------+-----------------------+
|  1 | SIMPLE      | order_exp | NULL       | range | idx_order_no  | idx_order_no | 152     | NULL |   58 |   100.00 | Using index condition |
+----+-------------+-----------+------------+-------+---------------+--------------+---------+------+------+----------+-----------------------+
1 row in set, 1 warning (0.00 sec)

读取这些二级索引记录的 CPU 成本就是:58 x 0.2 + 0.01 = 11.61

得到总共需要回表的记录数之后,就要考虑:
根据这些记录里的主键值到聚簇索引中做回表操作,所需的 I/O 成本就是: 58x1.0=58.0
回表操作后得到的完整用户记录,然后再比较其他搜索条件是否成立此步骤对应的 CPU 成本就是:
58x0.2=11.6
所以本例中使用 idx_order_no 执行查询的成本就如下所示:
I/O 成本:
3.0+58x1.0=61.0(范围区间的数量 + 预估的二级索引记录条数)
CPU 成本:
58 x 0.2 + 58 x 0.2 + 0.01 = 23.21 (读取二级索引记录的成本 + 读取并检测回表后聚簇索引记录的成本)
综上所述,使用 idx_order_no 执行查询的总成本就是: 61.0 + 23.21 = 84.21

  • 是否有可能使用索引合并(Index Merge)
    本例中有关 order_no 和 expire_time 的搜索条件是使用 AND 连接起来的,而对于 idx_order_no 和 idx_expire_time 都是范围查询,也就是说查找到的二级索引记录并不是按照主键值进行排序的,并不满足使用 Intersection 索引合并的条件, 所以并不会使用索引合并。而且 MySQL 查询优化器计算索引合并成本的算法也比较麻烦,所以我们也不会细说。
  1. 对比各种方案,找出成本最低的那一个下边把执行本例中的查询的各种可执行方案以及它们对应的成本列出来:
    全表扫描的成本:2148.7
    使用 idx_expire_time 的成本:55.61
    使用 idx_order_no 的成本:84.21

很显然,使用 idx_expire_time 的成本最低,所以当然选择idx_expire_time 来执行查询。

mysql> EXPLAIN SELECT
    -> *
    -> FROM
    -> order_exp
    -> WHERE
    -> order_no IN ('DD00_6S', 'DD00_9S', 'DD00_10S')
    -> AND expire_time > '2021-03-22 18:28:28'
    -> AND expire_time <= '2021-03-22 18:35:09'
    -> AND insert_time > expire_time
    -> AND order_note LIKE '%7 排 1%'
    -> AND order_status = 0 \G;
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: order_exp
   partitions: NULL
         type: range
possible_keys: idx_order_no,idx_expire_time
          key: idx_expire_time
      key_len: 5
          ref: NULL
         rows: 39
     filtered: 0.13
        Extra: Using index condition; Using where
1 row in set, 1 warning (0.00 sec)

请注意:
1、MySQL 的源码中对成本的计算实际要更复杂,但是基本思想和算法是没错的。
2、在 MySQL 的实际计算中,在和全表扫描比较成本时,使用索引的成本会去除读取并检测回表后聚簇索引记录的成本,也就是说,我们通过 MySQL 看到的成本将会是:idx_expire_time 为 47.81(55.61-7.8),idx_order_no 为 72.61(84.21-11.6)。但是 MySQL 比较完成本后,会再计算一次使用索引的成本, 此时就会加上去除读取并检测回表后聚簇索引记录的成本,也就是我们计算出来的值。

5.3.2.2. 基于索引统计数据的成本计算

index dive
有时候使用索引执行查询时会有许多单点区间,比如使用 IN 语句就很容易产生非常多的单点区间,比如下边这个查询(下边查询语句中的…表示还有很多参数):

SELECT * FROM order_exp WHERE order_no IN ('aa1', 'aa2', 'aa3', ... , 'zzz');

很显然,这个查询可能使用到的索引就是 idx_order_no,由于这个索引并不是唯一二级索引,所以并不能确定一个单点区间对应的二级索引记录的条数有多少,需要我们去计算。就是先获取索引对应的 B+树的区间最左记录和区间最右记录,然后再计算这两条记录之间有多少记录(记录条数少的时候可以做到精确计算,多的时候只能估算)。MySQL 把这种通过直接访问索引对应的 B+树来计算某个范围区间对应的索引记录条数的方式称之为 index dive。
有零星几个单点区间的话,使用 index dive 的方式去计算这些单点区间对应的记录数也不是什么问题,如果 IN 语句里 20000 个参数怎么办?
这就意味着 MySQL 的查询优化器为了计算这些单点区间对应的索引记录条数,要进行 20000 次 index dive 操作,这性能损耗就很大,搞不好计算这些单点区间对应的索引记录条数的成本比直接全表扫描的成本都大了。MySQL 考虑到了这种情况,所以提供了一个系统变量 eq_range_index_dive_limit,我们看一下在 MySQL 5.7.21 中这个系统变量的默认值:

mysql> show variables like '%dive%';
+---------------------------+-------+
| Variable_name             | Value |
+---------------------------+-------+
| eq_range_index_dive_limit | 200   |
+---------------------------+-------+
1 row in set (0.00 sec)

也就是说如果我们的 IN 语句中的参数个数小于 200 个的话,将使用 index dive 的方式计算各个单点区间对应的记录条数,如果大于或等于 200 个的话,可就不能使用 index dive 了,要使用所谓的索引统计数据来进行估算。怎么个估算法?
像会为每个表维护一份统计数据一样,MySQL 也会为表中的每一个索引维护一份统计数据,查看某个表中索引的统计数据可以使用 SHOW INDEX FROM 表名 的语法,比如我们查看一下 order_exp 的各个索引的统计数据可以这么写:

mysql> show index from order_exp;
+-----------+------------+------------------+--------------+--------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
| Table     | Non_unique | Key_name         | Seq_in_index | Column_name  | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment | Visible | Expression |
+-----------+------------+------------------+--------------+--------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
| order_exp |          0 | PRIMARY          |            1 | id           | A         |       10367 |     NULL |   NULL |      | BTREE      |         |               | YES     | NULL       |
| order_exp |          0 | u_idx_day_status |            1 | insert_time  | A         |         991 |     NULL |   NULL |      | BTREE      |         |               | YES     | NULL       |
| order_exp |          0 | u_idx_day_status |            2 | order_status | A         |         991 |     NULL |   NULL |      | BTREE      |         |               | YES     | NULL       |
| order_exp |          0 | u_idx_day_status |            3 | expire_time  | A         |       10367 |     NULL |   NULL |      | BTREE      |         |               | YES     | NULL       |
| order_exp |          1 | idx_order_no     |            1 | order_no     | A         |       10225 |     NULL |   NULL |      | BTREE      |         |               | YES     | NULL       |
| order_exp |          1 | idx_expire_time  |            1 | expire_time  | A         |        9807 |     NULL |   NULL |      | BTREE      |         |               | YES     | NULL       |
+-----------+------------+------------------+--------------+--------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
6 rows in set (0.02 sec)

属性名描述

  • Table 索引所属表的名称。
  • Non_unique 索引列的值是否是唯一的,聚簇索引和唯一二级索引的该列 值为 0,普通二级索引该列值为 1。
  • Key_name 索引的名称。
  • Seq_in_index 索引列在索引中的位置,从 1 开始计数。比如对于联合索引 u_idx_day_status,来说,insert_time, order_status, expire_time对应的位置分 别是 1、2、3。
  • Column_name 索引列的名称。
  • Collation 索引列中的值是按照何种排序方式存放的,值为 A 时代表升序存放,为 NULL 时代表降序存放。
  • Cardinality 索引列中不重复值的数量。后边我们会重点看这个属性的。
  • Sub_part 对于存储字符串或者字节串的列来说,有时候我们只想对这些串的前 n 个字符或字节建立索引,这个属性表示的就是那个 n 值。如果对完整的列建立索引的话,该属性的值就是 NULL。
  • Packed 索引列如何被压缩,NULL 值表示未被压缩。这个属性我们暂时不了解,可以先忽略掉。
  • Null 该索引列是否允许存储 NULL 值。
  • Index_type 使用索引的类型,我们最常见的就是 BTREE,其实也就是 B+树索引。
  • Comment 索引列注释信息。
  • Index_comment 索引注释信息。

Cardinality 属性,Cardinality 直译过来就是基数的意思,表示索引列中不重复值的个数。比如对于一个一万行记录的表来说,某个索引列的 Cardinality 属性是 10000,那意味着该列中没有重复的值,如果 Cardinality 属性是 1 的话,就意味着该列的值全部是重复的。不过需要注意的是,对于 InnoDB 存储引擎来说, 使用 SHOW INDEX 语句展示出来的某个索引列的 Cardinality 属性是一个估计值, 并不是精确的。
前边说道,当 IN 语句中的参数个数大于或等于系统变量 eq_range_index_dive_limit 的值的话,就不会使用 index dive 的方式计算各个单点区间对应的索引记录条数,而是使用索引统计数据,这里所指的索引统计数据指的是这两个值: 使用 SHOW TABLE STATUS 展示出的 Rows 值,也就是一个表中有多少条记录。
使用 SHOW INDEX 语句展示出的 Cardinality 属性。
结合上一个 Rows 统计数据,我们可以针对索引列,计算出平均一个值重复多少次。
一个值的重复次数 ≈ Rows ÷ Cardinality
以 order_exp 表的 idx_order_no 索引为例,它的 Rows 值是 10350,它对应 的 Cardinality 值是 10220,所以我们可以计算 order_no 列平均单个值的重复次数 就是:
10350÷ 10220≈ 1.012(条)
此时再看上边那条查询语句:

SELECT * FROM order_exp WHERE order_no IN ('aa1', 'aa2', 'aa3', ... , 'zzz');

假设 IN 语句中有 20000 个参数的话,就直接使用统计数据来估算这些参数需要单点区间对应的记录条数了,每个参数大约对应 1.012 条记录,所以总共需 要回表的记录数就是:
20000 x 1.012= 21,730
使用统计数据来计算单点区间对应的索引记录条数比 index dive 的方式简单,但是它的致命弱点就是:不精确!。使用统计数据算出来的查询成本与实际所需的成本可能相差非常大。
需要注意一下,在 MySQL 5.7.3 以及之前的版本中, eq_range_index_dive_limit 的默认值为 10,之后的版本默认值为 200。所以如果大家采用的是 5.7.3 以及之前的版本的话,很容易采用索引统计数据而不是 index dive 的方式来计算查询成本。当你的查询中使用到了 IN 查询,但是却实际没有用到索引,就应该考虑一下是不是由于 eq_range_index_dive_limit 值太小导致的。

InnoDB 一棵 B+树可以存放多少行数据?

计算机在存储数据的时候,有最小存储单元,这就好比我们今天进行现金的流通最小单位是一毛。在计算机中磁盘存储数据最小单元是扇区,一个扇区的大小是 512 字节,而文件系统(例如 XFS/EXT4)他的最小单元是块,一个块的大小是 4k,而对于我们的 InnoDB 存储引擎也有自己的最小储存单元——页 (Page),一个页的大小是 16K。Innodb 的所有数据文件(后缀为 ibd 的文件), 他的大小始终都是 16384(16k)的整数倍。
数据表中的数据都是存储在页中的,所以一个页中能存储多少行数据呢? 假设一行数据的大小是 1k,那么一个页可以存放 16 行这样的数据。

对于 B+树而言,只有叶子节点存放数据,非叶子节点存放的是只保存索引信息和下一层节点的指针信息。一个非叶子节点能存放多少指针?
其实这也很好算,我们假设主键 ID 为 常用的 bigint 类型,长度为 8 字 节,而指针大小在 InnoDB 源码中设置为 6 字节,这样一共 14 字节,我们一个页中能存放多少这样的单元,其实就代表有多少指针,即 16384/14=1170 个。
那么可以算出一棵高度为 2 的 B+树,存在一个根节点和若干个叶子节点能存放 117016=18720 条这样的数据记录。
根据同样的原理我们可以算出一个高度为 3 的 B+ 树可以存放: 1170
1170*16=21902400 条这样的记录。
所以在 InnoDB 中 B+ 树高度一般为 1-3 层,就能满足千万级的数据存储。

那么为什么 MySQL 的索引要使用 B+树而不是 B 树?

而 B 树和 B+树的最大区别就是,B 树不管叶子节点还是非叶子节点,都会保存数据,这样导致在非叶子节点中能保存的指针数量变少(有些资料也称为扇出),指针少的情况下要保存大量数据,只能增加树的高度,导致 IO 操作变多, 查询性能变低。

上一篇:【数据库】Django ORM 事务使用


下一篇:sql注入系列之Sqli-labs(less-2)