本节介绍排序的实现,排序的实现函数是ExecSort,与聚合函数类似,也有要一个初始化的过程ExecInitSort,本节主要介绍该函数的实现.
我们提供的服务有：网站制作、网站建设、微信公众号开发、网站优化、网站认证、下城ssl等。为1000多家企事业单位解决了网站和推广的问题。提供周到的售前咨询和贴心的售后服务，是有科学管理、有技术的下城网站制作公司
下面是测试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
