@H_403_245@ 图表 1：exec_simple_query总体流程
如图所示， exec_simple_query函数主要调用了PortalStart,PortalRun,PortalDrop 三个函数。PortalStart 主要做一些初始化准备工作， PortalDrop是在进行查询完毕之后的释放相关资源相关的等结尾工作。和我们项目相关的重点在PortalRun。
在PortalRun中，函数根据portal->strategy选择不同的语句执行策略，属于哪种情况，对于所给示例代码，属于PORTAL_ONE_SELECT分支，这样就调用PortalRunSelect函数开始处理，最后返回处理过的元组。
在PortalRunSelect函数中，进一步调用了ExecutorRun，它是查询处理的关键函数，查询执行器的核心功能都是在这个函数中处理完成。
ExecutorRun它主要是通过调用ExecutePlan，将按照查询规划处理之后的返回值赋给结果变量result。而ExecutePlan函数则是按照生成的查询规划树开始执行相应处理。
在ExecutePlan内部，递归遍历执行计划树，即调用ExecProcNode函数处理规划树上的每个节点，每次返回一个元组放入slot中去，如果返回元组为空则退出循环。每得到一个元组，根据其查询 *** 作的类型对该元组进行相应处理，在我们的语句，属于CMD_SELECT情况，会继续调用到ExecSelect函数将以个slot赋给result。
其中ExecProcNode函数是我们要重点分析和修改的部分。它处理一个规划树上的节点，并返回一个tuple。至此开始，它要开始循环调用自身，不断根据不同节点类型进行不同的处理。条件判断在一进入该函数时进行，在所给的示例语句中，计划树的结构如下图所示：
图表 2：示例语句的计划树结构
从上图可以看出，首先节点类型为T_limitState，这样就会调用Execlimit函数来处理。该函数我们将继续作为重点在下一张流程图中作分析。
在Execlimit中，将再次调用ExecProcNode函数，这时，它的左子节点是一个T_SortState类型，所以将会调用ExecSort函数进行排序，这个函数也是我们重点修改的，我们后面会单拿出来进行详细分析。
而ExecSort也会调用其子结点T_SeqScan的ExecSeqScan来执行，这个函数不是我们关注的重点，故可以略过。
2.3 ExecLimit详细分析 2.3.1 Execlimit关键代码及注释 @H_404_881@ TupletableSlot * Execlimit(limitState *node) /* return: a tuple or NulL */
{
TupletableSlot *slot;
PlanState *outerPlan;
/／获取子计划结点
outerPlan = outerPlanState(node);
/*
* Execlimit状态变化及运动的逻辑主体
*/
switch (node->lstate)
{
case liMIT_INITIAL: //处理offset限制
/／计算limit_count和offset等数据
recompute_limits(node);
/／判断参数是否合法
if (node->count <= 0 && !node->noCount)
{
node->lstate = liMIT_EMPTY;
return NulL;
}
/／处理至offset
for (;;)
{
/*这里开始了第一次递归调用，在此递归调用中，会引有子计划结点的执行
根据我们的示例select * from teacher order by name limits 2 offset 1
和图1,其子计划结点为T_SortState在即将运行的ExecProcNode中,将会运行 result = ExecSort((SortState *) node);
*/
slot = ExecProcNode(outerPlan);
if (TupIsNull(slot))
{
//如果子计划返回的元组为空,即元组不够
node->lstate = liMIT_EMPTY;
return NulL;
}
……
}
/*
* 我们已经通过执行子结点,获取了正确的元组,将状态修改为liMIT_INWINDOW
*/
node->lstate = liMIT_INWINDOW; //接下来返回的原组是满足要求的。
break;
}
case liMIT_INWINDOW:
/*
* Get next tuple from subplan,if any.
*/
slot = ExecProcNode(outerPlan);
//取出一下排序好的结点
//注意：outerPlan中有sort_Done标明已经排序完毕
//只是需要返回相应位置的值即可
if (TupIsNull(slot))
{
//没有成功取完就退出了。
node->lstate = liMIT_SUBPLANEOF;
return NulL;
}
node->subSlot = slot;
node->position++; //指到下一个该取的位置
}
else //逆向扫描的情况
{
}
break;
case liMIT_EMPTY: //状态机结束
/*
* The subplan is kNown to return no tuples (or not more than
* OFFSET tuples,in general). So we return no tuples.
*/
return NulL;
case liMIT_SUBPLANEOF:
……
break;
case liMIT_WINDOWEND:
……
case liMIT_windowsTART:
……
default:
……
break;
}
return slot;
@H_419_1966@}
图表 3：Execlimit关键代码及注释
2.3.2 Execlimit流程分析与描述 Execlimit函数首先判断节点状态，根据不同的执行状态进入不同的分支。
当第一次进入该函数时，为liMIT_INITIAL，调用recompute_limits函数来计算limit/offset的值，并将position参数置0。然后开始循环调用ExecProcNode函数，处理子规划的结点，知道节点的position超过了offset值，这样得到了从offset设定的开始位置的一个元组，并将node->lstate修改为liMIT_INWINDOW。
当node->lstate是liMIT_EMPTY情况时，则返回。
当node->lstate为liMIT_INWINDOW情况。表示元组在我们的处理窗口中，从liMIT_INWINDOW状态的元组开始，我们调用ExecProcNode陆续从子规划中得到tuple。如果节点状态变为了liMIT_WINDOWEND，则退出，返回空值。Execlimit函数每次返回一个slot给它的上层调用者。
后面的状态与我们的流程关系不大，故省略。
2.3.3 Execlimit流程图解 由上面的分析，我们可以大致得到以下的流程图：
图表 4：Execlimit流程图解
在Execlimit中递归调用子结点的ExecProcNode，在此时的ExecProcNode中，会调用ExecSort。下面我们就继续分析分析这个重要的函数。
2.4 ExecSort详细分析 2.4.1 ExecSort关键代码及注释 @H_404_881@ TupletableSlot *ExecSort(SortState *node)
{
EState *estate;
Tuplesortstate *tuplesortstate;
TupletableSlot *slot;
/／获取执行状态
estate = node->ss.ps.state;
tuplesortstate = (Tuplesortstate *) node->tuplesortstate;
/／如果还没有排序，则排序
if (!node->sort_Done)
{
tuplesortstate = tuplesort_begin_heap(tupDesc,plannode->numCols,plannode->sortoperators,
plannode->sortColIDx,work_mem,node->randomAccess); //分配空间
／／下面的循环是调用其子计划结点来获取待排序的元组，在示例语句中，此子计划为T_SeqScan类型，由ExecSeqScan来执行
for (;;)
{
slot = ExecProcNode(outerNode);
//在这里outerNode是一种方法取出数据库中数据，比方说ExecSeqScan() 方式
//运行：每一次从outerNode返回一个元组
if (TupIsNull(slot))
break;
tuplesort_puttupleslot(tuplesortstate,slot); //放入刚取出的元组
//如果放入元素量巨大，有可能演变成外排序中的顺串
}
//完成排序
tuplesort_performsort(tuplesortstate); //分为内排序（快速排序）和外排序两种情况
……
}
slot = node->ss.ps.ps_ResultTupleSlot;
//返回一个排序后的元组，关键的是puttuple_common()函数的实现
(voID) tuplesort_gettupleslot(tuplesortstate, ScanDirectionIsForward(dir), slot);
return slot;
@H_419_1966@}
图表 5：ExecSort关键代码及注释
2.4.2 ExecSort流程分析与描述 这个函数执行流程比较简单，当执行状态为“node->sort_Done”时执行排序，排序前先调用子计划结点以获取元组，在示例语句中，此子计划为T_SeqScan类型，由ExecSeqScan来执行。当准备好待排序数据之后，调用tuplesort_performsort来完成排序。
2.4.3 ExecSort流程图解 ExecSort流程图解如下图：
图表 6：ExecSort流程图解
在流程图中可以发现，tuplesort_performsort是完成排序模块，下面对其进行分析。
2.5 tuplesort_performsort详细分析 2.5.1 tuplesort_performsort关键代码及注释 @H_404_881@ voID tuplesort_performsort(Tuplesortstate *state)
{
MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
switch (state->status)
{
case TSS_INITIAL:
//如果有足够的内存来完成排序，则直接在内存中调用快速排序来完成
if (state->memtupcount > 1)
qsort_arg((voID *) state->memtuples,
state->memtupcount,
sizeof(SortTuple),
(qsort_arg_comparator) state->comparetup,
(voID *) state);
state->current = 0; //output run number，初始值为
//以下两个信息是对游标信息的设置
state->eof_reached = false;
state->markpos_offset = 0;
state->markpos_eof = false; //是否提前结束
state->status = TSS_SORTEDINMEM;
break;
case TSS_buildrUNS:
//否则进入外排序分支
dumptuples(state,true); //把内存所有的元组归位
mergeruns(state); //完成后状态机设置为TSS_FINALMERGE
//如果在内存中只有一个tape,设置状态为state->status = TSS_SORTEDONTAPE;
// TSS_FINALMERGE;
state->eof_reached = false;
state->markpos_block = 0L ;
state->markpos_offset = 0;
state->markpos_eof = false;
break;
default:
elog(ERROR,"invalID tuplesort state");
break;
}
MemoryContextSwitchTo(oldcontext);
}
图表 7:tuplesort_performsort关键代码及注释
2.5.2 tuplesort_performsort流程分析与描述 此函数的流程也很简单，在进行上下文切换之后，判断执行状态，如果是TSS_INITIAL则表示已经有足够的内存可以放置待排序元组，且已经把数据准备好，直接调用快速排序即可完成。如果TSS_buildrUNS，则进入外排序分支。
2.5.3 tuplesort_performsort 流程图解
图表 8：tuplesort_performsort 流程图解
2.6 重要的数据结构分析 在我们比较详细的分析的函数ExecProcNode(PlanState *node) 、Execlimit(limitState *node) 、ExecSort(SortState *node) 、tuplesort_performsort(Tuplesortstate *state)中，其入口参数分别对应着PlanState、limitState、SortState、Tuplesortstate。下面就其一些相对重要的成员做更深一步的分析。
2.6.1 P lanState @H_404_881@ //执行计划的状态结点
typedef struct PlanState
{
NodeTag type;
Plan *plan; /* 查询计划结点*/
EState *state; /* 执行状态*/
……
struct PlanState *lefttree; /* 左子计划结点：输入 */
struct PlanState *righttree;
List *subPlan; /* SubPlanState nodes in my Expressions */
……
@H_419_1966@} PlanState;
图表 9：PlanState关键代码及注释
@H_419_1966@ PlanState关键的变量即为以上几个。其中第一个域是NodeTag，说明他继承自己Node，后面用组合的方式来获得Plan和Estate的功能，因为PlanState正是两者的结合。 2.6.2 limitState @H_404_881@ typedef enum
{
liMIT_INITIAL, /* initial state for liMIT node */
liMIT_EMPTY, /* there are no returnable rows */
liMIT_INWINDOW, /* have returned a row in the window */
liMIT_SUBPLANEOF, /* at EOF of subplan (within window) */
liMIT_WINDOWEND, /* stepped off end of window */
liMIT_windowsTART /* stepped off beginning of window */
} limitStateCond;
typedef struct limitState
{
PlanState ps; /* its first fIEld is NodeTag */
ExprState *limitOffset; /* OFFSET parameter,or NulL if none */
ExprState *limitCount; /* COUNT parameter,or NulL if none */
int64 offset; /* current OFFSET value */
int64 count; /* current COUNT,if any */
bool noCount; /* if true,ignore count */
limitStateCond lstate; /* state machine status,as above */
int64 position; /* 1-based index of last tuple returned */
TupletableSlot *subSlot; /* tuple last obtained from subplan */
@H_419_1966@} limitState;
图表 10：limitState关键代码及注释
第一个枚举为limit结点的一些执行状态。从limitState的成员中可以看出，limitState的第一个域是PlanState，说明其继承自PlanState,这也是为什么ExecProcNode能递归运行的原因，是Postgresql用C语文实现了结构体的伪继承，从而实现了基类与派生类的指针转换，Postgresql中的伪继承机制在ExecProcNode中体现的淋漓尽致。在最后一章我们将再会探讨此技术。
@H_911_4194@2.6.3 @H_911_4194@SortState @H_404_881@ /* ----------------
* SortState information
* ----------------
*/
typedef struct SortState
{
ScanState ss; /* its first fIEld is NodeTag */
bool randomAccess; /* need random access to sort output? */
bool sort_Done; /* sort completed yet? */
voID *tuplesortstate; /* private state of tuplesort.c */
@H_419_1966@} SortState;
图表 11：SortState 关键代码及注释
从第一个域中可以看出，SortState继承自ScanState，其他三个成员也容易理解。第二个指示是否已经完成排序，tuplesortstate为其排序要用到的一些参数。
2.6.4 Tuplesortstate 这个数据结构比较复杂，我们摘其要点列表如下：
@H_404_881@ //nodeSort.c
struct Tuplesortstate
{
TupSortStatus status; /* enumerated value as shown above */
int nKeys; /* number of columns in sort key */
bool randomAccess; /* dID caller request random access? */
long availMem; /* remaining memory available,in bytes */
long allowedMem; /* total memory allowed,in bytes */
int maxTapes; /* number of tapes (knuth's T) */
int tapeRange; /* maxTapes-1 (knuth's P) */
MemoryContext sortcontext; /* memory context holding all sort data */
/*
排序用到的各种函数
*/
int (*comparetup) (const SortTuple *a,const SortTuple *b,
Tuplesortstate *state);
voID (*copytup) (Tuplesortstate *state,SortTuple *stup,voID *tup);
voID (*writetup) (Tuplesortstate *state,int tapenum,
SortTuple *stup);
voID (*readtup) (Tuplesortstate *state,
int tapenum,unsigned int len);
……
//下面还有一些内排序和外排序需要用到的一些数据。
@H_419_1966@};
图表 12：Tuplesortstate关键代码及注释
2.7 外存处理流程分析 在tuplesort_performsort(Tuplesortstate *state)中，switch (state->status)时，当case TSS_buildrUNS:时，会进入外存处理分支。在此分支中，调用mergeruns来完成外排序。这个函数实现了knuth的〈计算机程序设计艺术〉中的多阶段合并算法，下面讨论一下多阶段合并算法及其在Postgresql中的实现流程。
2.7.1 多阶段合并算法 此算法的具体思想在书中中文版本第二版第三卷的220页，读者可以参阅。
其大致流程如下图所示：
图表 13：多阶段合并算法流程示意图
算法步骤的描述简要如下：
图表 14：多阶段合并算法算法步骤
2.7.2 P ostgresql中多阶段合并算法实现流程 mergeruns实现了多阶段算法中的D5与D6步，因为此前的ExecSort在tuplesort_performsort之前，就已经调用tuplesort_puttupleslot准备好了初始顺串。其完成的流程是：tuplesort_puttupleslot调用puttuple_common，而puttuple_common在case TSS_buildrUNS:分支中调用tuplesort_heap_insert来完成的。
回到，mergeruns，在mergeruns中，会调用beginmerge(Tuplesortstate *state)来从外存中获取元组数据放入到内存中进行归并排序。
在beginmerge(Tuplesortstate *state)中，每次只取一个元组进行归并。如果我们能知道需要排序的项数，则可以在这个函数中去控制拿的项数，以减少访外的次数。 总结 以上是内存溢出为你收集整理的PostgreSQL源码修改 ——查询优化（二）全部内容，希望文章能够帮你解决PostgreSQL源码修改 ——查询优化（二）所遇到的程序开发问题。
如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。
微信扫一扫
支付宝扫一扫
评论列表（0条）