关系代数

传统的集合运算是二目运算，并（∪）、差（−）、交（∩）、笛卡尔积（×）四种运算。

设关系 R 和关系 S 具有相同的目 n（即两个关系都有 n 个属性），且相应的的属性取自同一个域，t 是元组变量，t∈R 表示 t 是 R 的一个元组。

下图分别是具有三个属性列的关系 R、S ：

可以定义并、差、交、笛卡尔积运算如下：

关系 R 与关系 S 的并由属于 R 且属于 S 的元组组成。其结果关系仍为 n 目关系。记作：

下图为关系 R 与关系 S 的并：

关系R与关系S的差由属于R而不属于S的所有元组组成。其结果关系仍为n目关系。记作：：

下图为关系 R 与关系 S 的差：

关系R与关系S的交由既属于R又属于S的元组组成。其结果关系仍为n目关系。记作：

下图为关系 R 与关系 S 的交：

这里的笛卡尔积严格地讲是广义笛卡尔积(Extended Cartesian Product)。在不会出现混淆的情况下广义笛卡尔积也称为笛卡尔积。

两个分别为n目和m目的关系R和S的广义笛卡尔积是一个(n+m)列的元组的集合。元组的前n列是关系R的一个元组，后m列是关系S的一个元组。若R有k1个元组，S有k2个元组，则关系R和关系S的广义笛卡尔积有k1×k2个元组。

记作：

下图为关系 R 与关系 S 的笛卡尔积：

为了叙述上的方便，我们先引入几个记号。

选择又称为限制（Restriction）。它是在关系R中选择满足给定条件的诸元组，记作：

关系R上的投影是从R中选择出若干属性列组成新的关系。记作：

其中A为R中的属性列。投影 *** 作是从列的角度进行运算。

【例】 查询学生的姓名和所在系，即求Student关系上学生姓名和所在系两个属性上的投影：

结果如下图所示，投影之后不仅取消了原关系的某些列，而且还可能取消某些元祖，因为取消了某些属性之后，就可能出现重复行，应取消这些完全相同的行。

结果如下图所示，Student关系原来有4个元组，而投影结果取消了重复的CS元组，因此只有三个元组：

除法运算是一个复合的二目运算。如果把笛卡尔积看作“乘法”运算，则除法运算可以看作这个“乘法”的逆运算。

给定关系R(X，Y)和S(Y，Z)，其中X、Y、Z为属性组。R中的Y与S中的Y可以有不同的属性名，但必须出自相同的域集。R与S的除运算得到一个新的关系P(X)，P是R中满足下列条件的元组在X属性列上的投影：元组在X上的分量值x的像集YX包含S在Y上投影的集合。记作：

【例】在关系R中，A可以去4个值{a1，a2，a3，a4}，其中：

a1的象集为{（b1，c2），（b2，c3），（b2，c1）}；

a2的象集为{（b3，c7），（b2，c3）}；

a3的象集为{（b4，c6）}；

a4的象集为{（b6，c6）}；

S在（B，C）上的投影为{（b1，c2），（b2，c1），（b2，c3）}；

显然只有a1的象集包含了S在（B，C）属性组上的投影，所以 R÷S = { a1 }。

连接也称为θ连接，关系R与关系S的连接运算是从两个关系的广义笛卡尔积中选取属性间满足一定条件的元组形成一个新的连接：

θ在“=”时的连接为等值连接。它是从关系R和S的广义笛卡尔积中选取A、B属性值相等的那些元组，即等值连接为：

自然连接是一种特殊的等值链接，它要求两个关系中进行比较的分量必须是相同的属性组，并且在结果中把属性重复的列去掉。即若R和S中具有相同的属性组B，U为R和S的全体属性集合，则自然连接可记作：

在自然连接的基础上加上左边表上不包含自然连接中所含元组（行）的元组。

在自然连接的基础上加上右边表上不包含自然连接中所含元组（行）的元组。

外连接=左连接 并 右连接；

表drivers有两个字段，司机的名字和司机会开的车的id：

表vehicles只有一个字段，即车的id：

使用关系除法的方案，sql为：

参考：

MySQL：关系除法

MySQL基础 -- 关系代数

如果查询缓存没有命中，那么SQL请求会进入分析器，分析器是用来分辨SQL语句的执行目的，其执行过程大致分为两步：

表1 语法分析关键字然后再通过语法规则解析，判断输入的SQL 语句是否满足MySQL语法，并且生成图5的语法树。由SQL语句生成的四个单词中，识别出两个关键字，分别是select 和from。根据MySQL的语法Select 和 from之间对应的是fields 字段，下面应该挂接username；在from后面跟随的是Tables字段，其下挂接的是userinfo。

优化器的作用是对SQL进行优化，生成最有的执行方案。如图6所示，前面提到的SQL解析器通过语法分析和语法规则生成了SQL语法树。这个语法树作为优化器的输入，而优化器（黄色的部分）包含了逻辑变换和代价优化两部分的内容。在优化完成以后会生成SQL执行计划作为整个优化过程的输出，交给执行器在存储引擎上执行。

所处的位置如上图所示，这节的重点在优化器中的逻辑变换和代价优化上。

逻辑变换也就是在关系代数基础上进行变换，其目的是为了化简，同时保证SQL变化前后的结果一致，也就是逻辑变化并不会带来结果集的变化。其主要包括以下几个方面：

这样讲概念或许有些抽象，通过图7 来看看逻辑变化如何在SQL中执行的吧。

如图7所示，从上往下共有4个步骤：

1. 针对存在的SQL语句，首先通过“否定消除”，去掉条件判断中的“NOT”。语句由原来的“or”转换成“and”，并且大于小于符号进行变号。蓝色部分为修改前的SQL，红色是修改以后的SQL。2. 等值传递，这一步很好理解分别降”t2.a=9” 和”t2.b=5”分别替换掉SQL中对应的值。3. 接下来就是常量表达式计算，将“5+7”计算得到“12”。4. 最后是常量表达式计算后的化简，将”9<=10”化简为”true”带入到最终的SQL表达式中完成优化。

代价优化是用来确定每个表，根据条件是否应用索引，应用哪个索引和确定多表连接的顺序等问题。为了完成代价优化，需要找到一个代价最小的方案。因此，优化器是通过基于代价的计算方法来决定如何执行查询的（Cost-based Optimization）。简化的过程如下：

这里将配置 *** 作的代价分为MySQL 服务层和MySQL 引擎层，MySQL 服务层主要是定义CPU的代价，而MySQL 引擎层主要定义IO代价。MySQL 5.7 引入了两个系统表mysql.server_cost和mysql.engine_cost来分别配置这两个层的代价。如下：MySQL 服务层代价保存在表server_cost中，其具体内容如下：

由上可以看出创建临时表的代价是很高的，尤其是内部的myisam或innodb临时表。MySQL 引擎层代价保存在表engine_cost中，其具体内容如下：

目前io_block_read_cost和memory_block_read_cost默认值均为1，实际生产中建议酌情调大memory_block_read_cost，特别是对普通硬盘的场景。MySQL会根据SQL查询生成的查询计划中对应的 *** 作从上面两张代价表中查找对应的代价值，并且进行累加形成最终执行SQL计划的代价。再将多种可能的执行计划进行比较，选取最小代价的计划执行。

当分析器生成查询计划，并且经过优化器以后，就到了执行器。执行器会选择执行计划开始执行，但在执行之前会校验请求用户是否拥有查询的权限，如果没有权限，就会返回错误信息，否则将会去调用MySQL引擎层的接口，执行对应的SQL语句并且返回结果。例如SQL：“SELECT * FROM userinfo WHERE username = 'Tom'“假设 “username“ 字段没有设置索引，就会调用存储引擎从第一条开始查，如果碰到了用户名字是” Tom“， 就将结果集返回，没有查找到就查看下一行，重复上一步的 *** 作，直到读完整个表或者找到对应的记录。需要注意SQL语句的执行顺序并不是按照书写顺序来的，顺序的定义会在分析器中做好，一般是按照如下顺序：

如果命中的记录比较多，应用会从MySql Server一批批获取数据

本文从MySQL中SQL语句的执行过程作为切入点，首先介绍了查询请求的执行流程，其中将MySQL的处理分为MySQL Server层和MySQL存储引擎层。通过介绍SQL语句的流转，引出了后面要介绍的5大组件，他们分别是：连接器、查询缓存、分析器、优化器、执行器。后面的内容中对每个组件进行了详细的介绍。连接器，负责身份认证和权限鉴别；查询缓存，将查询的结果集进行缓存，提高查询效率；分析器，对SQL语句执行语法分析和语法规则，生成语法树和执行计划；优化器，包括逻辑变换和代价优化；执行器，在检查用户权限以后对数据进行逐条查询，整个过程遵守SQL语句的执行顺序。

了解查询优化器的作用之前，我们先来看看一条 SQL 语句的执行都需要经历哪些环节，如下图所示：

你能看到一条 SQL 查询语句首先会经过分析器，进行语法分析和语义检查。我们之前讲过语法分析是检查 SQL 拼写和语法是否正确，语义检查是检查 SQL 中的访问对象是否存在。比如我们在写 SELECT 语句的时候，列名写错了，系统就会提示错误。语法检查和语义检查可以保证 SQL 语句没有错误，最终得到一棵语法分析树，然后经过查询优化器得到查询计划，最后交给执行器进行执行。

查询优化器的目标是找到执行 SQL 查询的最佳执行计划，执行计划就是查询树，它由一系列物理 *** 作符组成，这些 *** 作符按照一定的运算关系组成查询的执行计划。在查询优化器中，可以分为逻辑查询优化阶段和物理查询优化阶段。

逻辑查询优化就是通过改变 SQL 语句的内容来使得 SQL 查询更高效，同时为物理查询优化提供更多的候选执行计划。通常采用的方式是对 SQL 语句进行等价变换，对查询进行重写，而查询重写的数学基础就是关系代数。对条件表达式进行等价谓词重写、条件简化，对视图进行重写，对子查询进行优化，对连接语义进行了外连接消除、嵌套连接消除等。

逻辑查询优化是基于关系代数进行的查询重写，而关系代数的每一步都对应着物理计算，这些物理计算往往存在多种算法，因此需要计算各种物理路径的代价，从中选择代价最小的作为执行计划。在这个阶段里，对于单表和多表连接的 *** 作，需要高效地使用索引，提升查询效率。

在这两个阶段中，查询重写属于代数级、语法级的优化，也就是属于逻辑范围内的优化，而基于代价的估算模型是从连接路径中选择代价最小的路径，属于物理层面的优化。

查询优化器的目的就是生成最佳的执行计划，而生成最佳执行计划的策略通常有以下两种方式。

但我们需要记住，SQL 是面向集合的语言，并没有指定执行的方式，因此在优化器中会存在各种组合的可能。我们需要通过优化器来制定数据表的扫描方式、连接方式以及连接顺序，从而得到最佳的 SQL 执行计划。

你能看出来，RBO 的方式更像是一个出租车老司机，凭借自己的经验来选择从 A 到 B 的路径。而 CBO 更像是手机导航，通过数据驱动，来选择最佳的执行路径。

大部分 RDBMS 都支持基于代价的优化器（CBO），CBO 随着版本的迭代也越来越成熟，但是 CBO 依然存在缺陷。通过对 CBO 工作原理的了解，我们可以知道 CBO 可能存在的不足有哪些，有助于让我们知道优化器是如何确定执行计划的。

首先，我们先来了解下 MySQL 中的 COST Model ， COST Model 就是优化器用来统计各种步骤的代价模型，在 5.7.10 版本之后，MySQL 会引入两张数据表，里面规定了各种步骤预估的代价（Cost Value） ，我们可以从 mysql.server_cost 和 mysql.engine_cost 这两张表中获得这些步骤的代价：

server_cost 数据表是在 server 层统计的代价，具体的参数含义如下：

由这张表中可以看到，如果想要创建临时表，尤其是在磁盘中创建相应的文件，代价还是很高的。

然后我们看下在存储引擎层都包括了哪些代价：

engine_cost 主要统计了页加载的代价，我们之前了解到，一个页的加载根据页所在位置的不同，读取的位置也不同，可以从磁盘 I/O 中获取，也可以从内存中读取。因此在 engine_cost 数据表中对这两个读取的代价进行了定义：

既然 MySQL 将这些代价参数以数据表的形式呈现给了我们，我们就可以根据实际情况去修改这些参数。因为随着硬件的提升，各种硬件的性能对比也可能发生变化，比如针对普通硬盘的情况，可以考虑适当增加 io_block_read_cost 的数值，这样就代表从磁盘上读取一页数据的成本变高了。当我们执行全表扫描的时候，相比于范围查询，成本也会增加很多。

比如我想将 io_block_read_cost 参数设置为 2.0，那么使用下面这条命令就可以：

我们对 mysql.engine_cost 中的 io_block_read_cost 参数进行了修改，然后使用 FLUSH OPTIMIZER_COSTS 更新内存，然后再查看 engine_cost 数据表，发现 io_block_read_cost 参数中的 cost_value 已经调整为 2.0。

如果我们想要专门针对某个存储引擎，比如 InnoDB 存储引擎设置 io_block_read_cost ，比如设置为 2，可以这样使用：

然后我们再查看一下 mysql.engine_cost 数据表：

从图中你能看到针对 InnoDB 存储引擎可以设置专门的 io_block_read_cost 参数值。

总代价的计算是一个比较复杂的过程，上面只是列出了一些常用的重要参数，我们可以根据情况对它们进行调整，也可以使用默认的系统参数值。

那么总的代价是如何进行计算的呢？

在论文 《Access Path Selection-in a Relational Database Management System》 中给出了计算模型，如下图所示：

你可以简单地认为，总的执行代价等于 I/O 代价 +CPU 代价。在这里 PAGE FETCH 就是 I/O 代价，也就是页面加载的代价，包括数据页和索引页加载的代价。W*(RSI CALLS) 就是 CPU 代价。W 在这里是个权重因子，表示了 CPU 到 I/O 之间转化的相关系数，RSI CALLS 代表了 CPU 的代价估算，包括了键比较（compare key）以及行估算（row evaluating）的代价。

为了让你更好地理解，我说下关于 W 和 RSI CALLS 的英文解释：W is an adjustable weight between I/O and CPU utilization. The number of RSI calls is used to approximate CPU utilization。

这样你应该能明白为了让 CPU 代价和 I/O 代价放到一起来统计，我们使用了转化的系数 W，

另外需要说明的是，在 MySQL5.7 版本之后，代价模型又进行了完善，不仅考虑到了 I/O 和 CPU 开销，还对内存计算和远程 *** 作的代价进行了统计，也就是说总代价的计算公式演变成下面这样：

总代价 = I/O 代价 + CPU 代价 + 内存代价 + 远程代价

这里对内存代价和远程代价不进行讲解，我们只需要关注 I/O 代价和 CPU 代价即可。

---