数据库查询处理及优化
时间：2020.03.23
地点：陆河
主题：关系数据库查询处理及优化
【查询操作】是数据库最常用数据操作，查询速度快慢直接影响数据库系统（DBS）执行效率。为提高系统效率，必须提高查询效率。本文介绍关系型数据库相关查询优化技术；
首先介绍关系数据库管理系统【查询处理】步骤，然后再介绍【查询优化】相关技术。
查询优化技术有2种：
（1）代数优化：通过关系代数表达式优化；
（2）物理优化：涉及底层数据存储路径和底层操作算法选择优化；
1查询处理
2查询优化
1.【查询处理】
（1）关系数据库查询处理步骤；
（2）实现查询操作的算法；
1.1.1关系数据库查询处理步骤
1.1.2实现查询操作的算法
RDBMS中查询主要涉及操作有：
选择、投影和连接，其中投影比较简单，这里不介绍；
介绍选择+连接实现所用到各种算法；
（1）选择的实现算法
a.全表扫描
b.索引（或散列）扫描
【例1-1】
select * from student where <where_condition> 中的where子句有:a. 无where子句;b. Sname='zhuguozhu';c. Sage > 30;d. Sname='zhuguozhu' and Sage > 20;
1、全表扫描：对查询基表逐行进行扫描，逐一检查每个元组是否满足
where子句中给出的条件，把满足条件的元组作为结果进行输出。
2、索引（或散列）扫描：如果条件表达式的选择属性列上，建立了索引，可以用索引扫描方法。通过数据库中的索引首先找到满足的元组的指针，再通过指针直接在查找基本表中找到满足条件的元组（记录）；
例如，Sname=“zhuguozhu”，并且Sname上定义了索引，则可以使用索引得到Sname为“zhuguozhu”的元组的指针，然后通过这个指针在student表中查找到该学生相关信息。
---------------
例如，Sage>30，并且Sage定义B+树索引，可以直接使用B+树索引找到Sage=30索引项，以该索引项为入口，访问B+树顺序集，进而得到Sage>30所有元组指针，最后通过这些指针在student表中查找到所有年龄大于30的学生信息。
---------------
例如，Sname=’zhuguozhu’ and Sage>20，假设student表中对Sname和Sage都定义索引。
该选择操作执行有两种算法，
(1)分别找到Sname=’zhuguozhu’的一组元组指针和Sage>20的元组指针，求这两组元组指针的交集，再在student表中根据两组元组指针的交集进行检索，就可以得到年龄大于20，并且姓“zhuguozhu”的学生信息。
(2)先求出Sname=’zhuguozhu’指针，通过这组指针在student表中检索，在得到的元组集合中再检查另外一个选择条件Sage>20是否满足，把满足条件的元组作为结果输出。
(2)连接操作实现算法
连接操作是查询处理中最耗时操作。
a. 等值连接（或自然连接）b. 嵌套循环算法c. 排序合并算法d. 索引连接算法
e.g.:
select * from student , sc where student.sno = sc.sno;嵌套循环算法：简单可行方法，使用两层循环进行查询。对外层循环表（对应基表student）的每一个元组（记录），检索内层循环表（对应基表sc）中的每一个元组(记录)，检查这两个元组连接属性(sno)上是否相等。如相等，则把这两个元组串在一起作为查询结果输出，直到外层循环表元组都处理完为止。
实现简单，适用于小表，如大表，则循环检索的时间长，检索效率低；
假设student表有1000条学生记录，每个学生选修10门课程，那么sc表中将有10000条记录。
如采用嵌套循环方法，学生表只需要检1次即可，但是sc表却要检索1000次，每一次都要把它的10000条记录到检索一遍，总共需要检索10000*1000=10000000条元组，时间代价比较高，检索效率较低。
排序-合并算法：适合连接待连接表已经安装连接属性排序序的情况；
a. 对待连接表按照连接属性进行排序（如已排序则省略此步骤），连接首先是对student表和sc表安装连接属性sno进行排序；
b. 首先去student表第一个sno, 然后依次检索sc表中，只要检索到具有相同sno的元组，就进行元组串联；
c. 当在sc表中检索到sno不同的第一个sc元组时，就需要返回student表，扫描下一个元组，再回到sc表中扫描和新的sno相同的元组，把它们串联起来
d. 重复b, c步骤，直到整个student表检索完毕；
/////////////////////////////////////////////////
该方法好处是连接的两个表student和sc只需要检索一遍即可，大大节省了检索所花费的时间。
如果两个表开始并未排序，那么整个连接所花费的时间还需要加上排序时间，但是对于大表而言，先排序再使用排序-合并算法进行连接会大大的减少执行的时间。
例如:student中有1000条记录，每个学生10们课，sc表中有10000条记录，连接所需要检索的次数为1000*10 = 10000条，跟前面的10000000相比，时间减少很多。
索引连接算法：建立在索引基础上的一种连接方法；
a. 在sc表中建立属性sno的索引，如果原表已经建立，则省略此步骤
b. 对student表中的每一元组，根据sno的值通过sc表的索引来查找对应的元组记录；
c. 把找到的sc表中的元组和student的元组连接起来；
d. 循环执行b c步骤，直到student表检索完毕。
///////////////////////////////////////////////////////////////////////////
该方法非常适用于大表，连接所花费的时间非常少，基本不用扫描不满足条件的元组记录。
2.关系数据库系统查询优化
先对用户所给的语句进行转换，将其转换为一串执行时间较少的关系代数表达式（代数优化），并为这些运算选择较优的存取路径（物理优化），以便能大大减少执行时间；
查询的执行开销=I/O代价+CPU代价+内存代价+通信代价
在关系代数代数运算中：笛卡尔积、连接运算是最费时间和空间的；
关系代数表达式的优化准则：
a. 尽早进行选择运算；b. 同时进行投影运算和选择运算；c. 把投影运算同其前或其后的双目运算结合起来；d. 合并笛卡尔积与其后的选择运算为连接运算；e. 存储公共子表达式；
2.1关系代数表达式的优化算法
算法：关系代数表达式的优化；
输入：一个关系表达式的查询树；
输出：优化后的查询树；
2.2物理优化的优化算法
（1）启发式规则优化
（2）代价估算的优化
基于代价优化方法，优化器对查询各种执行策略进行代价估算，这时就要数据库中数据字典中所存储的一些统计信息（MySQL的统计信息是存储在InnoDB中）进行辅助。
（3）（1）+（2）相结合的优化--》首先会基于启发式规则优化，从多种执行策略中选择若干较优候选策略，从而减少代价估算工作量，然后再用基于代价估算的优化算法，分别估算出这些候选策略执行代价，进而较快的选出最终的优化策略；
3.小结：
实际的数据库系统--》综合使用了各种技术，所以【优化器】是比较复杂的；