优化器概念

优化器是数据库中用于把关系表达式转换成执行打算的外围组件，很大水平上决定了一个零碎的性能

优化器会蕴含一系列优化规定，这些优化规定能够对关系表达式进行等价转换，从而生成执行打算

优化规定常见逻辑算子

  • DataSource：数据源，也就是咱们SQL语句中的表，select name from table1中的table1
  • Selection：抉择，Where 条件，如select name from table1 where id = 1中的where后的过滤条件
  • Projection：投影，指搜寻抉择的列，如select name from table1 where id = 1中的列name
  • Join：连贯，如select * from table1 table2 where table1.name=table2.name就是把两个表做Join，连贯条件是最简略的等值连贯，当然还有其余咱们熟知的inner join,left join,right join等等
  • Sort：排序，如select * from table1 order by id外面的order by，无序的数据通过这个算子解决后，输入有序的数据
  • Aggregation：分组，如select sum(score) from table1 group by name中的group by，依照某些列进行分组，分组后能够进行一些聚合操作，比方Max、Min、Sum、Count、Average等等
  • Apply：子查问，如select * from (select id，name from table1) as t中的(select id,name from table1) as t，能够进行嵌套查问

优化规定-谓词下推

将外层查问块where子句中的谓词移入所蕴含的较低层次的查问块，从而可能提前进行数据过滤以及更好的应用索引

举例

比方对于表t1（100条数据），t2（100条数据），对于查问语句select * from t1,t2 where t1.a > 3 and t2.b >5

执行

  • 间接执行：执行时候是把t1和t2两个表做笛卡尔积，须要解决10000条数据，而后再依据条件进行过滤
  • 进行谓词下推：比方t1.a > 3的数据有10条，t2.b > 5的有5条，先进行过滤咱们所须要解决的数据条数则只有50条了，这就是尽量把过滤条件往下推到子节点上，就能够防止拜访很多数据，从而达到优化的成果

对于算子的谓词下推

  • DataSource算子，间接将过滤条件推给各个DataSource算子即可
  • 对于Join算子，则会首先进行简化，将外连贯转化为内连贯，收集连贯条件，辨别出哪些来自于Join的左节点哪些来自于Join的右节点，别离像左右节点进行下推

留神点

不能下推Limit，因为先进行Limit n再做Selection操作和先做Selection操作再Limit n失去的后果是不一样的

优化规定-列裁剪

对于没用到的列，则没有必要读取它们的数据去节约无谓的IO

举例

比方咱们有一张表table1，它含有四列数据a,b,c,d

当咱们执行查问select a from table1 where c >10时，table1中只有a,c两列被用到了

  • Selection算子用到c列
  • Projection算子用到a列

那么DataSource读取数据时，b，d两列则不须要读取，能够裁剪掉

总结

列裁剪的算法就是自顶向下的把算子过一遍，某个节点须要用到的列就等于它本人须要用到的列加上它的父节点所须要用到的列，这样失去整个SQL语句所波及到的列，从而再读取数据时只读取须要的列即可

优化规定-常量折叠

在编译优化时，多个变量进行计算时，而且可能间接计算出后果，那么变量将由常量间接替换

举例

比方select * from table1 where a > 3*5会转换为select * from table1 where a > 15

优化规定-常量流传

常量流传，在编译优化时，将可能计算出后果的变量替换为常量

实现逻辑

依赖一种叫做达到定值（reaching definition）的前向数据流剖析（forward data-flow analysis），要确定某个定值能被流传到哪些应用点，或者反过来说，某个应用点上应该采纳哪个版本的定值，如果在某个应用点上发现应该应用的定值是一个常量的话，就能够在此处做诸如常量折叠之类的常量优化了

举例

  • select * from table1 where a > 5 and a < 4

    一看就能看进去，不存在a > 5 && a < 4的值，然而未经优化的SQL会进行全表扫描查问a > 5和a < 4，这个时候就须要sql优化语句，从而打消无用的节点，判断是否存在后果

  • select * from table1 where a = b and b = 3

    能够优化为select * from table1 where a = 3 and b = 3

优化规定-投影打消

投影打消是把不必要的Projection给打消掉

如果Projection算子须要投影的列跟子节点的输入列一样，那么这个投影就是一个废操作，能够被打消掉

举例

  • select a,b from table1 如果再表table1中刚好只有a，b两列，也就是DataSource的输入和Projection须要投影的列一样，那么这时候就没必要在TableScan之后再做一次Projection操作了
  • select a from (select a,b,c from table2) 这条语句外面有两个Projection，别离是最上层的Projection(a)和它的子节点Projection(a,b,c)那么Projection(a,b,c)这个节点就是废操作，能够被打消掉如果Projection的子节点还是Projection的话，那么子节点的Projection就没有意义了，能够干掉
  • Aggregation在某种意义上也属于投影操作，因为从这个节点进去的都是列的概念，比方Max(a)、Min(b)等，因而在Aggregation->Projection的过程中，这个Projection也是能够被打消掉的

优化规定-最大最小打消

最大最小打消严格上说不是规范逻辑优化外面须要做的事件

举例

  • 最小打消：select min(a) from table1生成的逻辑执行打算是一个 TableScan 下面接一个 Aggregation，也就是说这是一个全表扫描的操作

    能够转换为select a from table1 order by a desc limit 1生成的逻辑执行打算是TableScan + Sort + Limit，在某些状况，比方a是主键或者是存在索引，数据自身是有序的， Sort 就能够打消，最终变成 TableScan 或者 IndexLookUp 加 Limit，这样子就不须要全表扫了，读到第一条数据就失去后果

  • 最大打消select max(id) from table1 优化为select max(id) from (select id from table1 order by id desc limit 1 where id is not null) t
  • 最小打消: select min(id) from table1优化为select min(id) from (select id from table1 order by id limit 1 where id is not null) table1

查问优化器分类

基于规定的优化器(Rule-Based Optimizer，RBO)

依据优化规定对关系表达式进行转换，一个关系表达式通过优化规定后会变成另外一个关系表达式，同时原有表达式会被裁剪掉，通过一系列转换后生成最终的执行打算

RBO中蕴含了一套有着严格程序的优化规定，同样一条SQL，无论读取的表中数据是怎么样的，最初生成的执行打算都是一样的

在RBO中SQL写法的不同很有可能影响最终的执行打算，从而影响脚本性能

执行过程

  1. Transformation

    遍历关系表达式，只有模式可能满足特定优化规定就进行转换，生成了一个逻辑执行打算，但这只是逻辑上可行

  2. Build Physical Plan

    将逻辑执行打算build成物理执行打算，即决定各个Operator的具体实现，如Join算子的具体实现抉择

基于代价的优化器(Cost-Based Optimizer，CBO)

依据优化规定对关系表达式进行转换，一个关系表达式通过优化规定后会生成另外一个关系表达式，同时原有表达式也会保留，通过一系列转换后会生成多个执行打算，而后CBO会依据统计信息和代价模型(Cost Model)计算每个执行打算的Cost，从中筛选Cost最小的执行打算

CBO中有两个依赖：统计信息和代价模型，统计信息的精确与否、代价模型的正当与否都会影响CBO抉择最优打算

执行过程

  1. Exploration
    依据优化规定进行等价转换，生成等价关系表达式，此时原有关系表达式会被保留
  2. Build Physical Plan
    决定各个Operator的具体实现
  3. Find Best Plan
    依据统计信息计算各个执行打算的Cost，抉择Cost最小的执行打算

CBO优于RBO的起因

RBO是一种只认规定，对数据不敏感的板滞的优化器，而在理论过程中，数据往往是有变动的，通过RBO生成的执行打算很有可能不是最优的

目前各大数据库和大数据计算引擎都偏向于应用CBO，例如Oracle、Hive、Spark、Flink等等

浏览参考

SQL优化器原理——查问优化器综述

SQL优化之谓词下推和常量优化

SQL优化器执行过程之逻辑算子