火山模型

履行器各个算子解耦合的基础。关于每个算子来说,只要三步:

  1. 向自己的孩子拿一个 tuple。即调用孩子节点的 Next 函数;

  2. 履行核算;

  3. 向上层回来一个 tuple。即当时节点 Next 函数的回来成果。

深入浅出openGauss的执行器基础

所以整个履行器的内核能够用下面这个伪代码来表达。

ExecutePlan
{
for (;;)
slot = ExecProcNode(planstate);
------->if (node->chgParam != NULL)
           ExecReScan(node);
        result= g_execProcFuncTable[index](node)  // 表驱动,每个算子不同的履行函数
        return result;
if (TupIsNull(slot)) {
   ExecEarlyFreeBody(planstate);
   break;
}
// 回来给前端
}

这种模型的好处是:

  1. 规划简略,算子解耦,互相不依赖;

  2. 内存运用量小,没有物化的情况下,每次只耗费一个 tuple 的内存。

Tuple 数据结构规划

两个算子之间的传递的都是 tuple。所以 Tuple 数据结构是整个履行器的中心,也是履行器和存储引擎交互的数据结构。

先看下几个详细数据结构之间的联系(附上关键的变量,非悉数)

// 存在磁盘上的数据结构,是 header + 数据 的一片接连内存。规划要求尽或许紧凑,节省存储空间。
// 只要业务信息等,其它比方长度、每一列开端地址等都不会直接存,而是算出来的。
HeapTupleHeaderData
    t_xmin; // 业务信息
    t_xmax;
    t_cid;
    t_ctid;
    ...
// 磁盘上的 Tuple 数据结构过于紧凑,不好用。所以规划了内存中一个 tuple 的目标,会存一些额外(冗余)的元数据信息方便处理。
// 数据和元数据能够不接连。这个数据结构一般是存储引擎内部用,比方可见性判别等。   
HeapTupleData
    t_len; // 数据长度
    tupTableType;// store 类型
    t_self; // ctid
    t_tableOid;
    ...
    HeapTupleHeader t_data;  // tuple header data 的地址
// 能够理解为 Tuple 槽位,履行器用。存储引擎不关心详细每一列的内容,只关心业务、长度等公共信息。
// 而履行器或许需求拜访每一列,所以在这里把 tuple 进一步拆解开。
TupleTableSlot
    Tuple tts_tuple;   // 物理 tuple 方位(HeapTupleData);虚拟 tuple 的话为 null。
    TupleDesc tts_tupleDescriptor;
    Buffer tts_buffer;
    Datum* tts_values; // 数组,表明每一列的值(假如是 int 便是值,假如是 varchar 便是地址)
    bool* tts_isnull;  // 数组,表明每一列是否是 null
    TableAmType tts_tupslotTableAm  // 处理物理 tuple 的函数(astore 和 ustore 不同)

以上图为例,最基层的 seqscan,会调用存储引擎的heap_getnext函数(astore)。

// 代码顶用的函数指针,实践调用栈如下
ExecScanFetch
--->SeqNext
--------->seq_scan_getnext_template    // 存储引擎入口
                 tuple =  (Tuple)heap_getnext  // 拿到 HeapTuple
                 // 组装TupleTableSlot,可是 attr 的值还没置上,得在 heap_slot_getattr 里设置。
                 heap_slot_store_heap_tuple(htup, slot, scan->rs_cbuf, false, false); 
heap_getnext
   ---> heapgettup
              HeapTuple tuple = &(scan->rs_ctup);   // tuple 是 scan 结构体中的变量。
              LockBuffer(scan->rs_base.rs_cbuf, BUFFER_LOCK_SHARE);  // 锁住 buffer
              dp = (Page)BufferGetPage(scan->rs_base.rs_cbuf);
              lpp = HeapPageGetItemId(dp, line_off);
              tuple->t_data = (HeapTupleHeader)PageGetItem((Page)dp, lpp);  // t_data 的地址便是 buffer 中的地址
              ItemPointerSet(&(tuple->t_self), page, line_off);  // 设置 tuple 中的一些变量
              valid = HeapTupleSatisfiesVisibility(tuple, snapshot, scan->rs_base.rs_cbuf);  // 用作可见性判别
        return  &(scan->rs_ctup);
// 把物理 tuple 中的数据,仿制到 tupleTableSlot 中。这里是 astore 的解析函数,ustore 不一样。
heap_slot_getattr
    // 中心思想是运用 TupleDesc 知道表的界说,然后从0 开端一个 attr 一个 attr 地解析。
    // 关于定长字段,直接按地址取值;关于变长字段,长度会存在原始的数据头中。
    // 因而,之前的物理 tuple 不需求存长度这种信息;同时,也需求 tupleTableSlot 这样的变量来缓存详细数据的开端地址。

以上便是存储引擎和履行引擎之间 tuple 怎样交互的。总结下便是存储引擎会把实践数据地点的地址传给上层,终究履行引擎拿到的结构体为TupleTableSlot。

所以,履行引擎只关心TupleTableSlot这一个结构体即可。

一个很自然的问题便是,假如算子之间的 Tuple 都是深仿制传递,关于较大的 tuple 来说(包含 varchar 类型),功能很差。因而,PG 中的 tuple 分了4类(详见头文件tuptable.h):

  1. 第一类 tuple 是 Disk buffer page 上的 physical tuple,便是前文的 HeapTuple。Buffer 一定要 pin 住。这种 Tuple 能够直接根据头地址进行拜访。

  2. 内存中的组装的tuple,格式和文件上 tuple 彻底一样,也是进行过紧缩。这种也算是 physical tuple,能够直接用地址。

  3. Minimal physical tuple,也是内存中的,仅有区别在于没有体系列(xmin、xmax 等)。

  4. virtual tuple,只记载每一个属性数据的地址,并没有深仿制,而是直接经过地址来拜访。现在约定的是,当一个算子向上层吐一个 tuple,直到它下次被调用时,该tuple地点的内存不会被开释。

关于查询来说,第一类和第四类最为常见。2、3两类会在物化的时候运用,比方 CTEScan、HashJoin 树立 hash 表的时候,相当于深仿制。功能比较敏感的场合,尽量避免2、3类 tuple的运用。

slot 的创立一般经过ExecAllocTableSlot、ExecSetSlotDescriptor两个函数来分配内存和初始化信息。在履行器初始化阶段,每个算子会分配相应的 slot。

以上图为例,

  1. SeqScan 算子有一个 tupleTableSlot,是一个 physical tuple,指向的是 Buffer 中的地址。

    向上层回来自己的 tuple slot;

  2. HashJoin 一个一个拿到 内表的 tuple slot,需求树立 hash 表,所以创立了一个 minimal physical tuple,仿制内表的 tuple 内容;

  3. Hash表树立后,HashJoin 算子然后一个一个拿到表面的 tuple slot,做 join 核算。

    HashJoin 自己有一个 tuple slot,假如碰到匹配,则把自己的 tuple slot 设置成 virtual tuple,其间的 tts_values 指向的是孩子节点的 tuple 中的地址。

    再向上回来。

    其间,表面的内容指向的是 Buffer 上的physical tuple, 内表的内容指向的是 hash 表中的 minimal physical tuple;

  4. 当 HashJoin 被再次调用时,它会重置 tuple slot。由于是 virtual tuple,所以没做任何事情。然后 HashJoin 会调用 SeqScan 拿下一条tuple;

  5. SeqScan 被再次调用时,也会重置 tuple slot。

    由于是 physical tuple,它需求开释之前的 Buffer。

    (当然,假如一向是同一个 Buffer 不会反复 pin/unpin,这是存储引擎的优化)。

条件核算

Expr 和 Var

履行器每个算子会对底下传上来的 tuple 进行核算和过滤。比方 NestLoop 需求核算内表面传上来的 tuple 是否满足 join 条件。

这时候需求引出第二个重要的概念,表达式的笼统。个人理解,任何对数据的获取操作都能够认为是表达式。

Var/Const 也是表达式的一种。Var 表明直接从 tuple 中获取数据,Const 表明的是直接获取一个常数。

每一个表达式会对应一个 ExprContext,ExprContext 中会记载核算所需求的一切数据,一般是孩子节点回来的 tuple。

表达式自身,在履行器顶用 ExprState 来表明。里边重点是表达式的核算函数

// 由于当时履行模型中,每个算子最多只要两个孩子节点,所以下面三个变量用的最多。
struct ExprContext {
    TupleTableSlot* ecxt_scantuple;  // scan 算子会用到
    TupleTableSlot* ecxt_innertuple;   // 非 scan 算子如 join
    TupleTableSlot* ecxt_outertuple;
    ...
}
// 表达式核算的结构体
struct ExprState {
    Expr* expr;  // 原始的表达式
    ExprStateEvalFunc evalfunc;  // 表达式对应的函数
}
// 履行器开端阶段,会经过优化器传过来的 Expr,初始化 ExprState 结构
ExecInitExpr {
    case T_Var:
        ExecInitExprVar
            state = (ExprState *)makeNode(ExprState);
            state->evalfunc = ExecEvalScalarVar;  // 内部实现是直接去取对应 tuple slot 上的 attr
    case T_OpExpr:
        FuncExprState* fstate = makeNode(FuncExprState);
        fstate->xprstate.evalfunc = (ExprStateEvalFunc)ExecEvalOper; // 内部实现是先递归调用 ExecEvalExpr, 获取参数列表,再调用 function
        fstate->args = (List*)ExecInitExpr((Expr*)opexpr->args, parent);
}

总结下,ExprState结构体表明表达式核算的逻辑,ExprContext结构体表明的是表达式核算要用到的数据。

从 OpExpr 能够看出,ExprState 自身也是一棵树。一向递归调用 ExecEvalExpr 来获取终究的成果。

需求留意的是,履行树中除了叶子节点上的扫描节点,其它节点的数据都来源于孩子节点。

所以,这些核算节点上的 Var,不能直接指向某个 table,而是需求指向的是内表还是表面的 tuple slot。

因而,在优化器终究的阶段,set_plan_refs函数中,会把中间节点的 Var 的 varno 改写成特定的值。

而 Var 的表达式处理函数ExecEvalScalarVar也是根据这个信息决定去找 ExprContext 中的 哪个 tuple slot。

深入浅出openGauss的执行器基础

表达式如下:

深入浅出openGauss的执行器基础

示例1 filter

以 SeqScan 为例,在优化器阶段, SeqScan 上会有一个 qual,表明过滤条件。在履行器阶段会生成一个对应的 ExprState,用于核算。

// 履行器初始化阶段,会根据优化器里的 Expr 构造 ExprState
ExecInitSeqScan
    InitScanRelation
        node->ps.qual = (List*)ExecInitQualWithTryCodeGen((Expr*)node->ps.plan->qual, (PlanState*)&node->ps, false);
// 履行阶段
ExecSeqScan
    ExecScan
        qual = node->ps.qual;
        slot = ExecScanFetch(node, access_mtd, recheck_mtd);  // 从存储引擎那里拿到 slot
        econtext->ecxt_scantuple = slot;   // 设置好 ExprContext
        ExecNewQual(qual, econtext)   // 调用 ExprState 进行核算
            ret = ExecEvalExpr((ExprState*)qual, econtext, &isNull, NULL);
            return DatumGetBool(ret);

示例2 join

以 Nestloop 为例,优化器结束的时候,join 节点会有一个 joinqual 表明 join 条件。

ExecInitNestLoop
    nlstate->js.joinqual = (List*)ExecInitQualWithTryCodeGen((Expr*)node->join.joinqual, (PlanState*)nlstate, false);
ExecNestLoop
    // 拿到内表面的 tuple slot,设置在 ExprContext 上
    econtext->ecxt_innertuple =ExecProcNode(inner_plan); 
    econtext->ecxt_outertuple = ExecProcNode(outer_plan);
    List* joinqual = node->js.joinqual;
    // 调用 ExprState 中的函数,假如契合 join 条件,则向上层回来一个 tuple。
    if (ExecNewQual(joinqual, econtext)) {
        result = ExecProject(node->js.ps.ps_ProjInfo, &is_done);
        return result
    }

示例3 index scan & index only scan

# Index on t(a,b,c)
# select a,b,c from t where a = 1 and c = 1;
 Index Only Scan using t_a_b_c_idx on t  (cost=0.15..8.26 rows=1 width=12)
   Index Cond: ((a = 1) AND (c = 1))
# select a,b,c from t where a = 1 and c <> 1;
 Index Only Scan using t_a_b_c_idx on t  (cost=0.15..32.35 rows=10 width=12)
   Index Cond: (a = 1)
   Filter: (c <> 1)
# select * from t where a = 1 and c <> 1 and d = 1;
 Index Scan using t_a_b_c_idx on t  (cost=0.15..32.36 rows=1 width=16)
   Index Cond: (a = 1)
   Filter: ((c <> 1) AND (d = 1))

之前很多人搞不清楚这里边 index cond/ filter 是什么联系。可是,经过履行器源码很容易得知它们的用处。先看 IndexOnlyScan

## 首先,经过 Explain 能够看出来,Index Cond 显示的是  plan->indexqual,  Filter 显示的是 plan->qual。
optutil_explain_proc_node:
    caesT_IndexOnlyScan:
       optutil_explain_show_scan_qual(((IndexOnlyScan *)plan)->indexqual, "Index Cond", planstate, ancestors, es);
       optutil_explain_show_scan_qual(plan->qual, "Filter", planstate, ancestors, es);
## 经过 Init 函数,发现 这两个 qual 分别被初始化为 Expr,赋给 ss.ps.qual 和 indexqual 上面。
ExecInitIndexOnlyScan
    indexstate->ss.ps.qual = ExecInitExpr((Expr *) node->scan.plan.qual,  (PlanState *) indexstate);
    indexstate->indexqual = (List *) = ExecInitExpr((Expr *) node->indexqual, 
    // 用 indexqual 来做Scan 的key
    ExecIndexBuildScanKeys((PlanState *) indexstate,
                           indexstate->ioss_RelationDesc,
                           node->indexqual.... 
## 在履行的时候发现,indexqual 在索引扫描内部运用, ps.qual 是用在扫描之后的 check 中。
ExecIndexOnlyScan
--->ExecScan
         qual = node->ps.qual;  // 留意,这里用的是 qual。
         slot = ExecScanFetch(node, accessMtd, recheckMtd);
                   ----> IndexOnlyNext
                                tid = index_getnext_tid(scandesc, direction)  // 调用 btree 相关函数
                                // 用 IndexTuple 来填充 scan  的 slot (IndexScan是根据 tid 回表去 heap 上读取)
                                StoreIndexTuple(slot, scandesc->xs_itup, scandesc->xs_itupdesc);
        // 用 qual 做过滤条件
         if (!qual || ExecQual(qual, econtext, false))
                回来 slot
btgettuple
    _bt_steppage
        _bt_readpage  
            _bt_checkkeys  // 每个页面会挨个检查一下 ScanKey 的条件是否满足

总结:

  • Index Cond 是用来做 btree 扫描的 key,定位到第一个 IndexTuple。存储引擎顶用

  • 之后索引扫描会顺着 btree 的链表扫描一切的叶子页面,对叶子页面上的每一个 tuple 用 ScanKey 检查是否满足条件,满足再回来

  • Filter 是在 履行器层用,针对 HeapTuple 再做一次过滤

  • IndexOnlyScan 和 Index Scan的仅有区别是,IndexOnlyScan 的HeapTuple是根据IndexTuple直接构建的,不需求回表,其它逻辑是一样。

  • 所以理论上讲 IndexOnlyScan 不应该呈现 filter,上述场景或许有改进空间。