乐趣区

关于数据库:数据库优化器与算子优化

jiezi

优化器概念

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

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

优化规定常见逻辑算子

  • 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优化器执行过程之逻辑算子

退出移动版