数据库内幕：查询优化技术

对于一条SQL，数据库会对其进行优化，找到最小代价的执行路径来运行。

整条优化的中心思想只需要把握以下一点：

• 尽可能早的把数据过滤到一个更低的数量级

主要的优化手段

查询重用技术

• 查询结果重用
• 查询计划重用

查询重写规则

对sql进行等价转换

• 语法级
• 代数级
• 语义级
• 物理级

主要用到的技术思路：

• 视图重写
• 把嵌套子查询、外连接、嵌套连接转变为多表连接
• 谓词转换
• 简化where、having、on条件

常见的手段：

• 选择操作：通过把选择下推（先执行），得到一个更小的数据集，再进行其他操作

• 投影操作：通过把投影下推，得到一个更小列数的数据集，再进行其他操作

• 连接操作：再多表连接的时候，以何种方式连接会更优，ABC还是BCA

• 索引优化

• 代价估算

• 子查询优化

  默认：父查询种的每一行，都执行一次子查询

  • 独立执行子查询，对于没有依赖父查询的子查询
  • 子查询条件外提，在父查询中进行条件下推
  • 子查询合并：对于类似的子查询可以合并成一个子查询
  • 子查询展开，变成与父查询并联，把查询转为多表连接
  • 聚集函数上推，并子查询展开

  对in关键字的优化：

  通过Exists 加子查询的方式

  优化的原理是子查询转变为连接条件关联父查询，为Hash半连接。如果对in不做优化，则父查询的结果有多少条，就会执行多少次子查询

  优化后，子查询子需要查询一次，并通过hash与父查询进行关联，加快了查询的速度

• 视图重写：视图有可能是多表关联的，但有些条件会和投影只对某一个表感兴趣，此时可以对视图进行重写，把多表查询简化成单表查询

• 谓词重写：

  通过重写，可以更好的使用索引

  • name like 'Abc%' =? name >= 'Abc' && name <'Abd'
  • no between 10 and 20 => no >=10 && no <= 20
  • age in ( 8 10) => age =8 or age = 10
  • or 重写： (sex = 'f' and sno > 15) or age>18 => sex='f' and sno>15 union age>18
  • 条件简化：常量替换

• 外连接消除

• 嵌套表消除：转变为多表关联，减少子表扫描次数

查询算法优化技术

• 单表结点

  考虑一次查询的IO尽可能低，来选择走索引还是直接走遍历

• 两表结点

  考虑表连接的代价，判断通过哪种方式的连接会更少占内存，会更快的得到最终结果。

  连接时是使用hash连接还是归并连接还是嵌套连接

• 多表中间结点

  AB先连接还是BC先连接

优化的手段：

• 基于规则优化

  通过经验，归类出一些常规的手段，进行优化

• 基于代价优化

  对数据进行动态分析，评估出一个较优或者最优的路径，进行查询

多表连接的优化算法有：

• SYSTEM-R：穷举所有，得到最优解
• 启发式搜索算法：基于规则，得到评估函数，进行启发式搜索
• 贪心算法：以当前情况判断哪条路径最优
• 动态规划
• 遗传算法：通过随机模拟进化，得到较优解

并行查询优化技术

通过对SQL的计划进行并行拆分，在多资源情况下，进行并行运行各个部分，更快的得到终解

分布式查询优化技术

在多台物理机上跑SQL，代价=IO代价+CPU代价+通讯代价

优化又分为逻辑优化和物理优化

• 逻辑优化：通过对SQL进行关系代数变换得到一个更有的解
• 物理优化：通过对数据的读取分析、表的连接方式对查询进行优化

物理优化

它解决的问题：

• 单表查询中，挑选怎样的扫描最优
• 两表连接时，如果连接最优
• 多表连接时，哪种连接顺序最优

代价函数

总代价 = IO 代价 + CPU 代价