简单聊聊TiDB中sql优化的一个规则---左连接消除(Left Out Join Elimination)

主要代码逻辑在这里:

　　outerJoinEliminator::doOptimize

　　　　这是一个递归的操作, 不断的获取 parentCols, 并对 LeftOuterJoin 或者 RightOuterJoin 尝试进行消除;

　　　　如果是LeftOuterJoin , 尝试消除右表, 如果是RightOuterJoin, 尝试消除左表;

因为我们这里只有 Projection算子 和 LeftOuterJoin算子, 所以代码调用基本是这样的:

　　* 获取Projection的列

　　* 对下面的LeftOuterJoin进行判断

　　　　* 获取左表的列: outerPlan.Schema().Columns

　　　　* 判断上层 Projection 用到的列是否全部来自左表: o.isColsAllFromOuterTable(parentCols, outerUniqueIDs)

　　　　* 获取 Join 连接的列: innerJoinKeys := o.extractInnerJoinKeys(p, innerChildIdx); 这即是右表的 t2.id

　　　　* 判断连接的列是否被包含在右表的主键: o.isInnerJoinKeysContainUniqueKey(innerPlan, innerJoinKeys)

　　　　* 满足条件, 将 LeftOutJoin 替换掉;

我们展示一下这个转换:

上图中灰色的执行计划会被消除掉;

变成了下面的执行计划:

最终, 上面给出的sql 的例子等价于下面的语句:

　　select t1.id, t1.a from t1;

有兴趣的读者可以看看其他的满足条件的左外连接消除的逻辑, 这里就不讲了;

逻辑优化的过程一般被叫做RBO(rule based optimization);

　　逻辑规则的优化是基于关系代数的等价推导和证明;

　　大部分数据库(例如mysql, Oracle, SQLServer)的逻辑优化规则都类似, 可以互相参考; 

物理优化的过程一般被叫做CBO(cost based optimization);

　　不同的数据库的物理优化规则不一定是一样的, 这个可能根据数据和索引的存放特点来进行针对性的处理;

简单聊聊TiDB中sql优化的一个规则---左连接消除(Left Out Join Elimination)

标签：com   style   logic   nbsp   only   阶段   根据   int   读者