Tddl_Optimizer

所有sql中的expression都抽象为ISelectable对象，比如函数，select a from xxx , select (1+1)
所有条件表达式都抽象为IFunction对象，比如常量，二元比较操作符，函数等，select (1>0), select 1 , select count(*) from xxx
aggregate : 聚合函数，输入一批记录，只输出一条记录。比如count , max , min , avg , sum
scalar : 标量函数，输入一条记录就会输出一条记录。比如常见的substring，length , add 等
IFilter用于标示一些二元比较操作符号，比如 a > b , a < b， a is null , a is true等 (目前常量也是做为一种IFilter)
column/value : 左右操作列. operate: 操作符.
比如a > b，此时column = a , value = b. operate = '>'

抽象语法树

说明：

DMLNode ：标示常见的insert/update/delete/replace的相关操作
QueryTreeNode : 标示query操作.

query节点：

TableNode : 一张物理数据表上的query操作
KVIndexNode : 一张索引表上的query操作，任何一个TableNode都会转化为基于KVIndex的查询.
QueryNode : 一张子查询的记录上的query操作，可以理解为子查询
JoinNode : 两张表上的join query操作，包括inner join/left join/right join/outer join/cross join.
MergeNode : 多张相同表上的聚合查询，一般用于分库分表查询的结果聚合，tddl特有。注意：不是对应于sql中的union，目前不支持union操作

Sql例子

例子1：

SELECT T.ID , LENGTH(NAME) AS LEN FROM TABLE1 T  WHERE ID=1

对应的抽象语法树：(TableNode)

Query from TABLE1 as T
    whereFilter:TABLE1.ID = 1
    columns:[TABLE1.ID, LENGTH(NAME) as LEN]

例子2:

SELECT * FROM TABLE1 A JOIN TABLE2 B ON A.ID=B.ID WHERE A.NAME=1

对应的抽象语法树：(JoinNode)

Join
    joinFilter::[A.ID = B.ID]
    type:inner join
    whereFilter:A.NAME = 1
    columns:[A.ID, A.NAME, A.SCHOOL, B.ID, B.NAME, B.SCHOOL]
    strategy:NEST_LOOP_JOIN
    left:
        Query from TABLE1 as A
            columns:[TABLE1.ID, TABLE1.NAME, TABLE1.SCHOOL]
    right:
        Query from TABLE2 as B
            columns:[TABLE2.ID, TABLE2.NAME, TABLE2.SCHOOL]

例子3:

SELECT NAME FROM (SELECT * FROM TABLE1 A WHERE A.ID=1) B ORDER BY NAME LIMIT 10

对应的抽象语法树：(QueryNode)

SubQuery as B
    limitFrom:0
    limitTo:10
    orderBy:[OrderBy [columnName=B.NAME, direction=true]]
    columns:[B.NAME]
    from:
        Query from TABLE1 as B
            whereFilter:TABLE1.ID = 1
            isSubQuery:true
            columns:[TABLE1.ID, TABLE1.NAME, TABLE1.SCHOOL]

优化逻辑

核心关键词：pushdown(下推)

尽可能让请求在底下执行，比如数据过滤和排序下推到存储上执行，这样在上层做聚合和计算操作代价相对会小.

整个优化流程大致分为：

预处理优化
a. join关系
b. filter条件
下推优化
a. filter下推
b. order下推
c. 元数据下推
索引优化
a. 二级索引
b, 索引选择
c. filter拆分
join优化
a. join策略选择
b. 二级索引join优化
c. join顺序调整
shard计算(分库分表)
a. MergeNode构造
b. 节点下推
特殊场景

预处理优化

Join预处理

1. right join调整为left join

可以将左表做为驱动表，下推order请求，方便做跨库join.

2. 子查询转化为join

sql :

SELECT * FROM TABLE1 WHERE ID = (SELECT ID FROM TABLE2)

转化为：

SELECT TABLE1.* FROM TABLE1 INNER JOIN TABLE2 ON TABLE1.ID = TABLE2.ID

sql:

SELECT * FROM TABLE1 WHERE ID IN (SELECT ID FROM TABLE2)

转华为：

SELECT TABLE1.* FROM TABLE1 INNER JOIN TABLE2 ON TABLE1.ID = TABLE2.ID

Filter预处理

1. 函数提前计算

SELECT 1 + 1 , 优化为SELECT 2
SELECT 1 = 1 , 优化为SELECT 1
SELECT 0 = 1 , 优化为SELECT 0

2. 判断永真/永假式,短化路径

比如:

false or a = 1，优化为 a = 1
true or a = 1，优化为true
false and a =1 , 优化为EmptyResultFilterException异常
true and a = 1 , 优化为 a = 1
1 and a = 1，优化为a = 1 (非0的常量值代表true，0值代表为false)

3. 调整下1 = id的列信息，优化为id = 1

几种case:

1 < a，优化为 a > 1
1 <= a，优化为 a >= 1
1 > a，优化为 a < 1
1 >= a，优化为 a <= 1
其他情况，仅仅是交换下column/value的位置

4. 类型转化

几种case :

a = '1' , 如果a为bigint类型，会将'1'调整为Long.valueof(1)
a='2014-01-22 12:12:12'，如果a为Timestamp类型，会解析为时间类型

ps. 字段的类型信息，会通过加载数据库中的表结构进行获取，并转化为自己的模型：ColumnMeta中的DataType

4. 智能合并and/or的范围查询

几种case :

1 < A <= 10 AND 2 <= A < 11, 优化为 2 <= A <= 10
1 < A AND A < 0 , 优化为EmptyResultFilterException异常，(不可能有结果)
A > 1 OR A < 3，优化为true，永真式
A > 1 OR A > 3，优化为A > 1
A > 1 or A = 5，优化为A > 1

ps. 合并范围查询，可以减少规则计算的复杂度，尽可能优化为一个区间的范围查询.

下推优化

Filter下推

主要是将节点中的where条件尽可能提前到叶子节点，同时提取出joinFilter

主要处理的类型为：JoinNode/QueryNode

几个原则：

如果条件中包含||条件则暂不优化，下推时会导致语义不正确
如果条件中的column/value包含function，也不做下推 (比较麻烦，需要递归处理函数中的字段信息，同时检查是否符合下推条件，先简单处理)
如果条件中的column/value中的字段来自于子节点的函数查询，也不做下推
JoinNode如果是outter节点，则不能继续下推，条件传递也不可以传递到outter节点 (outter条件可以传递到非outter的节点)

几种case:

where条件尽可能提前到叶子节点，根据字段属于的表，下推到叶子节点的where条件中
sql :
```
tabl1.join(table2).query("table1.id>5 && table2.id<10 && table1.name = table2.name")
```
优化为：
```
table1.query("table1.id>5").join(table2.query("table2.id<10").on("table1.name = table2.name")
```
解释：将table1.id>5和table2.id<10下推到各自的叶子节点，将table1.name = table2.name抽取为join的链接条件.
join中的非字段列条件，比如on id = id and column = 1的join条件，会将column=1提前到叶子节点
sql:
```
tabl1.join(table2).on("table1.id>5&&table2.id<10")
```
优化为：
```
table1.query("table1.id>5").join(table2.query("table2.id<10"))
```
解释：将table1.id>5和table2.id<10下推到各自的叶子节点
join中的where条件进行条件推导到左/右的叶子节点上，在第1和第2步优化中同时处理
sql :
```
table.join(table2).on("table1.id = table2.id and table1.id>5 && table2.id<10")
```
优化为：
```
table1.query("table1.id>5 && table1.id<10").join(table2.query("table2.id>5 && table2.id<10"))
```
解释：table.id > 5通过 table1.id = table2.id条件，传递为table2.id > 5. table2.id < 10同理可传递为table1.id < 10.

Order下推

主要是将MergeNode/JoinNode/QueryNode中的order by条件下推，包括隐式的order by条件，比如将groupBy转化为orderBy.

需要orderby的条件：(按照优先级)

join列 (Join策略为SortMergeJoin时有效，其他Join策略不需要Join列排序)
distinct列
groupby列
orderby列 (不可调整顺序)

上述几个排序条件中，只有orderby不可调整顺序，其他的可以按照当前显示orderby中的列信息进行调整.

举个例子：

order by c1,c2 group by c3,c2,c1

可优化为：

order by c1,c2,c3 group by c1,c2,c3

几个case:

order by c1,c2 group by c3,c2,c1，优化为 order by c1,c2,c3 group by c1,c2,c3 (要点：group列调整顺序)
select distinct c2,c1,c3... order by c1,c2 , 优化为 order by c1,c2,c3 (要点：distinct列调整顺序)
a join b on a.c2 = b.c2 and a.c1 = b.c1 order by c1,c2, 优化为order by c1,c2 (要点：join列调整顺序)
select distinct c2,c1,c3... group by c2,c3 order by c1,c2 , 优化为 order by c2,c3,c1，再使用临时表解决order by c1,c2 (要点：按照优先级，先满足distinct/group的排序)
a join b on a.c2 = b.c2 and a.c1 = b.c1 and a.c3 = b.c3 group by c2,c3 order by c1,c2，优化为order by c2,c3,c1，再使用临时表解决order by c1,c2 (要点：按照优先级，先满足join/group的排序)
a join b on a.c1 = b.c1 group by c2 order by c3，优化为order by c1，再使用临时表解决order by c2，再使用临时表解决order by c3 (要点：按照优先级，先满足join/group/order的排序)

总结：前面介绍了如何优化join/distinct/groupby/orderby列的，尽可能使用少的排序次数完成结果计算，如果不能一次排序完成，就需要借助于临时表做二次排序.

-------

完成了当前节点的order优化后，需要将调整后的第一次order排序条件进行下推，下推需要遵守几条原则：

子节点存在limit，不可下推
子节点存在order by，强制下推覆盖(前提：条件1不能出现)
orderby是当前节点或者叶子节点的函数或者函数列，不可下推 (目前简化处理，后续会有调整)

几个case :

父节点：order by c1 ,c2 ,c3，子节点：order by c1, c2. ==> 子节点优化：order by c1,c2,c3
父节点：order by c2 ,c3，子节点：order by c1,c2 ==> 子节点优化：order by c2,c3
父节点：order by c2 ,c3，子节点：order by c1, c2 limit 10 ==> 子节点不做调整，条件1
父节点：order by c1, c2 ,c3，子节点: 无 ==> 子节点优化：order by c1,c2,c3
父节点：order by count(*) 子节点: 无 ==> 子节点不做调整，条件3

条件3限制的优化：(规划中)

orderby列是当前节点的函数，比如order by count(*)，不可下推
orderby列是当前节点的函数列，比如select length(name) as c ordey c ，如果是scalar函数，并且函数的参数为单表中的列，此情况可下推参数的order或者下推整个元数据
orderby列是叶子节点的函数列，可下推order.

元数据下推

主要是针对JoinNode/MergeNode中使用的order by/group by/having中的列或者函数等元数据信息，下推到叶子节点，然后上层节点可基于元数据，进行二次计算.

需要下推的元数据：

orderby列
groupby列
having条件
function列或者其所有参数
跨机join条件
部分不可下推到存储的where条件

几点注意：

function列需要根据不同存储进行区别对待，比如mysql可下推整个function函数列，如果是hbase，只能下推function中的参数
where条件中需要根据不同存储的支持程度进行下推，比如传统的kv查询引擎，只支持主键的条件，针对非主键的条件，需要下推列，然后由上层来计算非主键的条件
join条件中，如果不满足Join下推的条件，则需要下推join列，然后由上层进行join列的处理. (join列的函数目前不支持)

几个case：

sql : (JoinNode)

SELECT A.NAME FROM A JOIN B ON A.ID = B.ID ORDER BY B.NAME

下推结果：

A表：SELECT A.ID , A.NAME
B表：SELECT B.ID , B.NAME

sql: (MergeNode存在分库分表)

SELECT A.ID, LENGHT(NAME) FROM A WHERE A.NAME > 100 ORDER BY A.SCHOOL

下推结果：

A表：SELECT A.ID, A.NAME, A.SCHOOL

索引优化

二级索引

引入二级索引概念，主要解决两类应用场景：

分库分表后，不带分库键的其他字段的查询
KV存储引擎，不带主键的其他字段查询

tddl这里的二级索引概念和mysql/oracle数据库自带的二级索引不同，mysql数据库的二级索引信息和数据表算一个整体，而tddl这里的二级索引可以理解为另一张数据表。

一次查询请求，可能会是先查二级索引表，拿到主键后做再回主表进行查询.

举个例子：(tddl5中中支持定义二级索引表结构)

<table name="student">
       <columns>
                 <column name="id" type="long" />
                 <column name="name" type="string" />
                 <column name="school" type="string" />
		</columns>
        <primaryKey>id</primaryKey>
        <secondaryIndexes>
			<indexMeta name="second_index" type="btree">
                                  <keys>name</keys>
                                  <values>id</values>
			</indexMeta>
         </secondaryIndexes>
</table>

说明：这个配置文件中描述了一张student表，主键为id，同时存在一个二级索引为name -> id的关系.

索引选择

主要是存在tddl的二级索引时，可以根据filter条件选择一个合适的索引进行操作.

选择策略：

cost模型
经验模型

cost模型

需要收集数据库上表数据的统计信息，比如总的记录数，列的选择度等，目前tddl5暂未支持

经验模型

根据一些经验值，进行预估cost，得出结果. 可参考： http://db.apache.org/derby/docs/10.0/manuals/tuning/perf56.html#Selectivity+From+Hard-Wired+Assumptions

Filter拆分

tddl5认为所有的sql查询请求都可以通过二级索引转化为基于KV的处理模型，为支持所有通用的存储引擎而设计，所以衍生出了两类filter:

keyFilter (索引表上主键值的filter)
valueFilter (索引表上索引值对应value的filter)

基于keyFilter/valueFilter的模型和二级索引模型，针对索引的选择结果拆分原本where中的filter条件，可拆分为三类条件：

IndexQueryKeyFilter (如果有索引，就是索引上的keyFilter，如果没索引，就是主表上的KeyFilter)
IndexQueryValueFilter (在索引表上的ValueFilter)
ResultFilter (在主表上的ValueFilter)

tddl5认为所有的sql查询请求都可以转化为基于KV的处理模型，为支持所有通用的存储引擎而设计，所以衍生出了这几类的filter

举个例子来说明下这几类条件的区别：

假定存在一个数据表，存在三个列：ID , NAME , SCORE

同时存在两个索引：

ID -> 物理地址，主键索引
NAME -> ID ，二级索引

给定一个sql:

WHERE ID > 100 AND NAME = 'LJH' AND SCORE > 100;

1. 因为NAME=’LJH‘是一个等值索引，选择度比ID>100更好，所以选择NAME->ID的二级索引，此时　IndexQueryKeyFilter = (NAME = 'LJH')

2. 然后ID > 100可做为二级索引上的valueFilter (ID是做为NAME二级索引的value)，此时 IndexQueryValueFilter = (ID > 100)

3. SCORE因为不存在于NAME的二级索引中，所以需要会主表查询，此时 ResultFilter = (SCORE > 100)

最后优化结果就是: 二级索引表 AS A Join 主键表 AS B on A.id = B.id WHERE A.NAME = 'LJH' AND A.ID > 100 AND B.SCORE > 100

二级索引表：　

keyFilter = (NAME = 'LJH')
valueFilter = (ID > 100)

主键表：

keyFilter = (ID IN 来自于二级索引表的查询结果)
valueFilter = (SCORE > 100)

Join优化

Join策略选择

主要基于各种因素(比如索引选择，join列，left/right join, 子查询，数据量等)选择不同的Join策略，用于提升Join的效率.

传统数据库几种Join策略算法：

Nest Loop Join
Sort Merge Join
Hash Join

具体描述可参见：http://blog.csdn.net/panzhaobo775/article/details/7327896

目前tddl5基于分库分表的特点，实现了几种Join策略算法：

Block Loop Join
Index Loop Join
Sort Merge Join
Hash Join (后续规划中)

针对传统数据库的Nest Loop Join，tddl5演变为两种具体的Loop Join算法，下面具体介绍下Join策略的选择.

1. Block Loop Join

主要原理是：将右表提前执行得出结果，数据全部cache到内存中，实现内存物化表，然后遍历左表数据，与右表数据据(纯内存)进行join计算.

几点注意：

右表是子查询会强制选择该Join策略
只支持inner/left/right这几种join
右表无顺序性要求，Join的order顺序可下推至左表.

限制：右表返回的记录数要足够少，不然会出现内存溢出的情况. (后期需优化，数据换出到硬盘或者提前估算大小，选择其他Join策略)

2. Index Loop Join

主要原理是：循环遍历左表，缓存一定的记录后，根据join列构造右表的In查询，批量获取结果后完成Join计算.

几点注意：

只支持inner/left/right这几种join
右表无顺序性要求，Join的order顺序可下推至左表.

限制：右表需支持join列的in查询 (比如join列是右表的主键或者索引字段，如果是mysql等关系型数据库，即使非主键或者索引条件查询，也可以采用此Join策略)

3. Sort Merge Join

主要原理是：左/右表都按照join列的order顺序进行返回，然后在内存中进行归并排序

几点注意：

目前唯一支持outer join的实现，也就是outter join默认选择该join策略，同时也支持inner/left/right/outer这几种join
left/right outer join的outer表如果存在order by/group by等条件时，默认选择该join策略
其余情况，不选择该Join策略

限制：左/右表都有顺序性要求，必须下推join列的order排序.

4. Hash Join

目前暂不支持，后续完善.

----

总结：

mysql等关系型数据库，支持任何条件的sql查询，所以Index Loop Join需要右表需支持join列的in查询，对于mysql来说无限制. 所以目前针对右表是mysql库的，并且是非子查询，使用Index Loop Join替换Block Loop Join的实现.
目前Join策略选择，优先级为 Index Loop Join > Sort Merge Join > Block Loop Join

二级索引join优化

主要是解决基于数据表选择二级索引后，调整为左子树，右节点尽可能是简单的叶子节点.

优化策略：

递归左序遍历，从叶子节点开始调整.
当前节点为TableNode，索引选择中最终选择了二级索引，会将当前TableNode裂变为 [KvIndexNode Join KvIndexNode]，对应join条件即为主键列.
当前节点为JoinNode，如果右表也是个JoinNode (可推断此JoinNode一定为步骤2中裂变产生)，此时的节点状态可能为 A join (B join C) ，这样的join结构只能选择Block Loop Join，如果需要选择Index Loop Join，需要优化为： ( A join B ) join C.

示意图：

Join顺序选择

主要基于cost模型，计算各节点的join顺序，来优化join查询效率。比如表查询结果数据越小的表，需要提前进行join.

调整的策略：

主要针对inner join，(left/right/outer join不做调整，既然用户指定了outer表，就意味着选定了驱动表，所以不做调整，而且调整后比较难保证SQL语义)
优先调整子查询，然后子查询做为一个整体参与join调整 (子查询内部的inner join的表，需要和外部inner join表做隔离，不能放一起做递归枚举调整)

调整的算法：

收集可调整的节点，比如 A inner Join B inner Join (C left Join D)，可调整的节点即为 ( A , B , (C left join D)一个整体 )
收集所有节点之间的join条件
枚举可调整节点的排列组合，并且尝试重组join条件，如果join条件重组成功，则返回，否则跳过，继续获取下一组排列 (比如存在A inner join b，不代表A和(C left join D)有对应的join关系，不满足join关系的排列需要跳过)
针对步骤3返回的join排列，进行join策略选择，然后各自计算cost模型
排列组合全部枚举完成后，选出最小的cost对应的排列组合，即为最佳的Join顺序，返回

何时会开启Join顺序调整：

设置ChooseJoin为true，默认为false
隐式join，不存在join条件.
sql :
```
SELECT * FROM A , B , C WHERE A.ID = C.ID AND C.ID = B.ID 
```
如果按照正常的顺序构造了 (A inner join B) inner join C , 此时会出现 A inner join B不存在join条件，目前的策略就是通过join顺序调整来优化为 (A inner join C) inner join B
inner join右表存在order排序信息
sql :
```
SELECT * FROM A, B WHERE A.ID = B.ID ORDER BY B.ID
```
因为Block Loop Join / Index Loop Join，是不会下推右表的order排序，这样会导致出现一次临时排序，目前的策略就是跳过join顺序调整来优化为 (B inner Join A) order by B.ID

Shard计算(分库分表)

MergeNode构造

主要基于tddl-rule进行分库分表计算，将原本对一张逻辑表的操作，映射到物理上的对应的分库分表操作. 比如SELECT * FROM TABLE，如果TABLE分了16个表，那将会拆分为16个表的查询.

更多关于分库分表的规则计算请点击：Tddl_rule，这里不展开介绍.

整个构造流程是基于语法树进行递归遍历，主要是针对叶子节点进行处理，再递归处理过程中，优化节点下推(下一章将详细展开).

几点注意：

在shard计算过程中，会通过规则计算得出一个group名字，对应于物理上的一个数据存储，并记录到ASTNode.executeOn()中，(执行器会根据该结果到目标存储上执行并获取数据)
对于二级索引表和主表，分别都会通过规则进行计算，并构造各自的MergeNode. (也就是说，二级索引可以是一张表，或者是分库分表，或者是其他异构的kv存储来实现).
特殊子查询，比如WHERE ID > (SubQuery)，目前暂未支持，后续同样需要对其进行展开为Merge处理.

节点下推

主要是针对MergeNode的构造结果，尽可能进行下推优化，将原本的JoinNode / QueryNode进行下推，然后对结果进行聚合Merge.

针对节点下推，主要是针对带子节点的优化：QueryNode 和 JoinNode.

在介绍下推优化之前，需要先了解几个概念：

1. 节点是否存在聚合操作(比如出现limit/group by/count/max等)

例：一旦子节点是个MergeNode，并且存在limit的操作，一定需要将MergeNode数据计算完成后，才可以与右表进行join.

----

QueryNode下推优化：

如果节点不存在聚合操作，原本[Query -> Merge ->(KvIndex) * n个节点]的节点树，将优化为[Merge -> (Query -> KvIndex) * n个节点]
在优化中，会复制和kvindex相同数量Query节点，每个Query节点和对应的KvIndex建立关系，并设置Query节点的executeOn()为KvIndex的物理位置。
如果底册存储支持整个Query -> KvIndex的查询，可直接下推到存储上完成执行，同时多个Query->KvIndex的查询，可以采取并行策略，最后Merge即为一个简单的数据归并.
如果节点存在聚合操作，还是保持[Query -> Merge ->(KvIndex) * n个节点]的节点树，不做任何优化

----

JoinNode下推优化：

在正式介绍之前，首先了解下tddl5做的两个join优化：

全局表或称广播表.
ER分片策略.

全局表：可以理解为将一张小表的数据，在所有数据分库中都存在，每次对全局表的记录修改，都会反映到所有分库上。

方案：

同步. 对全局表的insert/update/delete/replace操作，全部构造为[Merge -> put * 所有分库]的操作，采用分布式事务保证数据同步提交.
异步. 对全局表的insert/update/delete/replace操作，只构造为对任意一个表的Put操作，然后采用数据库日志异步复制到所有其他分库分表.

ER分片策略：可以简单理解为相关表都按照同一个纬度进行数据切分，比如用户，商品，商品表中冗余一个用户ID，然后用户和山品都按照用户id这一个纬度进行切分。

优点：如果对用户和商品进行join查询，join条件为用户id时，不管是inner join/left join/right join/outer join，都可以用相同分库上的用户和商品做join来实现merge join merge的语义，结果是等价的.

缺点：如果进行join查询时，同时存在对二级索引表的依赖，此时可能会打破ER分片的相同分库分表的策略，此时需要做权衡。(查询所有分库分表+valueFilter vs 二级索引表 join 主表 ).

整个JoinNode下推优化第一步，就是判断是否满足ER分片(即相同的分库分表)，整个判断逻辑如下：

对语法树进行左序遍历，优先从Join节点左边叶子节点开始判断是满足ER分片(进入流程2)，然后再判断右叶子节点是否满足ER分片(进入流程2)
如果叶子还是JoinNode节点，继续走流程1，否则进入流程3
如果当前节点为QueryNode，进入流程4
如果当前节点为KvIndexQuery
a. 如果当前为全局表，返回true，回到上一层判断.
b. 提取当前的分库分表键，判断是否和当前父节点的JoinNode的Join条件是否属于被包含关系，如果不是，则返回false，并退出整个判断流程.

总结一下：

如果是全局表，直接认为满足ER分片
多层语法树，采用左序遍历，从叶子节点逐层判断是否满足ER分区 (整个JoinNode的下推优化是从叶子节点开始处理，所以如果叶子节点部分满足ER分区，在处理叶子节点时已经得到优化，上层可不需要考虑)

----

特殊case： (假定member和item满足ER分片，同时分库键就是m.id和t.id)

select * from memeber m left join item t on m.id = t.id where t.id = 1 (不可下推)
select * from memeber m left join item t on m.id = t.id where m.id = 1 (可下推)

看上这两个case都没啥问题，满足ER分片，可优化为[Merge -> Join * n]，但实际上是有问题，问题点就在于执行的物理数据库节点上.

case 1: 存在outter右表的t.id条件，那是否可计算出item表只需要在1个分表上进行查询，那对应的member表是否也只需要在1这个分片上做？ 答案是错误的，member表需要做所有分库分表的查询，然后再于item表做join. 也就是只能是 Merge Join Merge的情况，左右表的分区数不一致.

case 2: 存在左驱动表上有m.id条件，可以计算出member表只要在1个分表上进行查询，那对应的member表是否也只需要在1这个分片上做？答案是正确的，因为左驱动表的m.id=1的条件，可经过条件推导，生成t.id = 1的条件，所以最后会是一个可下推的join.

总结一下：

如果left / right join的outer表，存在分库条件，不可推导到驱动表，反过来驱动表的条件可以推导到outer表. 所以就有了case 1和2的不同结果.

----

整个MergeNode构造，节点下推示意图：

特殊场景优化

分库limit

采用的是业界常用的分库limit处理思路.

给定SQL ：

ORDER BY ID LIMIT 10,20

优化思路：

首先通过shard计算，尝试构造为MergeNode
a. 如果是KvIndexNode，则代表为可在单库单表上进行执行，此时limit不做任何优化，直接下推到存储上执行
b. 如果是MergeNode，进入步骤2
c. 如果是JoinNode，进入步骤3
d. 如果是QueryNode，进入步骤4
当前为MergeNode，MergeNode上设置LIMIT 10,20，遍历所有子节点，设置LIMIT 0,30
当前为JoinNode，JoinNode上设置LIMIT 10,20，不对子节点做处理, 直接在JoinNode上执行limit操作，不可下推.
当前为QueryNode，QueryNode上设置LIMIT 10,20，针对子节点是否处理，需要分情况 (目前简化处理，默认不做下推LIMIT操作)
a. QueryNode节点只是一个简单的SELECT * FROM (Subquery) LIMIT 10,20，不带其他任何条件，此情况可下推LIMIT
b. QueryNode节点存在order by /group by / distinct / where条件等，不可下推LIMIT 10，20

注意：MergeNode子节点的LIMIT计算是Start = 0, Number = 10+20 = 30.

因为MergeNode上需要的LIMIT 10,20的数据，可能全部来自于第一个子节点。

分库Avg

给定SQL ：

SELECT AVG(SCORE) FROM TABLE

优化思路：

首先通过shard计算，尝试构造为MergeNode
a. 如果是KvIndexNode，则代表为可在单库单表上进行执行，此时avg不做任何优化，直接下推到存储上执行
b. 如果是MergeNode，进入步骤2
c. 如果是JoinNode，进入步骤3
d. 如果是QueryNode，进入步骤4
当前为MergeNode，MergeNode上设置查询列为SUM(SCORE)/COUNT(SCORE) AS AVG(SCORE), 遍历所有子节点，每个子节点上设置查询列为 SUM(SCORE) ，COUNT(SCORE). 【需要使用reduce函数进行计算，map的计算由对应的子节点完成】
当前为JoinNode，JoinNode上设置查询列为AVG(SCORE), 不对左/右子节点做任何处理. 【直接使用map函数进行计算】
当前为QueryNode，JoinNode上设置查询列为AVG(SCORE)，不对子节点做任何处理【直接使用map函数进行计算】

注意： Merge节点上的AVG操作不能只是简单的对底下AVG结果的再次AVG计算，而是需要收集所有库的SUM(SCORE)和COUNT(SCORE)的数据，这样计算的AVG才是一个正确的值. 目前TDDL5中抽象了map/reduce方法来解决. map对应于子节点的数据局部计算，reduce对应于父节点在子节点的局部计算基础上再次进行计算，得出最终结果。

分库sum(id1) + sum(id2)

给定SQL ：

SELECT SUM(SCORE1) + SUM(SCORE2) FROM TABLE

优化思路：

首先通过shard计算，尝试构造为MergeNode
a. 如果是KvIndexNode，则代表为可在单库单表上进行执行，此时不做任何优化，直接下推到存储上执行
b. 如果是MergeNode，进入步骤2
c. 如果是JoinNode，进入步骤3
d. 如果是QueryNode，进入步骤4
当前为MergeNode，MergeNode上设置查询列为SUM(SCORE1)+SUM(SCORE2)，遍历所有子节点，删除子节点上的SUM(SCORE1)+SUM(SCORE2)的函数列，然后为每个子节点上设置查询列为 SUM(SCORE1),SUM(SCORE2).
当前为JoinNode，JoinNode上设置查询列为SUM(SCORE1)+SUM(SCORE2)，不对左/右子节点做任何处理. 直接在JoinNode上进行计算
当前为QueryNode，需要分情况进行处理
a. QueryNode节点只是一个简单的SELECT xx FROM (Subquery)，此情况可SUM(SCORE1)+SUM(SCORE2)下推到子节点，做为函数列返回， QueryNode修改为对subquery的函数列的引用.
b. QueryNode节点存在order by /group by / distinct / where条件等，此情况上设置QueryNode查询列为SUM(SCORE1)+SUM(SCORE2)，不对子查询做任何处理.

注意：这个例子的一个特点 Scalar + Aggregate函数的一个组合.

Aggregate函数的参数里包含一个Scalar函数计算，比如max(subString(NAME,0,20))，此时的优化需要借助于元数据下推.
a. 将substring(NAME,0,20)下推到子节点，子节点返回scalar函数计算后，由父节点进行max()计算.
b. 如果子节点不可下推substring函数，那只能下推NAME列，由父节点进行substring计算，然后再进行max计算.
Sclar函数的参数里包含一个Aggregate计算，比如substring(max(name) , 0, 20)，此时的优化需要借助于元数据下推.
a. 将max(name)下推到子节点，子节点返回后，再次计算一次max(name)。 (可以理解为，先让子节点计算一次max(name)，每个子节点返回一条记录，然后在父节点内存中再次计算一次max(name)).
b. 如果子节点不可下推max(name)函数，那只能下推name列，由父节点进行max(name)计算，然后再进行substring计算.
Sclar函数的参数里包含一个scalar计算，比如substring(alias,0,20) + substring(name,0,20)，此时的优化同样需要借助于元数据下推.
a. 将substring(alias,0,20) + substring(name,0,20)下推到子节点，父节点不做任何处理，直接返回子节点返回的数据
b. 如果子节点不支持这些函数，只能下推alias,name等列数据，由父节点进行函数计算
Aggregate函数里包含Aggregate函数，这种情况不存在.

分库distinct(name)

给定SQL ：

SELECT DISTINCT(NAME) FROM TABLE

优化思路：

首先通过shard计算，尝试构造为MergeNode
a. 如果是KvIndexNode，则代表为可在单库单表上进行执行，此时不做任何优化，直接下推到存储上执行
b. 如果是MergeNode，进入步骤2
c. 如果是JoinNode，进入步骤3
d. 如果是QueryNode，进入步骤4
当前为MergeNode，MergeNode上设置查询列为DISTINCT(NAME)，遍历所有子节点，设置查询列为DISTINCT(NAME)，同时需要下推distinct的order信息.
当前为JoinNode，JoinNode上设置查询列为DISTINCT(NAME)，同时需要下推distinct的order信息. 直接在JoinNode上进行计算
当前为QueryNode，QueryNode查询列为DISTINCT(NAME)，同时可下推子查询进行DISTINCT(NAME)操作.

注意：Merge节点的distinct(name)的处理思路，先底下子节点做一次distinct，同时所有子节点按照统一的order顺序进行返回，然后上层merge节点再做一次有序归并，计算出distinct结果

分库count(distinct name)

给定SQL：

SELECT COUNT(DISTINCT NAME) FROM TABLE

优化思路：

首先通过shard计算，尝试构造为MergeNode
a. 如果是KvIndexNode，则代表为可在单库单表上进行执行，此时不做任何优化，直接下推到存储上执行
b. 如果是MergeNode，进入步骤2
c. 如果是JoinNode，进入步骤3
d. 如果是QueryNode，进入步骤4
当前为MergeNode，MergeNode上设置查询列为COUNT(DISTINCT NAME)，遍历所有子节点，设置查询列为DISTINCT(NAME)，同时需要下推distinct的order信息.
当前为JoinNode，JoinNode上设置查询列为COUNT(DISTINCT NAME)，下推distinct的order信息，在JoinNode上进行COUNT(DISTINCT NAME)计算.
当前为QueryNode，QueryNode查询列为COUNT (DISTINCT NAME)，同时可下推子查询进行DISTINCT(NAME)操作，在QueryNode计算COUNT.

注意：目前mysql语法支持DISTINCT和Aggregate函数的组合，MergeNode下推的时候，只能下推DISTINCT(NAME)函数，merge节点上首先进行一次有序归并，计算出distinct结果后，再进行count函数计算.

生成执行计划

类结构图：

说明：

执行计划类图基本和抽象语法树的类结构图一致，每个语法树节点都会对应于执行计划中的一个节点.
执行计划中依赖的元数据(column,function)等，和语法树共享对象，不做单独定义.

执行计划实现类：

普通java bean ：单机客户端运行模式，优化器和执行器部署于同一个jvm中，不存在跨jvm调用。
protobuf bean：优化器和执行器存在跨机执行，执行计划会按照protobuf进行序列化，传输至远程进行执行.

实例分析

SELECT 
               b.thedate, (sum(b.click)/sum(b.impression)) as ctr, (sum(b.cost) / sum(b.click)) as ppc,
               a.name, a.onlinestatus, a.reason
FROM
               tableA a left join tableB b on a.id=b.adgroupid
WHERE
               a.name like ‘%连衣裙%’
               AND a.onlinestatue in (1,2,3)
               AND b.impression>10
               AND b.thedate between ‘2013-12-12’AND ‘2013-12-31’
GROUP BY
               b.thedate, b.memberid, b.campaignid, b.productlineid, b.adgroupid
HAVING
               ppc>1
ORDER BY 
               ppc DESC
LIMIT 
               1，100；

背景说明：

SQL中为表tableA和表tableB的一个left join
包含order by / group by / having / limit / Aggregate函数 / Scalar函数

如果tableA和tableB，属于一个ER分片，tableA按照id进行分库分表，tableB按照adgroupid进行分库分表，两表都划分了4个库，每个库上8张表.

这样的条件，优化结果为：

整体为一个join merge join的树结构
merge节点上
a. limit=1,100
b. 存在group by b.adgroupid, b.thedate, b.memberid, b.campaignid, b.productlineid 【注意：将groupby中的adgroupid提到最前，和join列保持相同的orderby】
c. 存在having ppc>1
d. 存在order by ppc desc. 【注意：因为存在groupby，并且groupby和orderby并不是一个包含的关系，所以此处需要一次临时表二次排序】
join节点上
a. 根据where条件，不存在对应的分库条件，所以会是拆分为对32个表的查询操作，所以这里会是32个join子节点，同时因为不满足节点下推中的特殊case1，所以还是可以继续走ER分片，下推join节点，所以整体结构为join merge join
b. limit = 0,101. 【注意：参考特殊场景优化1】
c. 不存在having条件
d. 存在group by和order by，均为b.adgroupid, b.thedate, b.memberid, b.campaignid, b.productlineid
e. 存在where条件， b.impression>10 and b.thedate between ‘2013-12-12’AND ‘2013-12-31’ 【a表的条件会下推到左表上】
f. 因为outer表存在orderby条件，join策略选择Sort Merge Join
g. 存在列信息：b.thedate, (sum(b.click)/sum(b.impression)) as ctr, (sum(b.cost) / sum(b.click)) as ppc, a.name, a.onlinestatus, a.reason
join左节点
a. 不存在limit,group by和having条件
b. 存在order by a.id
c. 存在where条件， a.name like ‘%连衣裙%’ and a.onlinestatue in (1,2,3)
d. 存在列信息：a.name, a.onlinestatus, a.reason
join右节点
a. 不存在limit,group by和having条件
b. 存在order by b.adgroupid, b.thedate, b.memberid, b.campaignid, b.productlineid
c. 不存在where条件
d. 存在列信息：b.thedate, b.click, b.impression, b.cost , b.click 【对应的sum函数计算，都在join节点进行】

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Tddl_Optimizer

背景

工作原理

构建语法树

元数据

抽象语法树

Sql例子

优化逻辑

预处理优化

Join预处理

Filter预处理

下推优化

Filter下推

Order下推

元数据下推

索引优化

二级索引

索引选择

Filter拆分

Join优化

Join策略选择

二级索引join优化

Join顺序选择

Shard计算(分库分表)

MergeNode构造

节点下推

特殊场景优化

分库limit

分库Avg

分库sum(id1) + sum(id2)

分库distinct(name)

分库count(distinct name)

生成执行计划

实例分析

Clone this wiki locally