作者：chirpyli
起源：恒生 LIGHT 云社区
子查问的逻辑优化内容很多，咱们先以 select * from t1 where id in (select a from t2);这条 SQL 语句为例剖析 PostgreSQL 对子连贯的逻辑优化过程。
在往下讲之前，先区别一下子连贯与子查问，因为代码中别离会对子连贯和子查问进行上拉操作。怎么区别呢？通常，以范畴表的形式存在的称为子查问，以表达式的形式存在的称为子连贯。实际上也能够通过子句所处的地位来区分子连贯和子查问，呈现在 FROM 关键字之后的子句时子查问语句，呈现在 WHERE 等约束条件中的是子连贯。
咱们先通过执行打算进行察看剖析，数据库通过 Hash Semi Join对子连贯进行了逻辑优化。
-- 查看执行打算
postgres=# explain select * from t1 where id in (select a from t2);
QUERY PLAN
---------------------------------------------------------------
Hash Semi Join (cost=1.09..2.21 rows=4 width=8)
Hash Cond: (t1.id = t2.a)
-> Seq Scan on t1 (cost=0.00..1.06 rows=6 width=8)
-> Hash (cost=1.04..1.04 rows=4 width=4)
-> Seq Scan on t2 (cost=0.00..1.04 rows=4 width=4)解析层剖析
咱们先剖析子连贯在解析层的示意（以这条语句为例，其余子连贯模式相似）：
/* A SubLink represents a subselect appearing in an expression, and in some
* cases also the combining operator(s) just above it. */
typedef struct SubLink
{
Expr xpr;
SubLinkType subLinkType; /* see above */
int subLinkId; /* ID (1..n); 0 if not MULTIEXPR */
Node *testexpr; /* outer-query test for ALL/ANY/ROWCOMPARE */
List *operName; /* originally specified operator name */
Node *subselect; /* subselect as Query* or raw parsetree */
int location; /* token location, or -1 if unknown */
} SubLink;语法定义如下：
// 匹配 where id in (select a from t2);
where_clause:
WHERE a_expr {$$ = $2;}
| /*EMPTY*/ {$$ = NULL;}
;
// 匹配 id in (select a from t2);
a_expr: c_expr {$$ = $1;}
| a_expr IN_P in_expr
{
/* in_expr returns a SubLink or a list of a_exprs */
if (IsA($3, SubLink))
{/* generate foo = ANY (subquery) */
SubLink *n = (SubLink *) $3;
n->subLinkType = ANY_SUBLINK;
n->subLinkId = 0;
n->testexpr = $1; // 具体到下面的 SQL 语句是 id column
n->operName = NIL; /* show it's IN not = ANY */
n->location = @2;
$$ = (Node *)n;
}
else
{
/* generate scalar IN expression */
$$ = (Node *) makeSimpleA_Expr(AEXPR_IN, "=", $1, $3, @2);
}
}
// 匹配 (select a from t2)
in_expr: select_with_parens
{SubLink *n = makeNode(SubLink);
n->subselect = $1;
/* other fields will be filled later */
$$ = (Node *)n;
}
| '(' expr_list ')' {$$ = (Node *)$2; }
;咱们晓得 "x IN (select)", convert to "x = ANY (select)"这个转换是等价的。在解析阶段，会进行 IN转 ANY的解决，在调用过程如下：transformSelectStmt->transformWhereClause->transformExpr->transformSubLink。在 transformSublink中进行这个转换解决：
static Node *transformSubLink(ParseState *pstate, SubLink *sublink)
{Node *result = (Node *) sublink;
Query *qtree;
// 省略中间代码......
/* If the source was "x IN (select)", convert to "x = ANY (select)".*/
if (sublink->operName == NIL)
sublink->operName = list_make1(makeString("="));
// 省略中间代码......
return result;
} 了解了子连贯在解析层的示意后，咱们重点剖析一下逻辑优化阶段的解决。
逻辑优化
逻辑优化的根底是关系代数的等价变换，等价推理。有点相似于中学时数学中的简便运算思维。最容易了解的优化思维是：先抉择后投影，比方抉择下推的目标是缩小两头计算结果从而达到优化的成果。在 PG 中，查问优化器的代码在 src/backend/optimizer目录下：
optimizer
├── geqo // 遗传算法，在连贯较多的状况下会抉择该算法，阈值可调整，默认 geqo_threshold=12
├── path // 物理优化
├── plan // 优化器入口
├── prep // 逻辑优化相干
│ ├── prepjointree.c // 解决连贯操作
│ ├── prepqual.c // 解决抉择条件
│ ├── preptlist.c // 解决投影相干
│ └── prepunion.c // 解决汇合操作
└── util // 公共函数逻辑优化的内容有很多，这里咱们只剖析子连贯的逻辑优化（子连贯上拉），将子连贯转为 SEMI-JOIN，使得子连贯中的子查问有机会与父查问语句进行合并优化。咱们看一下具体的上面的执行打算。能够看到将子查问转为了 SEMI-JOIN 的模式。
postgres=# explain select * from t1 where id in (select cid from school);
QUERY PLAN
------------------------------------------------------------------
Hash Semi Join (cost=1.09..2.21 rows=4 width=8)
Hash Cond: (t1.id = school.cid)
-> Seq Scan on t1 (cost=0.00..1.06 rows=6 width=8)
-> Hash (cost=1.04..1.04 rows=4 width=4)
-> Seq Scan on school (cost=0.00..1.04 rows=4 width=4)咱们敞开 enable_hashjoin再看一下执行打算：
postgres=# set enable_hashjoin=off;
SET
postgres=# explain select * from t1 where id in (select cid from school);
QUERY PLAN
--------------------------------------------------------------------
Merge Semi Join (cost=2.22..2.30 rows=4 width=8)
Merge Cond: (t1.id = school.cid)
-> Sort (cost=1.14..1.15 rows=6 width=8)
Sort Key: t1.id
-> Seq Scan on t1 (cost=0.00..1.06 rows=6 width=8)
-> Sort (cost=1.08..1.09 rows=4 width=4)
Sort Key: school.cid
-> Seq Scan on school (cost=0.00..1.04 rows=4 width=4)敞开 hash join 后走的是 merge join 执行打算，咱们再把 enable_mergejoin 敞开：
postgres=# set enable_mergejoin =off;
SET
postgres=# explain select * from t1 where id in (select cid from school);
QUERY PLAN
------------------------------------------------------------------
Nested Loop Semi Join (cost=0.00..2.47 rows=4 width=8)
Join Filter: (t1.id = school.cid)
-> Seq Scan on t1 (cost=0.00..1.06 rows=6 width=8)
-> Materialize (cost=0.00..1.06 rows=4 width=4)
-> Seq Scan on school (cost=0.00..1.04 rows=4 width=4)咱们看到了逻辑优化后的后果，这里因为我本人结构的数据量很少，所以后果可能不是很显著，当数据量很大时后果比照会非常明显。咱们再看一个例子：
postgres=# explain select * from t1 where id in (select cid from school where students > t1.id);
QUERY PLAN
--------------------------------------------------------------
Seq Scan on t1 (cost=0.00..4.23 rows=3 width=8) /* 这里扫描节点的上层是子执行打算 */
Filter: (SubPlan 1)
SubPlan 1
-> Seq Scan on school (cost=0.00..1.05 rows=1 width=4)
Filter: (students > t1.id)没有被优化为 Semi Join。也就是说并不是所有的子连贯都能够被上拉优化。是否被上拉取决于上拉后是否放弃等价变换（正确性），有很多状况是不能被上拉的，另一个是上拉优化后是否执行效率更高，并不是所有的状况上拉后执行效率更高，具体的咱们剖析一下源码。
源码剖析
查问树生成执行打算是在 planner调用实现，planner会调用 standard_planner，咱们持续往下看：
PlannedStmt *standard_planner(Query *parse, const char *query_string, int cursorOptions, ParamListInfo boundParams)
{
PlannedStmt *result;
// 省略很多代码......
/* primary planning entry point (may recurse for subqueries) */
root = subquery_planner(glob, parse, NULL, false, tuple_fraction); // 看这里
final_rel = fetch_upper_rel(root, UPPERREL_FINAL, NULL);
best_path = get_cheapest_fractional_path(final_rel, tuple_fraction);
top_plan = create_plan(root, best_path); // 创立打算
// 省略很多代码......
return result;
}
PlannerInfo *subquery_planner(PlannerGlobal *glob, Query *parse, PlannerInfo *parent_root, bool hasRecursion, double tuple_fraction)
{
PlannerInfo *root;
// 省略中间代码......
/* Look for ANY and EXISTS SubLinks in WHERE and JOIN/ON clauses, and try
* to transform them into joins. Note that this step does not descend
* into subqueries; if we pull up any subqueries below, their SubLinks are
* processed just before pulling them up.*/
if (parse->hasSubLinks)
pull_up_sublinks(root); // 子连贯上拉优化，能够看到下体面查问也有上拉优化，区别是：子连贯能够认为是呈现在表达式中的子查问。pull_up_subqueries(root); // 子查问上拉
if (parse->setOperations)
flatten_simple_union_all(root);
// 前面是其余优化，包含表达式优化等，这里不再列出.......
}咱们晓得了子连贯上拉优化的调用关系以及地位后具体分析一下其处理过程：
/* Attempt to pull up ANY and EXISTS SubLinks to be treated as semijoins or anti-semijoins. */
void pull_up_sublinks(PlannerInfo *root)
{elog_node_display(NOTICE, "optimizer-before", root->parse->jointree, true); // 可通过减少日志打印出优化前后的变动
Node *jtnode;
Relids relids;
jtnode = pull_up_sublinks_jointree_recurse(root,(Node *) root->parse->jointree,&relids);
if (IsA(jtnode, FromExpr))
root->parse->jointree = (FromExpr *) jtnode;
else
root->parse->jointree = makeFromExpr(list_make1(jtnode), NULL);
elog_node_display(NOTICE, "optimizer-after", root->parse->jointree, true);
}pull_up_sublinks外围实现是在 pull_up_sublinks_jointree_recurse中实现的，咱们持续往下看：
Node *pull_up_sublinks_jointree_recurse(PlannerInfo *root, Node *jtnode, Relids *relids)
{if (jtnode == NULL)
*relids = NULL;
else if (IsA(jtnode, RangeTblRef))
{int varno = ((RangeTblRef *) jtnode)->rtindex;
*relids = bms_make_singleton(varno); /* jtnode is returned unmodified */
}
else if (IsA(jtnode, FromExpr))
{ // 重点看这段代码，子连贯上拉，须要重写 FromExpr
FromExpr *f = (FromExpr *) jtnode;
List *newfromlist = NIL;
Relids frelids = NULL;
FromExpr *newf;
Node *jtlink;
ListCell *l;
/* First, recurse to process children and collect their relids */
foreach(l, f->fromlist) // 对应解决 SQL 语句中的 from t1
{
Node *newchild;
Relids childrelids;
newchild = pull_up_sublinks_jointree_recurse(root,lfirst(l),&childrelids);
newfromlist = lappend(newfromlist, newchild);
frelids = bms_join(frelids, childrelids);
}
/* Build the replacement FromExpr; no quals yet */
newf = makeFromExpr(newfromlist, NULL); // 须要重写 where id in (select cid from school); 条件表达式，所以这里先赋 NULL
/* Set up a link representing the rebuilt jointree */
jtlink = (Node *) newf;
// 重写 where qual。须要重写成相似 select * from t1 semi-join (select cid from school) as any_subquery where t1.id=any_subquery.cid 这样的，留神没有 semi-join 这个语法。newf->quals = pull_up_sublinks_qual_recurse(root, f->quals,&jtlink, frelids, NULL, NULL);
*relids = frelids;
jtnode = jtlink;
}
else if (IsA(jtnode, JoinExpr))
{// 省略局部代码......}
// 省略局部代码......
return jtnode;
}难点在 pull_up_sublinks_qual_recurse的解决上，即怎么重写条件表达式。子连贯有多种，咱们只剖析下面的语句，其余的代码类似，这里不再列出。
Node *pull_up_sublinks_qual_recurse(PlannerInfo *root, Node *node,Node **jtlink1, Relids available_rels1,Node **jtlink2, Relids available_rels2)
{if (node == NULL)
return NULL;
if (IsA(node, SubLink))
{SubLink *sublink = (SubLink *) node;
JoinExpr *j;
Relids child_rels;
/* Is it a convertible ANY or EXISTS clause? */
if (sublink->subLinkType == ANY_SUBLINK) // 重点剖析这种状况，其余状况相似
{if ((j = convert_ANY_sublink_to_join(root, sublink,available_rels1)) != NULL)
{
/* Yes; insert the new join node into the join tree */
j->larg = *jtlink1;
*jtlink1 = (Node *) j;
/* Recursively process pulled-up jointree nodes */
j->rarg = pull_up_sublinks_jointree_recurse(root,j->rarg,&child_rels);
/* Now recursively process the pulled-up quals. Any inserted joins can get stacked onto either j->larg or j->rarg,depending on which rels they reference. */
j->quals = pull_up_sublinks_qual_recurse(root,j->quals,&j->larg,available_rels1,&j->rarg,child_rels);
/* Return NULL representing constant TRUE */
return NULL;
}
if (available_rels2 != NULL &&(j = convert_ANY_sublink_to_join(root, sublink,available_rels2)) != NULL)
{
/* Yes; insert the new join node into the join tree */
j->larg = *jtlink2;
*jtlink2 = (Node *) j;
/* Recursively process pulled-up jointree nodes */
j->rarg = pull_up_sublinks_jointree_recurse(root,j->rarg,&child_rels);
j->quals = pull_up_sublinks_qual_recurse(root,j->quals,&j->larg,available_rels2,&j->rarg,child_rels);
/* Return NULL representing constant TRUE */
return NULL;
}
}
else if (sublink->subLinkType == EXISTS_SUBLINK)
{// 省略代码.......}
/* Else return it unmodified */
return node;
}
if (is_notclause(node))
{
/* If the immediate argument of NOT is EXISTS, try to convert */
SubLink *sublink = (SubLink *) get_notclausearg((Expr *) node);
// 省略代码......
/* Else return it unmodified */
return node;
}
if (is_andclause(node))
{
/* Recurse into AND clause */
// 省略代码......
}
/* Stop if not an AND */
return node;
}还须要再思考一个问题，是所有的状况都能够进行上拉优化吗，显然不是的，后面的例子中曾经看到了，那进行上拉优化须要那些限度条件呢？有 3 条：
- 子连贯中的子查问不能应用其父查问中的任何 Var 类型变量
- 比拟表达式（testexpr）中必须蕴含父查问中的任意一个 Var 类型变量
- 比拟表达式中不能蕴含任何的易失函数
对于易失函数：PG 中的函数有 3 种稳定性级别（VOLATILE、STABLE、IMMUTABLE），其中 VOLATILE 函数输出同样的参数会返回不同的后果，查问优化器通常不对含有 VOLATILE 函数的表达式进行优化，子连贯不能晋升。
// convert_ANY_sublink_to_join: try to convert an ANY SubLink to a join
JoinExpr *convert_ANY_sublink_to_join(PlannerInfo *root, SubLink *sublink,Relids available_rels)
{
JoinExpr *result;
Query *parse = root->parse;
Query *subselect = (Query *) sublink->subselect;
Relids upper_varnos;
int rtindex;
ParseNamespaceItem *nsitem;
RangeTblEntry *rte;
RangeTblRef *rtr;
List *subquery_vars;
Node *quals;
ParseState *pstate;
//ANY 类型的子连贯, 子查问不能依赖父查问的任何变量, 否则不能上拉
if (contain_vars_of_level((Node *) subselect, 1))
return NULL;
// 子查问的 testexpr 变量中必须含有父查问的某些 Vars, 否则不能上拉(join)
upper_varnos = pull_varnos(root, sublink->testexpr);
if (bms_is_empty(upper_varnos))
return NULL;
/* However, it can't refer to anything outside available_rels.*/
if (!bms_is_subset(upper_varnos, available_rels))
return NULL;
// 组合操作符和左侧的表达式不能是易变 (volatile) 的, 比方随机数等
if (contain_volatile_functions(sublink->testexpr))
return NULL;
/* Create a dummy ParseState for addRangeTableEntryForSubquery */
pstate = make_parsestate(NULL);
// 子连贯上拉后, 子查问变成了下层的 RTE, 在这里结构,pull up the sub-select into upper range table.
nsitem = addRangeTableEntryForSubquery(pstate,subselect, makeAlias("ANY_subquery", NIL),false,false);
rte = nsitem->p_rte;
parse->rtable = lappend(parse->rtable, rte);
rtindex = list_length(parse->rtable);
/* Form a RangeTblRef for the pulled-up sub-select.*/
rtr = makeNode(RangeTblRef);
rtr->rtindex = rtindex;
/* Build a list of Vars representing the subselect outputs.*/
subquery_vars = generate_subquery_vars(root,subselect->targetList,rtindex);
/* Build the new join's qual expression 结构新的 join 的条件表达式 */
quals = convert_testexpr(root, sublink->testexpr, subquery_vars);
/* And finally, build the JoinExpr node.*/
result = makeNode(JoinExpr);
result->jointype = JOIN_SEMI; // 变换为半连贯
result->isNatural = false;
result->larg = NULL; /* caller must fill this in */
result->rarg = (Node *) rtr;
result->usingClause = NIL;
result->quals = quals;
result->alias = NULL;
result->rtindex = 0; /* we don't need an RTE for it */
return result;
}后记
这里只借助一条 SQL 语句剖析了一下其逻辑优化的过程，其中还有很多内容并没有讲，比方 EXIST 类型子连贯，相干子连贯与非相干子连贯的逻辑优化状况，这个能够联合执行打算和源码自行去剖析，前面还会补充这方面的内容，这里不再开展。另外须要留神的是，有的子连贯会晋升为子查问，有的不会，（比方，ANY 类型子连贯个别会晋升为子查问，EXIST 类型子连贯不会，间接晋升为表与表的连贯形式）。
针对下面的问题，举个例子：select * from ttt where exists (select id from teacher where ttt.id > id);
postgres=# explain (costs false) select * from ttt where exists (select id from teacher where ttt.id > id);
QUERY PLAN
--------------------------------------
Nested Loop Semi Join
Join Filter: (ttt.id > teacher.id)
-> Seq Scan on ttt
-> Materialize
-> Seq Scan on teacher会被优化成相似 select * from ttt semi join teacher where ttt.id > id的模式。
咱们再举个例子：select * from ttt where id > any (select id from teacher);ANY 子连贯优化后果：
postgres=# explain (costs false) select * from ttt where id > any (select id from teacher);
QUERY PLAN
--------------------------------------
Nested Loop Semi Join
Join Filter: (ttt.id > teacher.id)
-> Seq Scan on ttt
-> Materialize
-> Seq Scan on teacher在 pull_up_sublink阶段，会将其优化为相似 select * from ttt semi join (select id from teacher) as ANY_subquery where ttt.id > ANY_subquery.id的模式。也就是说将 ANY 类型的子连贯转换为了子查问的模式，这里只做了一半，后一半是子查问优化，也就是会将子查问进行上拉。这一优化过程前面文章再持续剖析子查问优化 pull_up_subquery。所以说，子连贯的优化学习还没有完结，前面还要持续剖析学习子查问的逻辑优化过程。
想向技术大佬们多多取经？开发中遇到的问题何处探讨？如何获取金融科技海量资源？
恒生 LIGHT 云社区，由恒生电子搭建的金融科技业余社区平台，分享实用技术干货、资源数据、金融科技行业趋势，拥抱所有金融开发者。
扫描下方小程序二维码，退出咱们！