共计 9660 个字符，预计需要花费 25 分钟才能阅读完成。
在上期 Postgres 技术底细系列直播中，咱们为大家介绍了 Postgres 投影算子和表达式计算实现原理和底层细节。本文依据直播内容整顿，作者现任 HashData 内核研发工程师。
投影 (projection)
关系代数中的一种，用于从关系 R 中选出属性蕴含在 A 中的列。
在 PG 中也用于引入额定的列（比方计算表达式）
PG 对投影的实现
整体实现能够分为三个次要局部：
1、判断是否须要投影
当且仅当被扫描的关系的描述符和打算节点的 targetlist 不匹配的时候，才须要进行投影，tlist_matches_tupdesc 函数用于实现相干的判断逻辑。
| static bool | |
| tlist_matches_tupdesc(PlanState *ps, List *tlist, Index varno, TupleDesc tupdesc) | |
| { | |
| int numattrs = tupdesc->natts; | |
| int attrno; | |
| ListCell *tlist_item = list_head(tlist); | |
| /* Check the tlist attributes */ | |
| for (attrno = 1; attrno <= numattrs; attrno++) | |
| {Form_pg_attribute att_tup = TupleDescAttr(tupdesc, attrno - 1); | |
| Var *var; | |
| if (tlist_item == NULL) | |
| return false; /* tlist too short */ | |
| var = (Var *) ((TargetEntry *) lfirst(tlist_item))->expr; | |
| if (!var || !IsA(var, Var)) | |
| return false; /* tlist item not a Var */ | |
| /* if these Asserts fail, planner messed up */ | |
| Assert(var->varno == varno); | |
| Assert(var->varlevelsup == 0); | |
| if (var->varattno != attrno) | |
| return false; /* out of order */ | |
| if (att_tup->attisdropped) | |
| return false; /* table contains dropped columns */ | |
| if (att_tup->atthasmissing) | |
| return false; /* table contains cols with missing values */ | |
| /* | |
| * Note: usually the Var's type should match the tupdesc exactly, but | |
| * in situations involving unions of columns that have different | |
| * typmods, the Var may have come from above the union and hence have | |
| * typmod -1. This is a legitimate situation since the Var still | |
| * describes the column, just not as exactly as the tupdesc does. We | |
| * could change the planner to prevent it, but it'd then insert | |
| * projection steps just to convert from specific typmod to typmod -1, | |
| * which is pretty silly. | |
| */ | |
| if (var->vartype != att_tup->atttypid || | |
| (var->vartypmod != att_tup->atttypmod && | |
| var->vartypmod != -1)) | |
| return false; /* type mismatch */ | |
| tlist_item = lnext(tlist, tlist_item); | |
| } | |
| if (tlist_item) | |
| return false; /* tlist too long */ | |
| return true; | |
| } |
其外围逻辑就是遍历 targetlist 并判断与扫描表的描述符是否匹配，比较简单，这里不再展开讨论。
2、构建投影所须要的信息
| ProjectionInfo * | |
| ExecBuildProjectionInfo(List *targetList, | |
| ExprContext *econtext, | |
| TupleTableSlot *slot, | |
| PlanState *parent, | |
| TupleDesc inputDesc) | |
| { | |
| /* Insert EEOP_*_FETCHSOME steps as needed */ | |
| ExecInitExprSlots(state, (Node *) targetList); | |
| /* Now compile each tlist column */ | |
| foreach(lc, targetList) | |
| { | |
| /* 思考投影列为 var 的状况 */ | |
| if (tle->expr != NULL && | |
| IsA(tle->expr, Var) && | |
| ((Var *) tle->expr)->varattno > 0) | |
| {if (inputDesc == NULL) | |
| isSafeVar = true; /* can't check, just assume OK */ | |
| else if (attnum <= inputDesc->natts) | |
| {Form_pg_attribute attr = TupleDescAttr(inputDesc, attnum - 1); | |
| /* | |
| * If user attribute is dropped or has a type mismatch, don't | |
| * use ASSIGN_*_VAR. Instead let the normal expression | |
| * machinery handle it (which'll possibly error out). | |
| */ | |
| if (!attr->attisdropped && variable->vartype == attr->atttypid) | |
| {isSafeVar = true;} | |
| } | |
| /* 对于简略的状况只须要 EEOP_ASSIGN_*_VAR 即可 */ | |
| if (isSafeVar) | |
| { | |
| /* Fast-path: just generate an EEOP_ASSIGN_*_VAR step */ | |
| switch (variable->varno) | |
| { | |
| case INNER_VAR: | |
| /* get the tuple from the inner node */ | |
| scratch.opcode = EEOP_ASSIGN_INNER_VAR; | |
| break; | |
| case OUTER_VAR: | |
| /* get the tuple from the outer node */ | |
| scratch.opcode = EEOP_ASSIGN_OUTER_VAR; | |
| break; | |
| /* INDEX_VAR is handled by default case */ | |
| default: | |
| /* get the tuple from the relation being scanned */ | |
| scratch.opcode = EEOP_ASSIGN_SCAN_VAR; | |
| break; | |
| } | |
| /* | |
| * 这里是外围逻辑 构建了投影所须要的执行步骤 在执行过程中依照步骤顺次执行即可 | |
| * 这么做的实质是为了升高函数递归调用的运行老本 | |
| */ | |
| ExprEvalPushStep(state, &scratch); | |
| } | |
| else | |
| { | |
| /* 具体来说，蕴含表达式计算，或者零碎变量等状况时，要依照惯例形式解决表达式 */ | |
| /* | |
| * Otherwise, compile the column expression normally. | |
| * | |
| * We can't tell the expression to evaluate directly into the | |
| * result slot, as the result slot (and the exprstate for that | |
| * matter) can change between executions. We instead evaluate | |
| * into the ExprState's resvalue/resnull and then move. | |
| */ | |
| ExecInitExprRec(tle->expr, state, | |
| &state->resvalue, &state->resnull); | |
| // 投影求值计算的时候会用到 attnum 和 resultnum | |
| scratch.d.assign_var.attnum = attnum - 1; | |
| scratch.d.assign_var.resultnum = tle->resno - 1; | |
| ExprEvalPushStep(state, &scratch); | |
| } | |
| } | |
| } | |
| } |
本节咱们次要注解了上述代码中 fast-path 相干逻辑，其余逻辑在后续开展解说。
这段代码的外围逻辑在于通过调用 ExprEvalPushStep 构建了用数组示意的投影的执行过程，并通过 opcode 标识每个步骤的类型，这样在执行阶段即可依据 opcode 调用不同的过程，请参考下文的执行过程一起了解。
相比于传统的表达式求值逻辑，这样写的益处在于缩小函数递归调用。3、执行投影算子执行器投影算子入口函数，能够看到要害函数是 ExecEvalExprSwitchContext，在 PG 中和表达式求值无关的逻辑都通过这个函数实现。
| #ifndef FRONTEND | |
| static inline TupleTableSlot * | |
| ExecProject(ProjectionInfo *projInfo) | |
| { | |
| ExprState *state = &projInfo->pi_state; | |
| TupleTableSlot *slot = state->resultslot; // 投影之后的后果；目前还是未计算的状态 | |
| /* Run the expression, discarding scalar result from the last column. */ | |
| (void) ExecEvalExprSwitchContext(state, econtext, &isnull); | |
| return slot; | |
| } |
首先要介绍一下 PG 表达式求值的框架，投影求值也是利用表达式求值实现的，即调用 ExecEvalExprSwitchContext，其底层调用了 ExecInterpExpr。
整个执行过程建设在一套由宏定义实现的散发器机制之上，实现了对之前构建的表达式求值步骤依次执行的逻辑。在过程执行中，咱们会用 ExprState 来存储两头计算结果和其余执行状态。具体代码如下：
| // opcode 对应步骤的实现逻辑的标识 用于 goto | |
| #define EEO_CASE(name) CASE_##name: | |
| // 散发至步骤的执行逻辑 | |
| #define EEO_DISPATCH() goto *((void *) op->opcode) | |
| // | |
| #define EEO_OPCODE(opcode) ((intptr_t) dispatch_table[opcode]) | |
| // 以后步骤执行结束时挪动至下一个须要执行的步骤 | |
| #define EEO_NEXT() \ | |
| do { \ | |
| op++; \ | |
| EEO_DISPATCH(); \} while (0) | |
| ExecInterpExpr(ExprState *state, ExprContext *econtext, bool *isnull) | |
| { | |
| op = state->steps; // 存储所有的步骤，咱们通过宏一直挪动以后执行的步骤 | |
| resultslot = state->resultslot; // 用于寄存最初返回的后果值 | |
| innerslot = econtext->ecxt_innertuple; | |
| outerslot = econtext->ecxt_outertuple; | |
| scanslot = econtext->ecxt_scantuple; | |
| EEO_DISPATCH(); | |
| EEO_CASE() | |
| EEO_CASE(EEOP_DONE) | |
| {goto out;} | |
| EEO_CASE(EEOP_SCAN_FETCHSOME) | |
| {CheckOpSlotCompatibility(op, scanslot); | |
| slot_getsomeattrs(scanslot, op->d.fetch.last_var); | |
| EEO_NEXT();} | |
| EEO_CASE(EEOP_ASSIGN_SCAN_VAR) | |
| { | |
| int resultnum = op->d.assign_var.resultnum; | |
| int attnum = op->d.assign_var.attnum; | |
| /* | |
| * We do not need CheckVarSlotCompatibility here; that was taken | |
| * care of at compilation time. But see EEOP_INNER_VAR comments. | |
| */ | |
| resultslot->tts_values[resultnum] = scanslot->tts_values[attnum]; | |
| resultslot->tts_isnull[resultnum] = scanslot->tts_isnull[attnum]; | |
| EEO_NEXT();} | |
| out: | |
| *isnull = state->resnull | |
| return state->resvalue | |
| } |
这样，咱们就实现了投影列计算的逻辑，最终的 tuple 存储在 state->resultslot 里，供下层算子应用。
表达式计算
上面咱们介绍表达式计算的实现。表达式计算的过程和后面投影列求值的过程复用了同样的逻辑，即利用同样的散发机制进行求值。
显著不同的中央包含：
1）计算逻辑通常更为简单，须要多个步骤实现，实质上是以迭代的形式对表达式树进行求值；
2）表达式能够预计算，其中常量的局部在优化器阶段就能够求值，防止迭代过程中反复求值。
上面咱们通过一个例子来钻研一下表达式树对应的求值步骤时如何构建的。explain select (SQRT(POWER(i,i))) from generate_series(1,5) i; 首先，咱们看一下 PG 在内存中是如何示意表达式树的，以下面的查问为例，下述 FuncExpr 能够十分清晰的找出到 (SQRT(POWER(i,i))) 的对应关系。
| FuncExpr [funcid=1344 funcresulttype=701 funcretset=false funcvariadic=false funcformat=COERCE_EXPLICIT_CALL is_tablefunc=false] | |
| FuncExpr [funcid=1368 funcresulttype=701 funcretset=false funcvariadic=false funcformat=COERCE_EXPLICIT_CALL is_tablefunc=false] | |
| FuncExpr [funcid=316 funcresulttype=701 funcretset=false funcvariadic=false funcformat=COERCE_IMPLICIT_CAST is_tablefunc=false] | |
| Var [varno=1 varattno=1 vartype=23 varnosyn=1 varattnosyn=1] | |
| FuncExpr [funcid=316 funcresulttype=701 funcretset=false funcvariadic=false funcformat=COERCE_IMPLICIT_CAST is_tablefunc=false] | |
| Var [varno=1 varattno=1 vartype=23 varnosyn=1 varattnosyn=1] |
一般来说，求解这样的表达式树通常采纳递归计算的形式，先算底层表达式，再算高层表达式，整体相似于后序遍历树的过程。
PG 为了进步执行效率，抉择在执行阶段用投影求值的形式迭代执行，因而在执行初始化阶段须要采纳相似于后序遍历树的形式，将每个子表达式退出求值步骤数组中。
构建求值步骤的调用栈如下：
| -> ExecBuildProjectionInfo | |
| -> ExecInitExprSlots // EEOP_*_FETCHSOME | |
| ->ExprEvalPushStep | |
| for targetList: | |
| -> ExecInitExprRec(tle->expr,) | |
| scratch.resvalue = resv // 以后步骤的后果；下层通过指针传入咱们应该寄存的地址 | |
| case T_FuncExpr: | |
| -> ExecInitFunc // 以后函数 [funcid=1344] | |
| fcinfo = scratch->d.func.finfo | |
| for args: // 这层有一个参数 | |
| -> ExecInitExprRec(arg, state, &fcinfo->args[argno].value) // resv - where to stor the result of the node into | |
| case T_FuncExpr: | |
| -> ExecInitFunc // 以后函数 [funcid=1368] | |
| for args: // 这层有两个参数 | |
| -> ExecInitExprRec() | |
| case T_FuncExpr: | |
| -> ExecInitFunc // 以后函数 [funcid=316] | |
| for args: // 这层有一个参数 Var [varno=1 varattno=1 vartype=23 varnosyn=1 varattnosyn=1] | |
| -> ExecInitExprRec() | |
| case T_Var: | |
| // regular user column | |
| scratch.d.var.attnum = variable->varattno - 1; | |
| -> ExprEvalPushStep() | |
| ExprEvalPushStep() | |
| ExprEvalPushStep() | |
| ExprEvalPushStep() | |
| ExprEvalPushStep() | |
| scratch.opcode = EEOP_DONE; | |
| ExprEvalPushStep() |
整个过程的主体是对表达式树的递归遍历。表达式树通常两头蕴含若干个 T_FuncExpr 或其余类型的表达式节点，每个节点有若干个参数，参数可能同样是一个表达式，子节点求值步骤全副生成后，才将以后步骤生成放入数组；叶子节点通常是 T_Var 或者 T_Const，解决形式和投影统一。
本节重点介绍一下对于 T_FuncExpr 类型的步骤构建过程和之前没讲的非 fast_path 的表达式求值逻辑。次要蕴含两个函数：ExecInitExprRec 和 ExecInitFunc。
其中 ExecInitExprRec 是表达式求值的要害函数，也是递归调用产生的中央；代码会依据不同的表达式类型，调用不同的逻辑，每个分支依据具体的状况会递归调用 ExecInitExprRec，随后将以后步骤推入步骤数组 ExprEvalPushStep。其中，有一个很重要的步骤是 scratch.resvalue = resv，这样以后步骤计算实现的值就能够被下层调用者以传指针的形式传入（相当于下层表达式能够拿到子表达式的求值后果），从而将整个递归的计算过程串联起来。
ExecInitFunc 是对函数表达式类型计算的过程，因为比较复杂，写成了一个独立的函数。其次要逻辑是遍历以后函数的参数，别离通过调用 ExecInitExprRec 进行求值步骤的初始化；子表达式求值的后果则能够通过 &fcinfo->args[argno].value 获取；实现后，将以后函数的求值步骤推入步骤数组。
上述例子的理论求值过程如下，在前述的散发机制中顺次执行以下步骤即可：
| EEO_CASE(EEOP_SCAN_FETCHSOME) | |
| EEO_CASE(EEOP_SCAN_VAR) // scan i | |
| EEO_CASE(EEOP_FUNCEXPR_STRICT) // i4tod | |
| EEO_CASE(EEOP_SCAN_VAR) // scan i | |
| EEO_CASE(EEOP_FUNCEXPR_STRICT) // i4tod | |
| EEO_CASE(EEOP_FUNCEXPR_STRICT) // dpow | |
| EEO_CASE(EEOP_FUNCEXPR_STRICT) // dsprt | |
| EEO_CASE(EEOP_ASSIGN_TMP) // 将计算结果赋值到 resultslot | |
| EEO_CASE(EEOP_DONE) |
常量预计算优化
对于表达式树中的常量局部，咱们能够在优化阶段就计算好，防止反复求值。同样利用一个例子来探讨这个问题。在下述例子中，如果 POWER(2,3)能够在优化阶段即被替换为 8，那么在执行阶段，显然就能够防止反复计算 5 次 POWER(2,3)。
select i+POWER(2,3) from generate_series(1,5) i;
| -> preprocess_expression | |
| -> eval_const_expressions | |
| -> eval_const_expressions_mutator | |
| -> expression_tree_mutator (case T_List) | |
| -> eval_const_expressions_mutator | |
| -> expression_tree_mutator (case T_TargetEntry) | |
| -> eval_const_expressions_mutator (case T_OpExpr) | |
| -> simplify_function | |
| // 对表达式列表递归调用 eval_const_expressions_mutator | |
| -> args = expand_function_arguments() | |
| -> args = (List *) expression_tree_mutator(args,eval_const_expressions_mutator) | |
| -> evaluate_function // try to pre-evaluate a function call | |
| -> evaluate_expr // pre-evaluate a constant expression | |
| // 初始化表达式节点的执行状态信息 | |
| -> ExecInitExpr | |
| -> ExecInitExprSlots() // Insert EEOP_*_FETCHSOME steps as needed | |
| -> ExecInitExprRec() // 将执行步骤填入 ExprState->steps 数组 | |
| case T_FuncExpr: | |
| -> ExecInitFunc // 次要工作是将 argument 求值；并放入 state 的 list 中 | |
| foreach(lc, args) | |
| if IsA(arg, Const) | |
| fcinfo->args[argno].value = con->constvalue | |
| else | |
| ExecInitExprRec() // 递归对表达式参数求值 | |
| -> ExprEvalPushStep | |
| -> const_val = ExecEvalExprSwitchContext | |
| -> evalfunc() | |
| op = state->steps | |
| resultslot = state->resultslot | |
| outerslot = econtext->ecxt_outertuple | |
| EEO_DISPATCH() // goto op->opcode |
代码的外围逻辑在于通过 eval_const_expressions_mutator 和 express_tree_mutator 函数遍历表达式树；如果遇到 op_expr 则调用 simplify_function()->evaluate_function() 简化子表白树中的常量。
evaluate_function 会查看子表达式是否含有十分量；如果全是常量，则能够持续简化。
简化的过程本质就是将执行器阶段的求值过程提前至优化阶段：首先生成节点执行状态信息和求值步骤数组；而后调用 ExecEvalExprSwitchContext 依次执行；最初通过 makeConst 生成一个常量节点，替换原来简单的表达式子节点。
至此，咱们就系统地介绍了 PG 中对于投影和表达式计算的实现逻辑。投影在大部分状况下简直是一个必须的操作，为数不多的优化伎俩可能在于将下层算子的投影下推，不再展开讨论。
