💻 深耕数据库内核架构设计与开发十余年，曾主导多款高性能分布式数据库内核研发，攻克高并发、低延迟等核心技术难题。现倾力打造《从零手写数据库》系列教程，首次系统性公开数据库内核源码级实现细节！

一、概述 

对于每种操作符，目前都定义了一种算法，其它方法以后再进行扩展。

二、扫描算法 

采用顺序全表扫描算法，它还有重置扫描位置的接口。

ExecStateInfo seqScanStateInfo = {
    ExecSeqScan,
    ExecReSeqScan,
    NULL
};

前者是开始全表扫描，后者会重置扫描位置，这与之前的全表扫描类似。

三、联接算法 

联接操作一般是中间节点，主要处理子节点返回的结果。嵌套循环的方法是简单有效的一种算法，通过两层循环来遍历内外表，它只有一个主函数。

ExecStateInfo nestloopStateInfo = {
    ExecNestLoop,
    NULL,
    NULL
};

嵌套循环中外层循环调用左子节点执行函数，内层循环调用右子节点的执行函数，具体的执行流程如下：

1. 外层循环调用左子节点的执行函数，从外表中获得结果集；
2. 当左子节点执行的结果集为空时，结束执行；不为空时，设置标志重置内表的扫描信息，从头重新开始；
3. 在内层循环中调用右子节点的执行函数，从内表获取结果集；
4. 当右子节点的执行结果集为空时，内层循环结束，从步骤1重新开始；
5. 左右子节点执行的结果集加到列表当中，开始执行联接表达式；
6. 当表达式计算为真时，返回当前结果列表；如果表达式计算为假时，从步骤3继续内层循环；

Node* ExecNestLoop(Node *planNode)
{
    NestLoopNode *nlNode = (NestLoopNode*)planNode;
    Node *lresult = NULL, *rresult = NULL;
    List *resultList = NULL;
    int isJunk = 0;
    int isReScan = 0;
    
    /* outer */
    for( ; ; )
    {
        if(nlNode->lresult == NULL)
        {
            lresult = ExecNodeProc(nlNode->leftplan);
            if(lresult == NULL)
            {
                break;
            }
            
            nlNode->lresult = lresult;
            isReScan = 1;
        }
        else
            lresult = nlNode->lresult;

        /* inner */
        for( ; ; )
        {
            if (nlNode->rresult != NULL)
            {
                ; /* release rresult */
                nlNode->rresult = NULL;
            }            

            if(isReScan)
            {
                rresult = ExecNodeReProc(nlNode->rightplan);
                isReScan = 0;
            }
            else
                rresult = ExecNodeProc(nlNode->rightplan);
            if(rresult == NULL)
            {                
                break;            
            }
            nlNode->rresult = rresult;
            
            resultList = (List*)AppendList(resultList, lresult);
            resultList = (List*)AppendList(resultList, rresult);

            isJunk = ExecJoinExpr(nlNode, (Node*)resultList);
            if(isJunk)
            {
                return (Node*)resultList;
            }

            if(resultList != NULL)
            {
                ;/* release list */
            }
        }

        if (nlNode->lresult != NULL)
        {
            ; /* release lresult */
            nlNode->lresult = NULL;
        }
    }

    returnNULL;
}

嵌套循环算法最终执行结束的条件是，当外层表返回结果为空时结束。当前嵌套循环算法只实现了两表的笛卡尔积的运算，外联接、自然联接等在后面章节介绍，另外联接表达式也在后面章节介绍，这里恒为真。

四、投影算法 

投影操作符的执行函数，它一般作为最顶层执行函数，来处理最终结果集要包含的列数量。

ExecStateInfo projectStateInfo = {
    ExecProject,
    NULL,
    NULL
};

投影执行函数定义如下：

Node* ExecProject(Node *planNode)
{
    ProjectNode *prjPlanNode = (ProjectNode *)planNode;
    Node *result = NULL;

    result = ExecNodeProc(prjPlanNode->subNode);
    if(result == NULL)
        return NULL;

    result = FormTargetResult(prjPlanNode->targetList, result);
    /* target option process distinct/all */
    return result;
}

投影算法的执行流程：

1. 执行它的子节点，得到结果集；
2. 遍历节点记录的目标列，在结果集中查找对应的列数据值；
3. 将所有目标列的数据值拼成一个结果数据行，返回给上层调用者。 这里对于目标列属性标识暂时未作处理，待后面补充。

在下面函数中，对目标列的数据值的获取处理。

Node* FormTargetResult(Node *targetList, Node *resultList)
{
    List *tList = (List*)targetList;
    ListNode *tNode = NULL;
    TargetElement *te = NULL;
    ResultNode *resNode = NULL;
    char tempBuf[PAGE_MAX_SIZE] = {0};
    int offset = sizeof(TupleHeader);

    if(tList == NULL)
        returnNULL;
    
    for(tNode = tList->head; tNode != NULL; tNode = tNode->next)
    {
        te = (TargetElement*)tNode->value;
        
        /* get result by table name */
        resNode = GetResultNodeFromList(te, (List*)resultList);
        if(resNode == NULL)
        {
            printf("result is not found about attr %s.\n", ((ColumnName*)te->val)->sub_name);
            offset = 0;
            break;
        }

        /* get column by column name */
        offset += FetchColumnData(tempBuf + offset, te, resNode);
    }

    if(offset > 0)
    {
        resNode = NewNode(ResultNode);
        resNode->rel = NULL;
        resNode->tup = (TupleHeader*)malloc(offset);
        memcpy(resNode->tup, tempBuf, offset);
        resNode->tup->size = offset;
    }

    return (Node*)resNode;
}

查找目标列对应的数据值的流程：

1. 结果集可能由多张表的行数据构成，所以目标列中记录了扫描表的信息，同时结果集中也记录扫描表的信息；
2. 首先找到目标列对应的扫描表，每个扫描表会对应一行结果数据；
3. 根据数据表的属性列元数据信息，找到行数据的对应字段值；
4. 将字段值记录到结果数据行对应位置。

五、选择算法 

当表达式计算结果为真时，才返回当前行结果。

ExecStateInfo selectStateInfo = {
    ExecSelect,
    NULL,
    NULL
};

选择操作主要将结果集代入表达式中，根据表达式的真假来选择当前结果是否需要返回给客户端。

Node* ExecSelect(Node *planNode)
{
    SelectNode *selectPlanNode = (SelectNode *)planNode;
    Node *result = NULL;
    int isJunk = 0;

    do {
        if(result != NULL)
            ReleaseResultNode(result);

        result = ExecNodeProc(selectPlanNode->subNode);
        if(result == NULL)
            break;

        isJunk = ExecJunkResult(selectPlanNode->expr, result);
    }while(isJunk == 0);

    return result;
}

表达式的计算在后面章节介绍，所有这里的选择处理时返回永真。

六、总结 

本节新增接口定义在excutor.c文件中，位置exam_46目录下。