简单聊聊TiDB中sql优化的一个规则---左连接消除(Left Out Join Elimination)
我们看看 TiDB 一段代码的实现 --- 左外连接(Left Out Join)的消除;
select 的优化一般是这样的过程:
在逻辑执行计划的优化阶段, 会有很多关系代数的规则, 需要将逻辑执行计划(LogicalPlan)树应用到各个规则中, 尝试进行优化改写;
我们看看其中的一条优化规则: outerJoinEliminator
TiDB作为优秀的开源项目, 代码的注释也非常优秀, 里面提到了满足这些条件的 Left Outer Join 可以消除右表;
// tryToEliminateOuterJoin will eliminate outer join plan base on the following rules
// 1. outer join elimination: For example left outer join, if the parent only use the
// columns from left table and the join key of right table(the inner table) is a unique
// key of the right table. the left outer join can be eliminated.
// 2. outer join elimination with duplicate agnostic aggregate functions: For example left outer join.
// If the parent only use the columns from left table with 'distinct' label. The left outer join can
// be eliminated.
我们这里只讨论第一种情况, 第二种情况请您自行查看源码;
我们构造满足第一种情况的查询:
左表:
t1(
id int primary key not null auto_increment,
a int,
b int
);
右表:
t2(
id int primary key not null auto_increment,
a int,
b int
);
查询语句:
select t1.id, t1.a from t1 left join t2 on t1.id = t2.id;
我们看看优化规则之前的逻辑执行计划:
这个执行计划是这样的:
顶层的算子是投影(Projection)操作, 取 t1.id 和 t1.a 这两列;
接下来是 连接(Join) 操作, 类型是: LeftOuterJoin;
接下来左边是 OuterPlan, 左表; 右边是 InnerPlan, 右表;
左边的算子是扫 t1 的数据, 右边的算子是扫 t2 表的数据;
底层的算子将数据返回给上层的算子, 来完成计划的执行;
注, 这种数据自底向上的流动方式有点像火山喷发, 所以这种执行模型叫做火山模型(Volcano);
主要代码逻辑在这里:
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);
不同的数据库的物理优化规则不一定是一样的, 这个可能根据数据和索引的存放特点来进行针对性的处理;
最新文章
- Script Component 引用package variable
- dotNet开发游戏微端
- 《JavaScript基础教程》
- unity3d 扩展NGUI Tweener —— TweenTime
- linux定时执行任务
- Javascript中new Date的坑
- lftp
- zabbix 编译
- ArcEngine颜色可视化
- USACO Section 5.1 Fencing the Cows(凸包)
- angular学习(二):Controller定义总结
- 质量体系 CMMI
- vim编辑器的使用技巧
- Lua模式匹配
- ASP.NET基础知识汇总之WebConfig各节点介绍
- wordpress安装后访问博客只显示文字的解决办法
- Windows 2008开启远程桌面连接
- linux环境下(非UI操作)所有软件的安装与卸载总结
- LeetCode算法题5----Longest Palindromic Substring
- gmssl
热门文章
- TypeScript 高级类型 类(class)
- ant 节点和属性
- 【MIT 6.824 】分布式系统 课程笔记(一)
- SQLSERVER远程链接Oracle数据库
- docker 宿主机与容器直接文件移动命令
- 怎样让ssh连接保持连接, 而不会因为没有操作而中断
- 表单送件前的Check(二) (未完)
- VS2017 CMD多出 “进程 6420)已退出,返回代码为: 0”的内容
- 【实战】Apache shiro<;=1.2.4 getshell
- Python——getpass(密码不显示)