Greenplum 查询优化器

发表评论
746 views

Greenplum 查询优化器

Greenplum 查询优化器

Greenplum 查询优化器介绍

对于给定的查询语句，找到“代价”最小的查询计划

查询计划介绍

一个查询计划就是由计划节点组成的树
每个计划节点代表一个特定类型的处理操作，计划节点中包含了执行器执行所需的全部信息
在执行时，计划节点产生输出元组
一般来说，扫描节点从数据表中获取输入元组
大部分其他节点从它们的子计划节点中获取输入元组

计划节点的类型

  • 扫描节点
    • 顺序扫描，索引扫描，位图扫描
  • 连接节点
    • Nestloop, hash, merge
  • 非SPJ节点
    • Sort, aggregate, set operation(UNION etc)

Greenplum 查询优化的具体处理过程

  • 查询树的预处理
    • 尽可能的简化查询树；收集有用信息
  • 扫描/连接优化
    • 为查询语句中扫描和连接部分做计划
  • 扫描/连接之外的优化
    • 为查询语句中扫描和连接之外的部分做计划
  • 计划树的后处理
    • 把优化结果转换成执行器可以执行的形式

查询树的预处理（前期）

  • 简化常量表达式

    • 输入参数包含NULL
    • 输入参数全部是常量
    • 简化布尔表达式
    • 简化case when

  • 内联简单的SQL函数

  • 提升IN，EXISTS类型的子连接
  • 提升子查询
  • 消除外连接

提升子连接

子连接(SubLink) 是指出现在表达式中的子查询，通常在Where或者join/on子句中
SELECT FROM foo WHERE EXISTS(SELECT 1 FROM bar WHERE foo.a = bar.c)
=>
SELECT FROM foo SEMI JOIN bar ON foo.a = bar.c

提升子查询

子查询一般以范围表的方式存在，通常出现在FROM子句中
SELECT FROM foo JOIN (SELECT bar.c FROM bar JOIN baz on TRUE) AS sub on foo.a = sub.c
=>
SELECT FROM foo JOIN (bar JOIN baz on TRUE) ON foo.a = bar.c

为什么提升子查询

通过把子查询提升到父查询之中，就可以使子查询参与整个计划搜索空间，从而找到更好的执行计划
否则，我们不得不为自查线单独做计划，然后再为父查询做计划时把子查询当做是一个”黑盒子“

消除外连接

外连接的上层由“严格”的约束条件，且该约束条件限定了来自nullable side的某一变量为非NULL值，则外连接可以转换成内连接
SELECT ... FROM foo LEFT JOIN bar ON (...) WHERE bar.d = 42;
=>
SELECT ... FROM foo INNER JOIN bar ON (...) WHERE bar.d = 42;
外连接本身有“严格”的连接条件，且该连接条件引用了来自nullable side的某一变量，且该变量被上层的约束条件限定为NULL值，则外连接可以转转换成反半连接（Anti Join)
SELECT FROM foo LEFT JOIN bar ON foo.a = bar.c WHERE bar.c IS NULL;
=>
SELECT FROM foo ANTI JOIN bar on foo.a = bar.c;

查询树的预处理（后期）

  • 分发WHERE和JOIN/ON约束条件
  • 收集关于连接顺序限制的信息
  • 消除无用的连接

分发约束条件

  • 一般来说，我们期望可以尽可能的下推约束条件
  • 如果只有内连接，我们可以把一个约束条件下推到它的“自然语意”位置
  • 如果存在外连接，那么约束条件的下推可能会受到阻碍，从而无法下推到它的“自然语意”位置
  • 对于被外连接阻碍的约束条件，我们通过让它的“required_relids"包含进外连接所需要的所有基表，从而避免该约束条件被下推到外连接之下

被外连接阻碍的约束条件

如果外连接本身的连接条件引用了non-nullable side的表，那么该连接条件不能下推到外连接之下，否则我们可能会丢失一些null-extended元组
如果外连接上层的约束条件引用了nullable side的变量，那么该约束条件不能下推到外连接之下，否则可能会多出一个null-extended 元组

连接顺序限制

  • 外连接会在一定程度上限制连接顺序的交换
  • 非FULL-JOIN可以和一个外连接的左端(LHS)自由结合
  • 通常非FULL-JOIN 不可以和外连接的右端(RHS)结合 (A left join B on (Pab)) inner join C on (Pac) = (A innerjoin C on (Pac)) left join B on (Pab)
    (A left join B on (Pab)) inner join C on (Pbc) != A left join (B inner join C on (Pbc)) on (Pab)

消除无用连接

  • 必须是左连接，且内表是基表
  • 内表的列没有在该连接之上使用
  • 连接条件最多只可能匹配内表中的一个元组 explain select student.sid from student left join (select distinct sid as sid from enrolled) sub on student.sid = sub.sid;

扫描/连接优化

  • 主要处理查询语句中FROM和WHERE部分
  • 同时也会考虑ORDER BY信息

  • 由代价来驱动

  • 首先为基表确定扫描路径，估计扫描路径的代价和大小

  • 利用动态规划算法，搜索整个连接顺序空间，生成连接路径
  • 在搜索连接顺序空间时，需要考虑到由外连接带来的连接顺序的限制

动态规划

  • 为每一个基表生成扫描路径
  • 为所有可能的两个表的连接生成连接路径
  • 为所有可能的三个表的连接生成连接路径
  • 为所有可能的四个表的连接生成连接路径
  • ...
  • 直到所有基表都连接在了一起
  • n个表的连接，理论上有n!个不同的连接顺序
  • 遍历所有可能的连接顺序是不可行的
  • 我们使用一些启发式办法，减少搜索空间
    • 对于不存在连接条件的两个表，尽量不做连接
    • 把一个大的问题，分解成多个子问题

扫描/连接之外的优化

  • 处理GROUP BY， aggregation, window functions, DISTINCT
  • 处理集合操作，UNION/INTERSECT/EXCEPT
  • 如果ORDER BY需要，添加最后的SORT节点
  • 添加LockRows,Limit, ModifyTable节点

计划树的后处理

  • 把代价最小的路径转换成计划树
  • 调整计划树中的一些细节
    • 展平子查询的范围表
    • 把上层计划节点中的变量变成OUTER_VAR或是INNER_VAR的形式，来指向子计划的输出
    • 删除不必要的SubqueryScan， Append等节点