数据库设计之查询处理和查询优化

关系数据库的查询处理

查询处理的过程

查询处理与代码的处理过程类似，分为五个步骤：

1. 查询分析： 就是语法词法分析，检查是否符合语法
2. 查询检查： 首先进行语义分析有时也把这个归到查询分析，权限检查即安全性检查，还要进行完整性检查
3. 查询内部表示： 用SQL写的查询命令DBMS是无法理解的所以要进行进一步翻译，解释成为关系代数表示。这也就相当于C语言的编译。
4. 查询优化：这也是本次学习的主要内容，查询优化会对查询效率有很大的影响。
5. 查询执行： DBMS根据优化后的查询命令执行查询操作，前面翻译成关系代数的命令依然无法被机器理解，机器理解的只能是二进制码，所以DBMS还会进行一次翻译。DBMS可以用两种方式完成该操作，一个是解释一个是编译。编译就和C语言编译一样生成一个可执行文件。解释则不生成可执行代码，解释一句就执行一句。效率吗，当然是编译更好。

查询的基本操作

上面的查询处理都是对查询命令进行一系列操作，操作命令基本上是由四类基本的操作组成的：

• 选择操作

  • 顺序扫描法：顺序搜索数据库逐条检查元组是否符合选择条件

  • 二分查找法：主要针对对应属性有序，学过算法的都知道这个是log的

  • 使用索引扫描法：通过索引找到要找的元组指针，然后通过指针找到元组

  • 复合选择：

    • 组合索引选择：和索引选择一样不过这里要求有组合属性的索引
    • 单独索引：对索引找到的元组进行判断符合留下不符合删去
    • 多个索引合取：对每个选择条件通过索引找到符合元组，最后在对元组集合合取
      以上都是复合条件使用AND连接的情况下：
      如果使用OR连接除非是每个都有对应的索引，否则不能通过索引选择。如果每个都有索引的话，与上面第三个类似，只不过最后是析取。

• 连接操作

  • 循环嵌套法：就是二重循环遍历，不过要注意的是要选择较少块的关系作为外循环。
  • 索引嵌套循环法： 就是在上面二重循环中把内层循环的遍历替换成通过索引寻找。
  • 排序合并法：对两个排好序的关系只需要遍历两个关系就可以了，这里类似算法中将两个排好序的数组合并为一个，很容易理解。
  • 散列连接法：散列连接是利用Hash函数将关系中的元组按连接属性分成一个个小的组，这样就可以减少不必要的连接尝试。利用的原理是相同属性值得散列值一定相等，但是相同散列值的属性值不一定相等。

• 投影操作：非常简单，基本上就是在消除重复元组时会有代价

• 集合运算：交、并、差就是顺序合并，笛卡尔积可以归为连接类。

查询优化

查询优化主要有代数优化、基于存储路径的优化、基于代价估计的优化。

代数优化

代数优化的中心思想是利用代数运算的运算律将选择和投影尽可能移到连接前执行，从而减少关系的元组数，消除本就不能连接的元组之间的判断、遍历。
代数运算律：

1. 连接、笛卡尔积交换律
2. 连接、笛卡尔积的结合律
3. 投影的串接定律
4. 选择的串接定律
5. 选择与投影操作的交换律
6. 选择与笛卡尔积的交换律
7. 选择与并、差、自然连接的分配律
8. 投影与笛卡尔积的分配律
9. 投影与并的分配律

启发式规则：

1. 在关系代数式中尽可能早地执行选择操作。
2. 投影运算和选择运算尽量同时进行
3. 把投影同其前或后的二元操作结合起来同时进行，避免为去掉某些属性而扫描一遍关系。
4. 把某些选择操作同在他前面要执行的笛卡尔积结合起来，合并成为一个连接操作。
5. 存储公共子表达式，先计算一次公共子表达式并把结果写入中间文件，以达到节省时间的目的。

基于存取路径的优化

相较于代数优化只优化基本操作的执行次序，基于存取路径的优化就是对各个基本存取操作的效率的优化，也就是更深入底层。
由于上面介绍的投影和集合操作基本都没什么消耗或者包含在选择连接中所以只需知道选择和连接的优化就行了。

• 选择操作的启发式规则
  1. 对于小关系，使用顺序扫描
  2. 对于选择条件是“主键=值”的查询，查询结果最多是一个元组，可以选择主键索引。
  3. 对于选择条件是“非主属性=值”的查询，并且选择列上有索引，需要估算查询结果的元组数目。如果比例小于10%可以使用索引法，否则还是采用顺序法。
  4. 对于选择条件是属性上的非等值查询或者范围查询，并且选择列上有索引，其选择方法与非主属性上的等值查询类似，要估算查询结果的元组数目。
  5. 对于用AND连接的合取选择条件，如果有涉及这些属性的组合索引，优先采用组合索引扫描方法，如果某些属性上有一般的索引，则可以用索引扫描法，否则使用顺序法。
  6. 对于用OR连接的析取选择条件，一般使用顺序扫描法。
• 连接操作的启发式规则
  1. 如果两个表都已经按照连接属性排序，选择排序合并方法。
  2. 如果一个表在连接属性上有索引，选用索引连接方法。
  3. 如果上面两个规则都不适用，其中一个表较小，选用散列法。
  4. 选用嵌套循环法，选择其中娇小的表，确切地讲是占用存储块数少的表作为外表。

基于代价估算的优化

需要考虑的因素：

• 访问存储器的代价
• 存储代价
• 计算代价
• 内存使用代价
• 通信代价

主要对前面的基于存取路径的优化进行代价估计
选择操作：

• 顺序扫描：平均为B_R/2.(B_R为关系R的元组占用的块数)

• 二分查找法：log₂B_R

• 索引查找法：L+S（L为索引层数，S为寻找的元组数）
  连接操作：

• 嵌套循环法：B_R+B_RB_S/（K-1）+（Krs*N_rN_s）/Mrs。（B_S与B_R一样，K为内存的块数，Nr为R的元组数，Ns一样Frs连接的结果占比例，Mrs一块能存放的元祖数量）；由B_R+B_RB_S/（K-1）可以看出B_R小的时候总值更小。所以要选择小的块的关系作为外表。
  ：B_R+B_RB_S/（K-1）为读取；
  （KrsN_r*N_s）/Mrs为写入。

• 索引嵌套循环法：B_R+N_S*c（c为索引的代价）

B_R为外层；
N_S*c为内层索引。

• 排序合并：B_R+B_S+（KrsN_rN_s）/Mrs（+2B_R+（2B_Rlog₂B_R）+2B_S+（2B_S*log₂*B_S））。

B_R+B_S为读取；（KrsN_rN_s）/Mrs为写入；
（+2B_R+（2B_Rlog₂B_R）+2B_S+（2B_S*log₂*B_S））为排序。