大云海山数据库(He3DB) 内核分析-子查询优化概述子查询分类:相关子查询子查询语句引用了外层查询中表的列属性。eg select * from t1 where c1 exists (select c1 from t2 where t1.c2 t2.c2);非相关子查询子查询语句和外层表没有直接关系子查询可以单独执行一次外层查询重复使用子查询的执行结果。eg select * from t1 where c1 exists (select c1 from t2);He3DB子查询分类子连接出现在表达式中的子查询叫做子连接where、on、having条件、投影中。egselect * from t1 where c1 in (select c1 from t2);子查询出现在范围表中的子查询叫做子查询from子句。egselect * from t1 , (select * from t2) t ;抛开大云海山数据库(He3DB) 不看单独理解子查询优化可以分为子查询合并、子查询反嵌套子查询上拉、聚集子查询消除三种优化思路在He3DB中仅仅实现了子查询上拉中的部分优化功能对于另外两种是完全不支持。子连接上拉He3DB中子连接有以下几种typedef enum SubLinkType{EXISTS_SUBLINK,ALL_SUBLINK,ANY_SUBLINK,ROWCOMPARE_SUBLINK,EXPR_SUBLINK,MULTIEXPR_SUBLINK,ARRAY_SUBLINK,CTE_SUBLINK /* for SubPlans only */} SubLinkType;He3DB主要对其中的EXISTS_SUBLINK、ANY_SUBLINK两种子连接做了上拉优化其他类型的子连接不做上拉处理EXISTS_SUBLINK对应的是SQL语句中的exists、not exists谓词ANY_SUBLINK对应的是any、in、not in、some谓词ALL_SUBLINK对应的是all谓词但是ALL_SUBLINK在He3DB中没有做上拉不在详细展开着重看一下EXISTS_SUBLINK和ANY_SUBLINK类型的子连接上拉。EXISTS_SUBLINK上拉He3DB优化器会上拉相关联的exists子连接变形成为semijoin非相关exists子连接不上拉形成initplan单独求解一次求解全局使用。exists相关子连接postgres# explain select * from t1 where exists (select c1 from t2 where t1.c1 t2.c1);QUERY PLANHash Semi Join (cost271.00…555.88 rows10100 width8)Hash Cond: (t1.c1 t2.c1)- Seq Scan on t1 (cost0.00…146.00 rows10100 width8)- Hash (cost146.00…146.00 rows10000 width4)- Seq Scan on t2 (cost0.00…146.00 rows10000 width4)(5 rows)exists非相关子连接postgres# explain select * from t1 where exists (select c1 from t2 );QUERY PLANResult (cost0.01…146.01 rows10100 width8)One-Time Filter: $0InitPlan 1 (returns $0)- Seq Scan on t2 (cost0.00…146.00 rows10000 width0)- Seq Scan on t1 (cost0.01…146.01 rows10100 width8)(5 rows)not exists 相关子连接postgres# explain select * from t1 where not exists (select c1 from t2 where t1.c1 t2.c1);QUERY PLANHash Anti Join (cost271.00…454.88 rows1 width8)Hash Cond: (t1.c1 t2.c1)- Seq Scan on t1 (cost0.00…146.00 rows10100 width8)- Hash (cost146.00…146.00 rows10000 width4)- Seq Scan on t2 (cost0.00…146.00 rows10000 width4)(5 rows)not exists非相关子连接postgres# explain select * from t1 where not exists (select c1 from t2 );QUERY PLANResult (cost0.01…146.01 rows10100 width8)One-Time Filter: (NOT $0)InitPlan 1 (returns $0)- Seq Scan on t2 (cost0.00…146.00 rows10000 width0)- Seq Scan on t1 (cost0.01…146.01 rows10100 width8)(5 rows)ANY_LINK上拉any类型的子连接理论上相关和非相关都可以上拉转成semijoin在He3DB中只做了非相关的子连接上拉相关子连接还是以subplan的形式执行。any相关子连接postgres# explain select * from t1 where c1 any (select c1 from t2 where t1.c2 t2.c2);QUERY PLANSeq Scan on t1 (cost0.00…863733.88 rows5050 width8)Filter: (SubPlan 1)SubPlan 1- Seq Scan on t2 (cost0.00…171.00 rows1 width4)Filter: (t1.c2 c2)(5 rows)any非相关子连接postgres# explain select * from t1 where c1 any (select c1 from t2);QUERY PLANNested Loop Semi Join (cost0.00…1010368.00 rows3367 width8)Join Filter: (t1.c1 t2.c1)- Seq Scan on t1 (cost0.00…146.00 rows10100 width8)- Materialize (cost0.00…196.00 rows10000 width4)- Seq Scan on t2 (cost0.00…146.00 rows10000 width4)(5 rows)子连接上拉代码实现从上面的流程图可以看出子连接的优化在He3DB中相当的苛刻必须要严格满足必要的条件才能执行子连接上拉的优化逻辑。对于EXISTS_SUBLINK类型的子连接需要满足以下条件才能上拉1子查询中不能包含cte语句。2子查询必须要是简单的语句不能有聚集、分组、窗口函数、limit等子句。3子查询中where/on条件必须包含父查询的列关联子查询其他子句必须不包含父查询的列。4子查询不能含有易失性函数。EXISTS_SUBLINK类型子连接上拉过程1调整子查询中var的varno和varlevelsup值2子查询的范围表添加到父查询的rtable链表中3创建join节点左孩子使用父查询的范围表右孩子使用子查询的范围表根据exists和not exists分别使用semijoin和antijoin。对于ANY_SUBLINK类型的子连接上拉的条件1子查询必须为非关联子查询2any表达式必须包含父查询相关的列testexpr3any表达式不能有易失性函数ANY_SUBLINK类型子连接上拉过程1为子查询生成RangetableEntryrte并插入父查询的rtable中2生成新的RangeTableRefrtr3使用子查询的投影列生成新的var list替换testexpr中的Param构建新的表达式作为join的条件4创建semijoin节点左孩子使用父查询的范围表右孩子使用子查询的rtr连接条件使用varlist生成的新表达式。从上面的步骤可以看出EXISTS_SUBLINK是直接转为表和表之间的连接而ANY_SUBLINK类型的子连接则是转为子查询再由后续的子查询上拉逻辑处理变形后查询树到此He3DB中的子连接上拉优化逻辑就梳理完了。子查询上拉子查询上拉代码实现子查询上拉功能主要实现函数是pull_up_subqueries_recurse该函数根据输入节点类型分三种不同情况处理RangeTblRef、FromExpr、JoinExpr其中RangeTblRef是叶子节点也是递归逻辑的出口其他两种类型最终都会递归处理到RangeTblRef类型中在RangeTblRef类型中又根据rtekind分为四种情况处理1RTE_SUBQUERYsimple调用pull_up_simple_subquery函数处理2RTE_SUBQUERYunion调用pull_up_simple_union_all函数处理3RTE_SUBQUERYvalues调用pull_up_simple_values函数处理4RTE_SUBQUERYfunction调用pull_up_constant_function函数处理其中simple类型的子查询最常使用下面看一下该类型的子查询的提升逻辑实现。和子连接一样RTE_SUBQUERYsimple子查询想要上拉也得满足一定的条件1子查询是select类型的子查询2子查询不能包含集合操作setOperations为NULL3子查询不能有agg、group by、sort、limit、cte、窗口函数等操作4子查询不能含有易失性函数RTE_SUBQUERYsimple子查询上拉过程1调整子查询中列的varno和varlevelsup值2如果父查询中引用了子查询的列使用调整后var替换父查询的引用3合并子查询的rtable链表到父查询的rtable链表中合并父子查询树
大云海山数据库(He3DB) PG内核分析-子查询优化
大云海山数据库(He3DB) 内核分析-子查询优化概述子查询分类:相关子查询子查询语句引用了外层查询中表的列属性。eg select * from t1 where c1 exists (select c1 from t2 where t1.c2 t2.c2);非相关子查询子查询语句和外层表没有直接关系子查询可以单独执行一次外层查询重复使用子查询的执行结果。eg select * from t1 where c1 exists (select c1 from t2);He3DB子查询分类子连接出现在表达式中的子查询叫做子连接where、on、having条件、投影中。egselect * from t1 where c1 in (select c1 from t2);子查询出现在范围表中的子查询叫做子查询from子句。egselect * from t1 , (select * from t2) t ;抛开大云海山数据库(He3DB) 不看单独理解子查询优化可以分为子查询合并、子查询反嵌套子查询上拉、聚集子查询消除三种优化思路在He3DB中仅仅实现了子查询上拉中的部分优化功能对于另外两种是完全不支持。子连接上拉He3DB中子连接有以下几种typedef enum SubLinkType{EXISTS_SUBLINK,ALL_SUBLINK,ANY_SUBLINK,ROWCOMPARE_SUBLINK,EXPR_SUBLINK,MULTIEXPR_SUBLINK,ARRAY_SUBLINK,CTE_SUBLINK /* for SubPlans only */} SubLinkType;He3DB主要对其中的EXISTS_SUBLINK、ANY_SUBLINK两种子连接做了上拉优化其他类型的子连接不做上拉处理EXISTS_SUBLINK对应的是SQL语句中的exists、not exists谓词ANY_SUBLINK对应的是any、in、not in、some谓词ALL_SUBLINK对应的是all谓词但是ALL_SUBLINK在He3DB中没有做上拉不在详细展开着重看一下EXISTS_SUBLINK和ANY_SUBLINK类型的子连接上拉。EXISTS_SUBLINK上拉He3DB优化器会上拉相关联的exists子连接变形成为semijoin非相关exists子连接不上拉形成initplan单独求解一次求解全局使用。exists相关子连接postgres# explain select * from t1 where exists (select c1 from t2 where t1.c1 t2.c1);QUERY PLANHash Semi Join (cost271.00…555.88 rows10100 width8)Hash Cond: (t1.c1 t2.c1)- Seq Scan on t1 (cost0.00…146.00 rows10100 width8)- Hash (cost146.00…146.00 rows10000 width4)- Seq Scan on t2 (cost0.00…146.00 rows10000 width4)(5 rows)exists非相关子连接postgres# explain select * from t1 where exists (select c1 from t2 );QUERY PLANResult (cost0.01…146.01 rows10100 width8)One-Time Filter: $0InitPlan 1 (returns $0)- Seq Scan on t2 (cost0.00…146.00 rows10000 width0)- Seq Scan on t1 (cost0.01…146.01 rows10100 width8)(5 rows)not exists 相关子连接postgres# explain select * from t1 where not exists (select c1 from t2 where t1.c1 t2.c1);QUERY PLANHash Anti Join (cost271.00…454.88 rows1 width8)Hash Cond: (t1.c1 t2.c1)- Seq Scan on t1 (cost0.00…146.00 rows10100 width8)- Hash (cost146.00…146.00 rows10000 width4)- Seq Scan on t2 (cost0.00…146.00 rows10000 width4)(5 rows)not exists非相关子连接postgres# explain select * from t1 where not exists (select c1 from t2 );QUERY PLANResult (cost0.01…146.01 rows10100 width8)One-Time Filter: (NOT $0)InitPlan 1 (returns $0)- Seq Scan on t2 (cost0.00…146.00 rows10000 width0)- Seq Scan on t1 (cost0.01…146.01 rows10100 width8)(5 rows)ANY_LINK上拉any类型的子连接理论上相关和非相关都可以上拉转成semijoin在He3DB中只做了非相关的子连接上拉相关子连接还是以subplan的形式执行。any相关子连接postgres# explain select * from t1 where c1 any (select c1 from t2 where t1.c2 t2.c2);QUERY PLANSeq Scan on t1 (cost0.00…863733.88 rows5050 width8)Filter: (SubPlan 1)SubPlan 1- Seq Scan on t2 (cost0.00…171.00 rows1 width4)Filter: (t1.c2 c2)(5 rows)any非相关子连接postgres# explain select * from t1 where c1 any (select c1 from t2);QUERY PLANNested Loop Semi Join (cost0.00…1010368.00 rows3367 width8)Join Filter: (t1.c1 t2.c1)- Seq Scan on t1 (cost0.00…146.00 rows10100 width8)- Materialize (cost0.00…196.00 rows10000 width4)- Seq Scan on t2 (cost0.00…146.00 rows10000 width4)(5 rows)子连接上拉代码实现从上面的流程图可以看出子连接的优化在He3DB中相当的苛刻必须要严格满足必要的条件才能执行子连接上拉的优化逻辑。对于EXISTS_SUBLINK类型的子连接需要满足以下条件才能上拉1子查询中不能包含cte语句。2子查询必须要是简单的语句不能有聚集、分组、窗口函数、limit等子句。3子查询中where/on条件必须包含父查询的列关联子查询其他子句必须不包含父查询的列。4子查询不能含有易失性函数。EXISTS_SUBLINK类型子连接上拉过程1调整子查询中var的varno和varlevelsup值2子查询的范围表添加到父查询的rtable链表中3创建join节点左孩子使用父查询的范围表右孩子使用子查询的范围表根据exists和not exists分别使用semijoin和antijoin。对于ANY_SUBLINK类型的子连接上拉的条件1子查询必须为非关联子查询2any表达式必须包含父查询相关的列testexpr3any表达式不能有易失性函数ANY_SUBLINK类型子连接上拉过程1为子查询生成RangetableEntryrte并插入父查询的rtable中2生成新的RangeTableRefrtr3使用子查询的投影列生成新的var list替换testexpr中的Param构建新的表达式作为join的条件4创建semijoin节点左孩子使用父查询的范围表右孩子使用子查询的rtr连接条件使用varlist生成的新表达式。从上面的步骤可以看出EXISTS_SUBLINK是直接转为表和表之间的连接而ANY_SUBLINK类型的子连接则是转为子查询再由后续的子查询上拉逻辑处理变形后查询树到此He3DB中的子连接上拉优化逻辑就梳理完了。子查询上拉子查询上拉代码实现子查询上拉功能主要实现函数是pull_up_subqueries_recurse该函数根据输入节点类型分三种不同情况处理RangeTblRef、FromExpr、JoinExpr其中RangeTblRef是叶子节点也是递归逻辑的出口其他两种类型最终都会递归处理到RangeTblRef类型中在RangeTblRef类型中又根据rtekind分为四种情况处理1RTE_SUBQUERYsimple调用pull_up_simple_subquery函数处理2RTE_SUBQUERYunion调用pull_up_simple_union_all函数处理3RTE_SUBQUERYvalues调用pull_up_simple_values函数处理4RTE_SUBQUERYfunction调用pull_up_constant_function函数处理其中simple类型的子查询最常使用下面看一下该类型的子查询的提升逻辑实现。和子连接一样RTE_SUBQUERYsimple子查询想要上拉也得满足一定的条件1子查询是select类型的子查询2子查询不能包含集合操作setOperations为NULL3子查询不能有agg、group by、sort、limit、cte、窗口函数等操作4子查询不能含有易失性函数RTE_SUBQUERYsimple子查询上拉过程1调整子查询中列的varno和varlevelsup值2如果父查询中引用了子查询的列使用调整后var替换父查询的引用3合并子查询的rtable链表到父查询的rtable链表中合并父子查询树
