数据库管理系统

数据定义
数据操纵
数据库的运行管理
数据库的建立和维护等

查询优化的目标

使查询优化引擎生成一个执行策略的过程，尽量使查询的总开销（IO，CPU，网络传输等）达到最小。

查询优化技术（广义）

查询重用技术
查询重写规则
查询算法优化技术
并行查询优化技术
分布式查询优化技术
其他方面（如框架结构）的优化技术

查询优化技术（狭义）

查询重写规则
查询算法优化

代数优化（逻辑优化）

主要依据关系代数的等价变换做一些逻辑变换。查询重写规则属于逻辑优化。

非代数优化（物理优化）

主要根据数据读取，表连接方式，表连接顺序，排序等技术对查询进行优化。查询算法优化，属于物理优化。运用了基于代价估算的多表连接算法求解最小花费的技术。

数据库调优

目标是使数据库有更高的吞吐量以及更短的响应时间。它是全局的。而查询优化技术是SQL层面的，局部的优化。

查询重用

指尽可能利用先前的执行结果，以达到节约查询计算全过程的时间并减少资源消耗的目的。
（1）查询结果的重用
在缓冲区分配一块缓冲块，存放该SQL语句文本和最后的结果集，当遇到同样的SQL输入时，可直接把结果返回。它节约了查询计划生成时间和查询执行过程的时间，减少了查询执行全过程的资源消耗。

（2）查询计划的重用
缓存一条查询语句的执行计划及其相应语法树结构。查询计划的重用技术减少了查询计划生成的时间和资源消耗

查询重写规则

它是一种等价转换。即对于任何相关模式的任意状态都会产生相同的结果。目标：
（1）将查询转换为等价的，效率更高的形式。
（2）尽量将查询重写为等价，简单且不受表顺序限制的形式，为物理查询优化阶段提供更多的选择。如：视图的重写，子查询的合并转换等。
重写的主要依据是关系代数。它是查询重写规则的理论支持。
它有3个角度，第4个是物理优化。
（1）语法级
（2）代数级
（3）语义级
（4）物理级：即基于代价估算模型，比较得出代价最小的，是从连接路径中选择代价最小的路径的过程。

主要思路：
1）将过程性查询转换为描述性的查询，如视图重写
2）将复杂的查询（嵌套子查询，外连接，嵌套连接）尽可能转换为多表连接查询
3）将效率低的谓词转换为等价的效率高的谓词（如等价谓词重写）
4）利用等式和不等式的性质，简化 WHERE， HAVING 和 ON 条件

核心是：等价转换，只有等价才能转换。

查询算法优化

查询优化即求解给定查询语句的高效执行计划的过程。

单表结点获取数据的方式有：
（1）直接通过IO获取
（2）通过索引获取数据
（3）通过索引定位数据的位置再经IO到数据块中获取数据
这是从物理存储到内存解析成逻辑字段的过程。

查询计划的策略：
（1）基于规则优化
（2）基于代价优化。
PG和MySQL采取了基于规则和代价估算的查询优化策略。

多表连接优化算法

SYSTEM-R算法
启发式搜索算法 
贪婪算法 
动态规划算法
遗传算法

并行查询优化

单机：找到查询的一个具有最小执行花费的执行计划
并行：寻找具有最小响应时间的查询执行计划

并行查询：
（1）操作内并行：将同一操作，如单表扫描操作，两表连接操作，排序操作等分解成多个独立的子操作，由不同的CPU同时执行。
（2）操作间并行：一条SQL查询语句可以分解成多个子操作，由多个CPU执行。

分布式查询优化

查询策略优化（主要是数据传输策略）和局部处理优化（传统的单结点数据库的查询优化技术）是查询优化的重点。

主要目标：
减少传输的次数和数据量

分布式代价估算模型
总代价 = IO代价 + CPU代价 + 通信代价