《数据库查询优化器的艺术》第一章学习笔记

数据库管理系统

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

查询优化的目标

使查询优化引擎生成一个执行策略的过程,尽量使查询的总开销(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代价 + 通信代价