SQL优化器庖丁解牛篇(四)

2018-04-01

这一次讲谓词下推。谓词下推是相当重要的一个优化。比如 select * from t1, t2 where t1.a > 3 and t2.b > 5 ,假设 t1 和 t2 都是 100 条数据。如果把 t1 和 t2 两个表做笛卡尔集了再过滤,我们要处理 10000 条数据,而如果先做过滤条件,那么数据量就会少很多。这就是谓词下推的作用,我们尽量把过滤条件下靠近叶子节点做,可以减少访问许多数据。

谓词下推实现的接口函数大概是这样子:

func (p *baseLogicalPlan) PredicatePushDown(predicates []expression.Expression) ([]expression.Expression, LogicalPlan)

函数会处理当前的算子 p,假设在 p 上层要添加 predicates 这些过滤条件。函数返回的下推之后,还剩下的条件,以及生成的新 plan。这个函数会把能推的尽量往下推,推不下去了剩下的,加一个 Selection 条件在当前节点上面,变在新的 plan。比如说现在有条件 a > 3 AND b = 5 AND c < d,其中 a > 3 和 b = 5 都推下去了,那剩下就接一个 c < d 的 Selection。

DataSource 算子很简单,会直接把过滤条件加入到 CopTask 里面。

我们看一下 Join 算子是如何做谓词下推的。

首先会做一个简化,将左外连接和右外连接转化为内连接。什么情况下外连接可以转内连接?

左向外连接的结果集包括左表的所有行,而不仅仅是连接列所匹配的行。如果左表的某行在右表中没有匹配行,则在结果集右边补 NULL。谓词下推时,外连接转换为内连接的规则:如果我们知道接下来的的谓词条件一定会把包含 NULL 的行全部都过滤掉,那么做外连接就没意义了,可以直接改写成内连接。

什么情况会过滤掉 NUll 呢?比如,某个谓词的表达式用 NULL 计算后会得到 false,比如说谓词里面用 OR 多个条件,其中有条件会过滤 NULL,又或者用 AND 条件连接,并且每个都是过滤 NULL 的。

用 OR 连接起来的条件这个说法比较 low,有个高大上的术语叫析取范式 DNF (disjunctive normal form)。对应的还有合取范式 CNF (conjunctive normal form)。反正如果看到代码里面写 DNFCondition 之类的,知道术语会好理解一些。

接下来,把所有条件全收集起来,然后区分哪些是 Join 的等值条件,哪些是 Join 需要用到的条件,哪些全部来自于左孩子,哪些全部来自于右孩子。

区分开来之后,对于内连接,可以把左条件,和右条件,分别向左右孩子下推。等值条件和其它条件保留在当前的 Join 算子中,剩下的返回,也就是在这个 Join 上面接一个 Selection 节点作为新的 Plan 返回。

谓词下推不能推过 MaxOneRow 和 Limit 节点。

先 Limit N 行,然后再做 Selection 操作,跟先做 Selection 操作,再 Limit N 行得到的结果是不一样的。比如数据是 1 到 100,Limit 10 就是从 1 到 10,再 Select 大于 5 的,一个得到的是 1 到 10,另一个得到的是 5 到 15。MaxOneRow 也是同理,跟 Limit 1 效果一样。

说一下构建 unique key 和 MaxOneRow 属性。这个不属于优化的步骤,但是优化过程需要用来这里的一些信息。

收集关于唯一索引的信息。我们知道某些列,是主键或者唯一索引,这种情况一列不会在多个相同的值。构建 unique key 就是要将这个信息,从叶子节点,传递到 LogicalPlan 树上的所有节点,让每个节点都知道这些属性。

对于 DataSource,对于主键列,和唯一索引列,值都具有唯一属性。注意处理 NULL,考虑列的 NotNull 标记,以及联合索引。

对于 Projection,它的孩子中的唯一索引信息,再到它投影表达式里面用到的那些。比如 a b c 列的值都具备唯一属性,投影其中的 b 列,则输入仍然具有值唯一的属性。

哪些节点会设置 MaxOneRow 信息?

  • 如果一个算子的孩子是 MaxOneRow 算子,那它就也带上 MaxOneRow 属性,而且会继续往上传递。
  • 如果 Limit 只有一列,它就可以设置 MaxOneRow 属性。
  • 如果是 Selection,并且过滤条件是 unique key 等于某个常量,或者 unique key 是某个关联列,那么它也具有 MaxOneRow 属性。
  • 对于 Join,如果它的左右孩子都是 MaxOneRow 属性,那 Join 出来仍然会有 MaxOneRow 属性。
sql