ch58 查询处理

查询处理步骤

大部分情况下，应用的业务逻辑确定，那么相关的flower语句是确定的
image.png
执行重复的flower语句，可以直接使用查询执行计划。再次执行，就不需要优化了，直接使用
执行的次数越多，那么所带来的收益也就越大。
如果执行某些不常用的语句，

查询分析

image.png

查询检查

查询优化

image.png
基于规则的优化器更像是一个经验丰富熟知各条路段的老司机，大部分情况可以根据自己的经验来判断走哪条路可以更快的到达目的地，而基于代价的优化更像手机里面的地图，它可以选择出许多不同的路径根据实时的路况信息综合考虑路程长度，交通状况来挑出最优的路径。

查询执行

image.png

选择操作的实现

image.png

全表扫描算法

image.png

索引扫描算法

image.png

image.png

image.png

连接操作的实现

连接操作是查询处理中最耗时的操作之一

嵌套循环算法

image.png

排序-合并算法

image.png

  1. 排序阶段本身需要开销
  2. 排序的结果需要重新写回，无法存储在内存中
  3. 规模越大，收益越大

image.png

索引连接算法

image.png

Hash Join算法

image.png

ch59 查询优化

image.png
物理统计信息是归属在内模式中的

查询优化的实例

image.png

方案A

image.png

image.png

方案B

笛卡尔积上做特定选择就可以看做是连接
image.png

方案C

image.png

拥有索引的实例

image.png

优化实例

image.png

ch60 代数优化

先投影，后选择
同时进行选择（判断是否需要留下）和投影
类比：先发可乐，后发汉堡和同时发可乐、汉堡

典型的启发式规则

不需要找到每一个等价表达式，而是需要尽可能找到最优解

  1. 选择运算
    1. 应尽可能先做在优化策略中这是最重要、最基本的一条。
  2. 把投影运算和选择运算同时进行
    1. 如有若干投影和选择运算，并且它们都对同一个关系操作，则可以在扫描此关系的同时完成所有的这些运算以避免重复扫描关系。
  3. 把投影同其前或其后的双目运算结合起来
    1. 没有必要为了去掉某些字段而扫描一遍关系。
  4. 把某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算
    1. 连接特别是等值连接运算要比同样关系上的笛卡尔积省很多时间。
  5. 找出公共子表达式
    1. 如果这种重复出现的子表达式的结果不是很大的关系，并且从外存中读入这个关系比计算该子表达式的时间少得多，则先计算一次公共子表达式并把结果写入中间文件是合算的。
    2. 当查询的是视图时，定义视图的表达式就是公共子表达式的情况。视图产生的结果集是固定的？

大量的关系型数据库不支持笛卡尔积，效率低

启发式优化1

image.png
选择往叶节点跑

启发式优化2

image.png

启发式优化3

image.png

例子

image.png

image.png

image.png

image.png

image.png

image.png

ch61 物理优化

  • 代数优化改变查询语句中操作的次序和组合，不涉及底层的存取路径
  • 对于一个查询语句有许多存取方案，它们的执行效率不同， 仅仅进行代数优化是不够的
  • 物理优化就是要选择高效合理的操作算法或存取路径，求得优化的查询计划

物理优化方法

  • 基于规则的启发式优化
    • 启发式规则是指那些在大多数情况下都适用，但不是在每种情况下都是最好的规则。
  • 基于代价估算的优化
    • 优化器估算不同执行策略的代价，并选出具有最小代价的执行计划。
  • 两者结合的优化方法：
    • 常常先使用启发式规则，选取若干较优的候选方案，减少代价估算的工作量
    • 然后分别计算这些候选方案的执行代价，较快地选出最终的优化方案

启发式规则

选择操作的启发式规则

image.png
求并使用索引比较麻烦，得到的是超集

连接操作的启发式规则

image.png

基于代价的优化

统计信息

image.png

代价估算

image.png

image.png