-
查询优化技术
(1) 代数优化
(2) 基于存储路径的优化
(3) 基于代价估算的优化
整体过程：
将查询转换成语法树；
根据关系的等价变化规则对语法树进行代数优化；
选择底层的操作算法，对于语法树中的每个操作，根据存储路径、数据存储分布、存储数据的聚簇等信息选择具体的执行算法；
生成查询计划，查询计划由一系列内部操作组成，这些内部操作按照一定的次序构成不同的执行方案，估算每个执行方案的代价，选择最小的一个。
-
代数优化策略
(1) 基本原则
减少查询处理的中间结果的大小
(2) 先执行投影、选择等操作，后执行联接、笛卡尔积等操作
(3) 先做小关系之间的联接，后做与大关系的联接
(4) 一般系统都采用基于规则的启发式查询优化方法
一般的规则包括：
1° 尽可能早的进行选择操作
2° 投影操作和选择操作尽量同时进行，减少扫描关系的次数
3° 将投影和其前或其后的联接操作同时进行，避免因为去掉某些属性而重复扫描
4° 将某些联接操作同在它前面的笛卡尔积结合起来，合并成为一个联接操作(特别是等值连接的情况)
5° 存储公共子表达式(此时要考虑子表达式结果集的大小、从外存中读入结果集的时间)
(5) 关系代数表达式的查询优化是由DBMS的DML编译器自动完成的
(6) 代数优化只改变查询语句中操作的次序和组合，不涉及底层的存取路径
-
基于存储路径的优化
(1) 每种操作有多种实现算法，具体选择哪种算法，要根据底层的存储路径的方式
(2) 选择操作的启发式规则
1° 小的关系一律顺序扫描，即便选择的列上有索引
2° 如果选择条件是 <主键=值>，则查询结果最多是一个元组（主键的唯一性），此时使用主键索引（一般的RDBMS会自动创建主键索引，例如MYSQL）
3° 如果选择条件是 <非主属性=值>，并且选择列上有索引。若估算查询结果元组数目少，则使用索引；若估算查询结果元组数目多，则使用顺序扫描
4° 如果选择条件是非等值查询，同3°
5° 对于AND合取条件，如果有涉及这些属性的组合索引，使用组合索引扫描；如果某些属性上有索引，则对其进行索引扫描后验证；没有任何索引，使用顺序扫描
6° 对于OR析取条件，只要任意一个条件没有索引，就只能用顺序扫描的方式
7° 如果关系按照条件中的属性进行排序且为关于该属性的等值查询，在使用顺序扫描的地方可以考虑二分查找
(3) 连接操作的启发式规则
1° 如果两个表都按照连接属性排序，则使用排序合并
2° 如果一个表在连接属性上有索引，使用索引连接
3° 如果1°,2°都不满足，其中一个表较小，则使用散列连接
4° 嵌套循环时，外循环使用记录数少的表
-
基于代价估算的因素
(1) 访问存储器的代价
(2) 生成中间文件的存储代价
(3) 计算代价：搜索、排序、合并、计算等的代价
(4) 内存使用代价：查询执行需要的内存缓冲区数目
(5) 通信代价：数据在不同数据库结点中传送的代价
-
为了估算代价，DBMS会在数据字典中存储查询优化器所需的各种统计信息
例如：元组总数、元组占用的块数、平均元组长度、块因子（一个块中能够存放的元组数量）、连接选择性（？？？）、索引的层数、索引的选择基数、索引的叶结点数
具体估算代价的计算 P111
-
解释执行的系统一般包括代数优化 + 基于规则的启发式存储路径优化，全面的优化会延长系统响应时间，所以只能做部分优化；
编译执行的系统查询优化和查询执行分开，因此可以使用以上的全部优化方法进行比较精细复杂的优化。
chapter05_查询处理和查询优化_2_关系数据库系统的查询优化方式
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 一、MySQL架构与历史 A.并发控制 1.共享锁（shared lock，读锁）：共享的，相互不阻塞的。 2.排...
- 前面的章节我们介绍了如何设计最优的库表结构、 如何建立最好的索引， 这些对于高性能来说是必不可少的。 但这些还不够...
- 查询处理的过程(1) 查询分析检查语法错误(2) 查询检查语义检查、用户权限检查、完整性约束检查(3) 建立查询的...
