本节介绍排序的实现,排序的实现函数是ExecSort,与聚合函数类似,也有要一个初始化的过程ExecInitSort,本节主要介绍该函数的实现. 下面是测试SQL执行排序的计划树: ``` ",,,,,"select bh,c1 from t_sort order by t_sort;",,,"psql" 2019-05-17 15:12:42.494 CST,"xdb","testdb",1519,"[local]",5cde5e9e.5ef,15,"SELECT",2019-05-17 15:11:26 CST,3/10,0,LOG,00000,"plan:"," {PLANNEDSTMT :commandType 1 :queryId 0 :hasReturning false :hasModifyingCTE false :canSetTag true :transientPlan false :dependsOnRole false :parallelModeNeeded false :jitFlags 0 :planTree {SORT :startup_cost 14142.82 :total_cost 14392.82 :plan_rows 100000 :plan_width 66 :parallel_aware false :parallel_safe true :plan_node_id 0 :targetlist (... ) :qual <> :lefttree {SEQSCAN :startup_cost 0.00 :total_cost 1736.00 :plan_rows 100000 :plan_width 66 :parallel_aware false :parallel_safe true :plan_node_id 1 :targetlist (... ) :qual <> :lefttree <> :righttree <> :initPlan <> :extParam (b) :allParam (b) :scanrelid 1 } :righttree <> :initPlan <> :extParam (b) :allParam (b) :numCols 1 :sortColIdx 3 :sortOperators 2990 :collations 0 :nullsFirst false } :rtable (... ) :resultRelations <> :nonleafResultRelations <> :rootResultRelations <> :subplans <> :rewindPlanIDs (b) :rowMarks <> :relationOids (o 278567) :invalItems <> :paramExecTypes <> :utilityStmt <> :stmt_location 0 :stmt_len 40 } ",,,,,"select bh,c1 from t_sort order by t_sort;",,,"psql" ``` ### 一、数据结构 **SortState** 排序运行期状态信息 ``` /* ---------------- * SortState information * 排序运行期状态信息 * ---------------- */ typedef struct SortState { //基类 ScanState ss; /* its first field is NodeTag */ //是否需要随机访问排序输出? bool randomAccess; /* need random access to sort output? */ //结果集是否存在边界? bool bounded; /* is the result set bounded? */ //如存在边界,需要多少个元组? int64 bound; /* if bounded, how many tuples are needed */ //是否已完成排序? bool sort_Done; /* sort completed yet? */ //是否使用有界值? bool bounded_Done; /* value of bounded we did the sort with */ //使用的有界值? int64 bound_Done; /* value of bound we did the sort with */ //tuplesort.c的私有状态 void *tuplesortstate; /* private state of tuplesort.c */ //是否worker? bool am_worker; /* are we a worker? */ //每个worker对应一个条目 SharedSortInfo *shared_info; /* one entry per worker */ } SortState; /* ---------------- * Shared memory container for per-worker sort information * per-worker排序信息的共享内存容器 * ---------------- */ typedef struct SharedSortInfo { //worker个数? int num_workers; //排序机制 TuplesortInstrumentation sinstrument[FLEXIBLE_ARRAY_MEMBER]; } SharedSortInfo; ``` **TuplesortInstrumentation** 报告排序统计的数据结构. ``` /* * Data structures for reporting sort statistics. Note that * TuplesortInstrumentation can't contain any pointers because we * sometimes put it in shared memory. * 报告排序统计的数据结构. * 注意TuplesortInstrumentation不能包含指针因为有时候会把该结构体放在共享内存中. */ typedef enum { SORT_TYPE_STILL_IN_PROGRESS = 0,//仍然在排序中 SORT_TYPE_TOP_N_HEAPSORT,//TOP N 堆排序 SORT_TYPE_QUICKSORT,//快速排序 SORT_TYPE_EXTERNAL_SORT,//外部排序 SORT_TYPE_EXTERNAL_MERGE//外部排序后的合并 } TuplesortMethod;//排序方法 typedef enum { SORT_SPACE_TYPE_DISK,//需要用上磁盘 SORT_SPACE_TYPE_MEMORY//使用内存 } TuplesortSpaceType; typedef struct TuplesortInstrumentation { //使用的排序算法 TuplesortMethod sortMethod; /* sort algorithm used */ //排序使用空间类型 TuplesortSpaceType spaceType; /* type of space spaceUsed represents */ //空间消耗(以K为单位) long spaceUsed; /* space consumption, in kB */ } TuplesortInstrumentation; ``` ### 二、源码解读 ExecInitSort为排序节点创建运行期信息并初始化outer子树,逻辑较为简单. ``` /* ---------------------------------------------------------------- * ExecInitSort * * Creates the run-time state information for the sort node * produced by the planner and initializes its outer subtree. * ---------------------------------------------------------------- */ SortState * ExecInitSort(Sort *node, EState *estate, int eflags) { SortState *sortstate;//排序运行期信息 SO1_printf("ExecInitSort: %s\n", "initializing sort node"); /* * create state structure * 创建运行期状态节点结构体 */ sortstate = makeNode(SortState); sortstate->ss.ps.plan = (Plan *) node; sortstate->ss.ps.state = estate; sortstate->ss.ps.ExecProcNode = ExecSort; /* * We must have random access to the sort output to do backward scan or * mark/restore. We also prefer to materialize the sort output if we * might be called on to rewind and replay it many times. * 需要随机访问用于排序输出用于执行后端搜索或者标记/存储. * 同时,如果可能在rewind或replay很多次的情况下,会倾向于物化排序输出 */ sortstate->randomAccess = (eflags & (EXEC_FLAG_REWIND | EXEC_FLAG_BACKWARD | EXEC_FLAG_MARK)) != 0; sortstate->bounded = false;//结果集不存在边界 sortstate->sort_Done = false;//未完成排序 sortstate->tuplesortstate = NULL;//元组排序状态为NULL /* * Miscellaneous initialization * 执行各种初始化 * * Sort nodes don't initialize their ExprContexts because they never call * ExecQual or ExecProject. * 排序节点不需要初始化ExprContexts,因为排序不会调用ExecQual/ExecProject */ /* * initialize child nodes * 初始化子节点 * * We shield the child node from the need to support REWIND, BACKWARD, or * MARK/RESTORE. * 子节点不需要支持REWIND, BACKWARD, MARK/RESTORE */ eflags &= ~(EXEC_FLAG_REWIND | EXEC_FLAG_BACKWARD | EXEC_FLAG_MARK); //外(左)子节点往往是扫描节点,如SeqScan等 outerPlanState(sortstate) = ExecInitNode(outerPlan(node), estate, eflags); /* * Initialize scan slot and type. * 初始化扫描slot和类型 */ ExecCreateScanSlotFromOuterPlan(estate, &sortstate->ss); /* * Initialize return slot and type. No need to initialize projection info * because this node doesn't do projections. * 初始化返回slot和类型. * 不需要初始化投影信息因为排序节点不需要投影. */ ExecInitResultTupleSlotTL(estate, &sortstate->ss.ps); sortstate->ss.ps.ps_ProjInfo = NULL; SO1_printf("ExecInitSort: %s\n", "sort node initialized"); return sortstate; } /* ---------------- * ExecCreateSlotFromOuterPlan * ---------------- */ void ExecCreateScanSlotFromOuterPlan(EState *estate, ScanState *scanstate) { PlanState *outerPlan; TupleDesc tupDesc; outerPlan = outerPlanState(scanstate); tupDesc = ExecGetResultType(outerPlan); ExecInitScanTupleSlot(estate, scanstate, tupDesc); } /* ---------------- * ExecInitScanTupleSlot * ---------------- */ void ExecInitScanTupleSlot(EState *estate, ScanState *scanstate, TupleDesc tupledesc) { scanstate->ss_ScanTupleSlot = ExecAllocTableSlot(&estate->es_tupleTable, tupledesc); scanstate->ps.scandesc = tupledesc; } ``` ### 三、跟踪分析 N/A ### 四、参考资料 N/A