PostgreSQL 源碼解讀（192）- 查詢#108(排序#1 - ExecInitSort)

本節(jié)介紹排序的實(shí)現(xiàn),排序的實(shí)現(xiàn)函數(shù)是ExecSort,與聚合函數(shù)類似,也有要一個(gè)初始化的過程ExecInitSort,本節(jié)主要介紹該函數(shù)的實(shí)現(xiàn).

下面是測(cè)試SQL執(zhí)行排序的計(jì)劃樹:

",,,,,"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"

一、數(shù)據(jù)結(jié)構(gòu)

SortState
排序運(yùn)行期狀態(tài)信息

/* ----------------
 *     SortState information
 *     排序運(yùn)行期狀態(tài)信息
 * ----------------
 */
typedef struct SortState
{
    //基類
    ScanState    ss;                /* its first field is NodeTag */
    //是否需要隨機(jī)訪問排序輸出?
    bool        randomAccess;    /* need random access to sort output? */
    //結(jié)果集是否存在邊界?
    bool        bounded;        /* is the result set bounded? */
    //如存在邊界,需要多少個(gè)元組?
    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的私有狀態(tài)
    void       *tuplesortstate; /* private state of tuplesort.c */
    //是否worker?
    bool        am_worker;        /* are we a worker? */
    //每個(gè)worker對(duì)應(yīng)一個(gè)條目
    SharedSortInfo *shared_info;    /* one entry per worker */
} SortState;
/* ----------------
 *     Shared memory container for per-worker sort information
 *     per-worker排序信息的共享內(nèi)存容器
 * ----------------
 */
typedef struct SharedSortInfo
{
    //worker個(gè)數(shù)?
    int            num_workers;
    //排序機(jī)制
    TuplesortInstrumentation sinstrument[FLEXIBLE_ARRAY_MEMBER];
} SharedSortInfo;

TuplesortInstrumentation
報(bào)告排序統(tǒng)計(jì)的數(shù)據(jù)結(jié)構(gòu).

/*
 * Data structures for reporting sort statistics.  Note that
 * TuplesortInstrumentation can't contain any pointers because we
 * sometimes put it in shared memory.
 * 報(bào)告排序統(tǒng)計(jì)的數(shù)據(jù)結(jié)構(gòu).
 * 注意TuplesortInstrumentation不能包含指針因?yàn)橛袝r(shí)候會(huì)把該結(jié)構(gòu)體放在共享內(nèi)存中.
 */
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//使用內(nèi)存
} 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為排序節(jié)點(diǎn)創(chuàng)建運(yùn)行期信息并初始化outer子樹,邏輯較為簡(jiǎn)單.

/* ----------------------------------------------------------------
 *        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;//排序運(yùn)行期信息
    SO1_printf("ExecInitSort: %s\n",
               "initializing sort node");
    /*
     * create state structure
     * 創(chuàng)建運(yùn)行期狀態(tài)節(jié)點(diǎn)結(jié)構(gòu)體
     */
    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.
     * 需要隨機(jī)訪問用于排序輸出用于執(zhí)行后端搜索或者標(biāo)記/存儲(chǔ).
     * 同時(shí),如果可能在rewind或replay很多次的情況下,會(huì)傾向于物化排序輸出
     */
    sortstate->randomAccess = (eflags & (EXEC_FLAG_REWIND |
                                         EXEC_FLAG_BACKWARD |
                                         EXEC_FLAG_MARK)) != 0;
    sortstate->bounded = false;//結(jié)果集不存在邊界
    sortstate->sort_Done = false;//未完成排序
    sortstate->tuplesortstate = NULL;//元組排序狀態(tài)為NULL
    /*
     * Miscellaneous initialization
     * 執(zhí)行各種初始化
     *
     * Sort nodes don't initialize their ExprContexts because they never call
     * ExecQual or ExecProject.
     * 排序節(jié)點(diǎn)不需要初始化ExprContexts,因?yàn)榕判虿粫?huì)調(diào)用ExecQual/ExecProject
     */
    /*
     * initialize child nodes
     * 初始化子節(jié)點(diǎn)
     *
     * We shield the child node from the need to support REWIND, BACKWARD, or
     * MARK/RESTORE.
     * 子節(jié)點(diǎn)不需要支持REWIND, BACKWARD, MARK/RESTORE
     */
    eflags &= ~(EXEC_FLAG_REWIND | EXEC_FLAG_BACKWARD | EXEC_FLAG_MARK);
    //外(左)子節(jié)點(diǎn)往往是掃描節(jié)點(diǎn),如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和類型.
     * 不需要初始化投影信息因?yàn)榕判蚬?jié)點(diǎn)不需要投影.
     */
    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