数据库查询优化技术 - zzyoga/JustTest GitHub Wiki

1.什么是查询优化

关系数据库最大的问题就是执行效率问题，比如乘积运算，这样的运算会使数据量爆炸。但是如果同样的检索需求可以用不同的关系代数表达式表达，那么我们就能优化速度：不如把乘积操作放在选择操作之后。就是说：关系代数的操作次序很重要。

查询优化：“如何使数据库查询的执行时间最短？”

我们有三个层面进行优化：1.语义优化：利用模型的语义以及完整性规则，优化查询。2.语法优化（逻辑层优化）：利用语法结构，优化操作执行顺序。3.执行优化（物理层优化）：存取路劲和执行算法的选择与执行次序优化。

2.查询优化的总体思路

（1）语义优化（内容等价性）：用户/程序员在写SQL语句的时候注意要去掉无关的表，属性等，改写成等价的效果更好的语句。DBMS怎么自动的进行上述的优化？---->语义等价性，完整性规则。

（2）语法优化（逻辑层优化）：DBMS可以自动的将数据库的查询语句转换成关系代数的表达形式。但是DBMS不能按照直接转换过来的次序执行，因为如前面的问题。那么DBMS怎么在语法层面优化？

（3）执行优化（物理层优化）：在形成物理查询计划的时候，每个关系代数选择什么样的算法，我们需要进行代价估计。

我们在写了一条SQL语句进行执行的时候--->编译成关系代数的表达--->进行语法优化--->执行优化：为每个关系代数的操作选取优化的执行层的程序，形成物理查询计划--->执行引擎依据查询计划调用相应的例行程序进行处理并返回结果。（DML编译器做逻辑层和物理层的优化）。

3.逻辑层优化策略

基本思想是：（1）改变关系代数的操作次序，尽可能的早做选择和投影运算，使得中间结果尽量的少。（2）把选择和投影串接起来：一元运算序列可一起执行，只需要对整个关系扫描一遍。（3）把投影与其前或后的二元运算结合起来：在第一次用关系时去掉一些无关属性，可以避免多次扫描整个关系。（4）把某些选择与其前的笛卡尔积合并成一个连接。（5）执行连接运算前对关系做适当的预处理。（6）找出表达式里的公共子表达式。

我们可以将一个关系代数表达成一颗语法树，从叶到根反应了它的执行次序。用这种关系代数的语法树可以清晰的表达和优化一条语句。

3.1等价变换定理

什么情况下才能交换次序而不改变逻辑含义？这就需要等价变换定理。

我们知道所有的操作都可以由5种基本的操作组合而成：并，差，积，选择，投影。所以等价变换定理只考虑基本操作。最基本的思想的这五种操作两两交换，看交换后是不是等价（直观的看就是操作结果是不是一样）的。

（1）定理L1：连接与连接，积与积的交换律：这个定理的用处主要是在我们在实现物理查询的具体算法时，涉及到具体的怎么处理内存和磁盘之间的装入次序的时候可以用到。

（2）定理L2：连接与连接，积和积的结合律：E1，E2，E3是关系代数表达式，F1，F2是条件，我们有 （E1 连接F1 E2）连接F2 E3 = E1 连接F1 （E2 连接F2 E3）。自然连接也满足。（E1E2）E3 = E1（E2E3），注意并运算和交运算也有这种规律。：这个定律是就是我们在算中间结果的时候，经常先算结果集合小的运算。

（3）定理L3：投影串接律：A属于B ， 对E先做投影B在做投影A等价于对E直接做A：这个定理可以双向使用，在优化语法树的时候可以用到，正向使用的时候使两趟扫描数据库变成了一趟扫描。

（4）定理L4:选择串接律：F1，F2是条件，对E先做F2选择，再做F1选择操作 等价于 对E直接做F1^F2的选择：这个定理也可以双向使用。

（5）定理L5：选择和投影交换定律：先做选择再做投影 = 先做投影再做选。（一定要保证投影后的属性能进行判断，这是这个定理能用的前提）。如果先做选择在做投影时，选择使用的属性比投影的要多，我们可以先扩展属性做投影，然后选择最后在做一次投影把扩展的属性去掉。

（6）定理L6：选择和积的交换律：--如果选择的条件F只涉及E1中的属性，则E1E2之后再做选择，等价于先对E1做选择然后E2。--如果选择的条件F=F1^F2，则E1*E2之后再做选择，等价于对E1做F1选择 * （对E2做F2选择）。所以这个定理让我们尽可能的先做选择操作。

（7）定理L7：投影和积的交换律：对E1*E2做投影，等价于先对E1中要投影的属性做投影 * 对E2中要投影的属性做投影。它能减少每一条记录的长度，能够增加内存存放的记录条数。

（8）定理L8：选择和并的交换律：对（E1并E2）做选择，等价对E1做选择 并 对E2做选择 （要求E1，E2一定是并相容的）。这个定理可以降低中间结果。

（9）定理L9：选择和差的交换律：同8 对（E1-E2）做选择，等价于对E1做选择 - 对E2做选择。

（10）定理L10：投影和并的交换律：先做并运算，再做投影 等价于 先做投影再做并运算。但是投影和差的交换律并不成立。

3.2基于关系代数的查询优化算法

Input：关系代数的语法树 Output：计算该表达式的程序

Method： （S1）依据定理L4把复杂条件变成一些列选择的串接。（S2）依据定理L4-L9，尽可能的把它移动到树的底部。（S3）对每个投影，依据定理L3，L7，L10和L5，尽可能的把它移动到树的底部。如果一个投影是对某个表达式所有属性进行的，则去掉。（S4）...

4.物理层查询优化

根据前面通过逻辑优化得到的关系代数，我们可以继续进行物理层优化，即选择合适高效的执行算法。

物理查询运算符：直接和程序相关，是关系代数操作的特定实现。

（1）获取关系元组的操作：TableScan（R）---表空间扫描算法；SortTableScan（R）---表空间扫描排序算法；IndexScan（R）---索引扫描算法；SortIndexScan（R）---索引扫描排序算法。

（2）关系操作的各种算法实现：元组的选择，投影等等，以及集合和包上的操作，具体的就是前面介绍的一趟算法，两趟算法，基于索引的算法，基于散列的算法和基于排序的算法等等。

（3）迭代器的构造

物理查询的基本思路是：选择代价最小的执行方案。首先获取数据库的相关信息，知道每个操作都有那些程序可以实现，然后选择相应的属性例行程序，依据相关信息进行代价估计，选择代价最小的作为最终的执行方案。

4.1代价估计

DBMS衡量物理查询计划的优劣指标：IO访问次数，CPU的占用时间，内存使用代价，中间结果存储代价，计算量等等。

依据数据库的一些统计信息---存放在数据字典或者系统目录中 来进行代价估计。比如T(R),B(R),I(R)...，分别表示关系R的元组数目，磁盘块数，每个元组的字节数

需要注意的是，当一个表装入内存和创建索引的时候，这些统计信息不是被自动收集的，必须由DBA使用特定的命令来完成信息统计，这些命令就是收集统计信息并把其存入系统目录的实用程序。也就是说DBMS必须提供相应的统计信息的操作。DBA需要保证统计信息不过时。Mysql通过语句Analyze table tablename 来收集统计信息。