一. 关系数据库系统的查询处理过程

要做优化, 首先理解查询处理过程.
查询处理: 把用户提交给RDBMS的查询语句转换为高效的查询执行计划.
经过的步骤: 查询分析, 查询检查, 查询优化(指的是DBMS完成的)和查询执行.

1)查询分析

对查询语句进行扫描, 词法分析(识别出保留字, 变量, 运算符, 发现拼写错误)和语法分析(判断是否符合SQL的语法规则, 出现错误就报告SQL语法错误)

2)查询检查

有效性检查: 对符合语法规则的查询语句进行语义检查, 也就是根据数据字典中有关的模式定义去检查语句中的数据库对象, 比如表名, 属性名是否都在存在和有效.
视图转换: 把对视图的操作求解, 转换成对基本表的操作
安全性: 还要检查用户权限
完整性检查: 根据数据字典中存储的完整性约束进行检查(主键约束, 外键约束, 用户自定义约束非空, 取值范围等).
如果都没有问题, 那么就把SQL查询语句转换成内部表示(等价的关系代数表达式), 构建出一棵查询的语法分析树.

语法分析树

3) 查询优化

是数据库技术的关键. 划分为代数优化(逻辑优化), 物理优化(存取路径, 底层算法).
优化的依据: 基于规则, 基于代价, 基于语义
优化器得出一个执行策略, 并生成相应的查询计划.

4) 查询执行

由code generator负责生成执行能够"查询计划"的实际代码, 然后加以执行并回送查询结果.
一个典型的查询过程可以参考这个, 里面写的非常详细!! http://www.jb51.net/article/33535.htm

过程

二. 查询优化

1. 查询优化的意义

把最好的程序员的思维做在了DBMS中, 并且提供数据库存储的数据字典, 物理存储信息供决策, 比普通应用程序员自己写的好很多. 因此选择比较好的DBMS, 本身就是查询优化的基础条件.

2. 选择操作的算法

naive table scan: 全表扫描, 按照物理次序读取Student表的M个block到内存, 检查是否满足条件, 满足则输出.
index scan: 如果选择条件中的属性上有索引(比如学号, 姓名, age可能有B+), 那么可以用索引扫描方法, 通过索引先找到满足条件的元组的指针, 然后通过指针在基本表中找到元组.

3. 连接操作的算法

连接操作在select中是最最最费时间的, 因此有很多种算法.
做一个简单的连接比如select * from student S inner join on SC where S.sno = SC.sno;

1. naive nested loop join: O(N^2), 嵌套循环
2. sort-merge join排序合并算法: 假设sno做连接, 那么两个表都按照sno排序, 排好序了以后按照Student, 对SC进行扫描, 注意由于排好序了, 因此两张表都只要扫描一遍即可, 总的时间复杂度是O(NlgN + 2N) = O(NlgN)
   如果已经排好序了, 那就更快了.
3. index join: 假设SC表上已经建立了属性sno的索引, 那么对于Student中的每一个元组, 在SC中找到对应的元组的时间就不是全表扫描O(N), 而是O(lgN).
4. hash join: (神奇的hash大法!) 对记录行数较少的那张表, 假设是Student表, 建立一个hashtable, 然后对大表SC, 用同样的hash函数, 对每个元组上的sno进行hash, 如果在hashtable中有对应的Student元组, 就连接.
   整个时间开销是O(N), 当然了, 相比其他算法, 额外的空间开销是O(N).

4. 代价模型

在大数据条件下, 代价模型不能只是简单的CPU时间和内存开销. 要关注IO和网络通信这些比较慢的瓶颈.
DBMS会根据其特有的代价模型来计算各种查询执行策略的代价, 然后选取代价最小的方案.
对集中式数据库: 主要开销是IO
对分布式数据库: 主要开销是IO + 网络通信代价

5. 以一个实例分析连接操作的时间开销

select Student.sname from Student, SC where Student.sno = SC.sno and SC.cno = 2;

1. naive: 先全体连接再逐个筛选
   假设1000行Student记录, 10000行SC选课记录, 假设1个block能放10行Student, 1个block也能放100行SC.
   那么naive算法IO开销 = (假设内存最多放6个block)
   读入行记录: 1000/10 + (10000/100) * ( 1000/(105) ) = 2100 block
   写入中间结果到硬盘: 100010000 / 10 = 10^6 block
   读出中间结果, 进行where条件筛选: 10^6 block
   选择列, 做输出: 0
   所以IO开销 = x * 10^6
   这其实也是mapreduce为什么这么慢的原因...大量的IO开销.

2. 优化: 先筛选再连接
   对查询的优化, 应当关注如何降低参与连接的元组数目. 本语句中, 先进行where筛选, 再连接才是正道.
   读入SC所有元组进行筛选: 10000/100 = 100 block
   由于筛选出来的元组很少, 比如只有50行 (1个block), 那么放在内存中即可, 不用落盘.
   读入Student所有元组进行连接: 1000/10 = 100 block
   连接的时候, 把结果需要存盘: 100 * 5 = 500 block,
   再对这500个block进行连接条件的筛选, 需要读入: 500 block

100 + 100 + 500*2 = 1200
所以IO开销 = x * 10^3
降低到了千分之一的数量级别.

这种先做选择, 再做连接的基本优化, 叫做代数优化. 因为我们并没有建立或者利用任何物理结构, 因此代数优化是算法上的优化.
同样地, 如果我们对SC表中sno建立了B+Tree index, 那么我们就不用读入所有的块, 只要读取包含指定sno的块,这样也能提高速度, 这叫做物理优化.

三. 代数优化

1. 核心问题

关系代数表达式的等价变换规则
经验性的优化策略

2. 变换五大核心规则

总结起来就是: "(连接类的)交换律, 结合律; (投影和选择类的)串接律, (这两大类相互之间)分配率"

1. E1 X E2 = E2 X E1, (E1 X E2) X E3 = E1 X (E2 X E3)做笛卡尔积, 多个表做连接是满足交换律和结合律的

2. 投影和选择的串接定律
   多层的投影可以取小的那个
   多层的选择可以取交集(其实也是那个范围比较小的), 这样能够把多次选择多次表的扫描, 改成一次.

3. 选择与投影交换律: 选择和投影的顺序可以随意改变

4. 选择与笛卡尔积, 并, 自然连接, 差的分配律: 处在后面的选择, 可以与处在前面的二目运算顺序进行调整, 使得对相应的表先实施选择, 再实现连接等二目运算. 这个非常重要, 是先选择后进行二目运算的依据, 又名"选择提前".

5. 选择与笛卡尔积, 并的分配率: 可以先投影, 也可以先进行二目运算

还有几个规则不是特别有用, 不叙述

3. 经验性优化五大策略

其实就是"选择, 合并, 视图"

1. 选择运算尽可能先做, 这是最最最最重要和基本的, 这样往往使得执行代价减少了几个数量级, 主要的原理就是选择运算能够大大降低参与连接的元组的行数, 使得连接生成的A•B结果也大大被缩小.

2. 把选择和投影运算同时进行, 如果有若干投影和选择运算, 并且他们都是针对同一个表, 那么可以在扫描这个表的时候同时完成这些所有的运算, 以此避免重复扫描这张表.

3. 把投影与其前或者后的双目运算(笛卡尔积, 等值连接, 并集, 差集)结合起来, 也就是说, 没有必要为了选择出几个字段而单独再重新扫描全表.

4. 把某些选择和在它前面要执行的笛卡尔积结合起来成为一个连接运算(比如变成等值连接), 这是因为连接运算要比同样情形下的笛卡尔积节省很多时间.
   杜老师说: "笛卡尔积原则上是不能自己执行的!!!太浪费了!!!"

笛卡尔积先进行了 O(N • M)操作 生成了A•B大小的中间文件, 存盘, 然后读盘, 然后再按照where选择进行筛选得到结果; 对比之下, 等值连接运算也进行了O(N•M)操作, 但是还进行了筛选, 只生成比较小的中间文件, 存盘和读盘的是一个非常小的结果集合. 大大减少了IO开销.

5. 找出公共子表达式(一次计算, 多次使用). 比如很多的查询都基于某个公共部分, 那么可以定义一个公共子表达式, 然后先计算一次公共子表达式, 然后把它存盘, 供其他大量的表达式来使用. 我们定义视图其实就是在实践这种策略.

4. 举例子

1

这是一棵查询树, 从叶子端开始执行, 最后合并到顶部, 产生一个唯一的结果.
默认情况下, select sname from student and SC where student.sno = SC.sno and SC.sno = '2';就是这么构建成查询树的.

2

3

四. 物理优化

1. 基于经验规则的优化

对于小的表, 直接全表扫描, 即使列上有索引.
对于大的表, 如果是选择条件涉及主键, 那么使用主键索引(MySQL等主流关系数据库都会对主键建立索引);
如果不是涉及主键, 那么如果是等值查询, 列上有索引, 就使用索引; 如果非等值查询, 而是范围值查询, 那么范围<=10%用索引, 范围比较大的, 直接全表扫描.
And 和 OR: AND连接的, 优先考虑使用索引; OR连接的, 优先考虑使用顺序扫描, 毕竟OR可能性非常多.

连接操作: 如果两个表都按照连接属性排序, 用sort-merge算法, 如果其中一个表在连接属性上有索引,采用索引连接算法; 如果啥都没有, 对小的表建立哈希表, 使用hash join方法; 或者使用基本的嵌套循环, 不过外层循环(i循环)使用小表, 这样能稍微减小代价.

2. 基于代价的优化

基于代价的优化需要依赖数据库表的各种"情报", 来计算出不同方案的代价, 从中选择最优的.
这些信息(meta info)包括:

1. 对每个表来说:
   表的元组行数 N,
   元组的长度, 即列的维度数目 P,
   表占用的block数目 B,
   表占用的溢出块的块数 BO,

2. 对表中的每个列,
   该列的不同值的个数 k
   列的最大值, 最小值max, min
   列上有什么类型的索引 index: 按照实现方式有B+, Hash, Cluster / 按照类型来说有普通索引, 唯一索引, 主键索引, 聚集索引
   列上的数值分布情况 (直方图)

那么对于不同情况, 我们有如下的代价估算:

1. 全表扫描 cost = B

2. 有索引的扫描
   如果选择条件是key = value, 能适用唯一索引: L + 1
   如果选择条件是attr = value, 能使用普通索引: L + S (可能有S个元组满足)
   如果条件是范围类的, 比如>, <, between A and B, 那么基本上就是接近全表扫描B;

3. 连接算法的代价
   如果用嵌套循环: 读入Capacity-1块B[a], 遍历连接b表所有B[b], 再换下一批B[a], 直到a表结束. 所以, cost = B[a] + ( B[a]/(C-1) ) • B[b] = a表IO次数 + b表IO次数, 假如要生成中间文件的话, 那么还得加上存下所有连接好的元组的磁盘IO开销.

如果用sort-merge: cost = B[a] + B[b], 如果要把中间结果写入外存, 那么还要加上存下所有连接好的元组的磁盘IO开销, 这个开销和上面嵌套循环的是一样的.
假如表本身没有排序, 那么排序的代价是B[a]logB[a] + B[b]logB[b]

参考资料

1. 数据库系统概论（高级篇）
2. 脚本之家: SQL语句的各个关键字的解析过程详细总结