本节继续介绍排序的实现,上一节介绍了ExecInitSort,本节主要介绍排序的实现函数ExecSort.

创新互联公司从2013年开始，是专业互联网技术服务公司，拥有项目网站制作、成都网站制作网站策划，项目实施与项目整合能力。我们以让每一个梦想脱颖而出为使命，1280元积石山保安族东乡族做网站,已为上家服务,为积石山保安族东乡族各地企业和个人服务,联系电话:18982081108

一、数据结构

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;

二、源码解读

ExecSort使用tuplesort排序从outer子树节点获取的元组,在内存或者临时文件中缓存结果.在初次调用后,后续的每次调用返回一行.
实现逻辑不复杂,从outer plan中获取所有元组,调用tuplesort进行排序,如work_mem大小足够则在内存中存储否则在磁盘中使用临时文件存储.

/* ----------------------------------------------------------------
 *        ExecSort
 *
 *        Sorts tuples from the outer subtree of the node using tuplesort,
 *        which saves the results in a temporary file or memory. After the
 *        initial call, returns a tuple from the file with each call.
 *        使用tuplesort排序outer子树节点获取的元组,
 *          在内存或者临时文件中缓存结果.
 *        在初次调用后,后续的每次调用返回一行.
 *
 *        Conditions:
 *          -- none.
 *          -- 无
 *
 *        Initial States:
 *          -- the outer child is prepared to return the first tuple.
 *        初始状态:
 *          -- outer子节点已准备返回第一个元组.
 * ----------------------------------------------------------------
 */
static TupleTableSlot *
ExecSort(PlanState *pstate)
{
    //排序运行状态
    SortState  *node = castNode(SortState, pstate);
    EState       *estate;//运行状态
    ScanDirection dir;//扫描方向
    Tuplesortstate *tuplesortstate;//元组排序状态
    TupleTableSlot *slot;//元组slot
    CHECK_FOR_INTERRUPTS();
    /*
     * get state info from node
     * 从节点中获取运行状态
     */
    SO1_printf("ExecSort: %s\n",
               "entering routine");
    estate = node->ss.ps.state;
    dir = estate->es_direction;
    tuplesortstate = (Tuplesortstate *) node->tuplesortstate;
    /*
     * If first time through, read all tuples from outer plan and pass them to
     * tuplesort.c. Subsequent calls just fetch tuples from tuplesort.
     * 如果第一轮,从outer plan中读取所有元组并传递给tuplesort.c.
     * 后续的调用只是从tuplesort中提取元组.
     */
    if (!node->sort_Done)
    {
        //-------------- 首次,需要进行排序
        Sort       *plannode = (Sort *) node->ss.ps.plan;
        PlanState  *outerNode;
        TupleDesc    tupDesc;
        SO1_printf("ExecSort: %s\n",
                   "sorting subplan");
        /*
         * Want to scan subplan in the forward direction while creating the
         * sorted data.
         * 在创建结果排序数据时,向前扫描子计划
         */
        //设置扫描方向
        estate->es_direction = ForwardScanDirection;
        /*
         * Initialize tuplesort module.
         * 初始化tuplesort模块
         */
        SO1_printf("ExecSort: %s\n",
                   "calling tuplesort_begin");
        //获取outer plan运行状态
        outerNode = outerPlanState(node);
        //获取结果类型(元组描述符)
        tupDesc = ExecGetResultType(outerNode);
        //执行tuplesort_begin_heap
        tuplesortstate = tuplesort_begin_heap(tupDesc,
                                              plannode->numCols,
                                              plannode->sortColIdx,
                                              plannode->sortOperators,
                                              plannode->collations,
                                              plannode->nullsFirst,
                                              work_mem,
                                              NULL, node->randomAccess);
        if (node->bounded)
            //节点有界,则设置边界
            tuplesort_set_bound(tuplesortstate, node->bound);
        node->tuplesortstate = (void *) tuplesortstate;
        /*
         * Scan the subplan and feed all the tuples to tuplesort.
         * 扫描子计划并把所有元组都发给tuplesort
         */
        for (;;)
        {
            //从outer plan中获取元组
            slot = ExecProcNode(outerNode);
            if (TupIsNull(slot))
                break;//直至全部获取完毕
            //排序
            tuplesort_puttupleslot(tuplesortstate, slot);
        }
        /*
         * Complete the sort.
         * 完成排序
         */
        tuplesort_performsort(tuplesortstate);
        /*
         * restore to user specified direction
         * 恢复用户指定的扫描方向
         */
        estate->es_direction = dir;
        /*
         * finally set the sorted flag to true
         * 最后,设置已排序标记为T
         */
        node->sort_Done = true;
        node->bounded_Done = node->bounded;
        node->bound_Done = node->bound;
        if (node->shared_info && node->am_worker)
        {
            TuplesortInstrumentation *si;
            Assert(IsParallelWorker());
            Assert(ParallelWorkerNumber <= node->shared_info->num_workers);
            si = &node->shared_info->sinstrument[ParallelWorkerNumber];
            tuplesort_get_stats(tuplesortstate, si);
        }
        SO1_printf("ExecSort: %s\n", "sorting done");
    }
    SO1_printf("ExecSort: %s\n",
               "retrieving tuple from tuplesort");
    /*
     * Get the first or next tuple from tuplesort. Returns NULL if no more
     * tuples.  Note that we only rely on slot tuple remaining valid until the
     * next fetch from the tuplesort.
     * 在tuplesort中获取第一个/下一个元组.
     * 如无更多的元组,返回NULL.
     * 注意我们会一直保持存储在slot中的元组可用直至从tuplesort中提取下一个元组.
     */
    slot = node->ss.ps.ps_ResultTupleSlot;
    (void) tuplesort_gettupleslot(tuplesortstate,
                                  ScanDirectionIsForward(dir),
                                  false, slot, NULL);
    return slot;
}

三、跟踪分析

创建数据表,插入测试数据

drop table  if exists t_sort;
create table t_sort(bh varchar(20),c1 int,c2 int,c3 int,c4 int,c5 int,c6 int);
insert into t_sort select 'GZ01',col,col,col,col,col,col from generate_series(1,100000) as col;
testdb=# explain (verbose,analyze) select * from t_sort order by c1,c2;
                                                        QUERY PLAN                                                         
---------------------------------------------------------------------------------------------------------------------------
 Sort  (cost=8172.55..8308.71 rows=54464 width=82) (actual time=173.447..225.213 rows=100000 loops=1)
   Output: bh, c1, c2, c3, c4, c5, c6
   Sort Key: t_sort.c1, t_sort.c2
   Sort Method: external merge  Disk: 4120kB
   ->  Seq Scan on public.t_sort  (cost=0.00..1280.64 rows=54464 width=82) (actual time=0.092..55.257 rows=100000 loops=1)
         Output: bh, c1, c2, c3, c4, c5, c6
 Planning Time: 4.648 ms
 Execution Time: 238.227 ms
(8 rows)

测试脚本

testdb=# select * from t_sort order by c1,c2;

跟踪调试

(gdb) b ExecSort
Breakpoint 1 at 0x711909: file nodeSort.c, line 42.
(gdb) c
Continuing.
Breakpoint 1, ExecSort (pstate=0x17a29b0) at nodeSort.c:42
42        SortState  *node = castNode(SortState, pstate);
(gdb)

输入参数

(gdb) p *pstate
$1 = {type = T_SortState, plan = 0x179e540, state = 0x17a2798, ExecProcNode = 0x7118fd , 
  ExecProcNodeReal = 0x7118fd , instrument = 0x0, worker_instrument = 0x0, worker_jit_instrument = 0x0, 
  qual = 0x0, lefttree = 0x17a2ac8, righttree = 0x0, initPlan = 0x0, subPlan = 0x0, chgParam = 0x0, 
  ps_ResultTupleSlot = 0x17a3900, ps_ExprContext = 0x0, ps_ProjInfo = 0x0, scandesc = 0x17a2e50}

左树节点是SeqScan,亦即outer node

(gdb) p *pstate->lefttree
$2 = {type = T_SeqScanState, plan = 0x17a8960, state = 0x17a2798, ExecProcNode = 0x6e0670 , 
  ExecProcNodeReal = 0x710589 , instrument = 0x0, worker_instrument = 0x0, worker_jit_instrument = 0x0, 
  qual = 0x0, lefttree = 0x0, righttree = 0x0, initPlan = 0x0, subPlan = 0x0, chgParam = 0x0, 
  ps_ResultTupleSlot = 0x17a3268, ps_ExprContext = 0x17a2be0, ps_ProjInfo = 0x0, scandesc = 0x7faf6c0ec160}

获取节点的运行状态&扫描方向

(gdb) n
48        CHECK_FOR_INTERRUPTS();
(gdb) 
56        estate = node->ss.ps.state;
(gdb) 
57        dir = estate->es_direction;
(gdb) 
58        tuplesortstate = (Tuplesortstate *) node->tuplesortstate;
(gdb) 
(gdb) n
65        if (!node->sort_Done)
(gdb) 
(gdb) p *estate
$3 = {type = T_EState, es_direction = ForwardScanDirection, es_snapshot = 0x17698a0, es_crosscheck_snapshot = 0x0, 
  es_range_table = 0x17a8e58, es_plannedstmt = 0x16a7e80, es_sourceText = 0x16a6d78 "select * from t_sort order by c1,c2;", 
  es_junkFilter = 0x0, es_output_cid = 0, es_result_relations = 0x0, es_num_result_relations = 0, 
  es_result_relation_info = 0x0, es_root_result_relations = 0x0, es_num_root_result_relations = 0, 
  es_tuple_routing_result_relations = 0x0, es_trig_target_relations = 0x0, es_trig_tuple_slot = 0x0, 
  es_trig_oldtup_slot = 0x0, es_trig_newtup_slot = 0x0, es_param_list_info = 0x0, es_param_exec_vals = 0x0, 
  es_queryEnv = 0x0, es_query_cxt = 0x17a2680, es_tupleTable = 0x17a2e18, es_rowMarks = 0x0, es_processed = 0, 
  es_lastoid = 0, es_top_eflags = 16, es_instrument = 0, es_finished = false, es_exprcontexts = 0x17a2ca0, 
  es_subplanstates = 0x0, es_auxmodifytables = 0x0, es_per_tuple_exprcontext = 0x0, es_epqTuple = 0x0, 
  es_epqTupleSet = 0x0, es_epqScanDone = 0x0, es_use_parallel_mode = false, es_query_dsa = 0x0, es_jit_flags = 0, 
  es_jit = 0x0, es_jit_worker_instr = 0x0}
(gdb) p dir
$4 = ForwardScanDirection
(gdb) p *tuplesortstate
Cannot access memory at address 0x0

未完成排序,进入排序逻辑,设置扫描方向

(gdb) n
67            Sort       *plannode = (Sort *) node->ss.ps.plan;
(gdb) n
78            estate->es_direction = ForwardScanDirection;
(gdb) 
86            outerNode = outerPlanState(node);
(gdb) p *plannode
$5 = {plan = {type = T_Sort, startup_cost = 12434.82023721841, total_cost = 12684.82023721841, plan_rows = 100000, 
    plan_width = 29, parallel_aware = false, parallel_safe = true, plan_node_id = 0, targetlist = 0x17a8fc8, qual = 0x0, 
    lefttree = 0x17a8960, righttree = 0x0, initPlan = 0x0, extParam = 0x0, allParam = 0x0}, numCols = 2, 
  sortColIdx = 0x17a89f8, sortOperators = 0x17a8a18, collations = 0x17a8a38, nullsFirst = 0x17a8a58}
(gdb)

获取结果类型并调用tuplesort_begin_heap获取排序状态tuplesortstate

(gdb) n
87            tupDesc = ExecGetResultType(outerNode);
(gdb) 
96                                                  NULL, node->randomAccess);
(gdb) p *tupDesc
$6 = {natts = 7, tdtypeid = 2249, tdtypmod = -1, tdhasoid = false, tdrefcount = -1, constr = 0x0, attrs = 0x17a2e70}
(gdb) n
89            tuplesortstate = tuplesort_begin_heap(tupDesc,
(gdb) 
97            if (node->bounded)
(gdb) 
99            node->tuplesortstate = (void *) tuplesortstate;
(gdb)

循环获取元组并调用tuplesort_puttupleslot(下一节介绍),放到待排序中

(gdb) n
107                slot = ExecProcNode(outerNode);
(gdb) 
109                if (TupIsNull(slot))
(gdb) 
112                tuplesort_puttupleslot(tuplesortstate, slot);
(gdb) 
113            }
(gdb) 
107                slot = ExecProcNode(outerNode);
(gdb)

设置断点,完成循环,并执行tuplesort_performsort(下一节介绍)完成排序

(gdb) b nodeSort.c:118
Breakpoint 2 at 0x711a72: file nodeSort.c, line 118.
(gdb) c
Continuing.
Breakpoint 2, ExecSort (pstate=0x17a29b0) at nodeSort.c:118
118            tuplesort_performsort(tuplesortstate);
(gdb)

设置相关其他标记

(gdb) n
123            estate->es_direction = dir;
(gdb) 
128            node->sort_Done = true;
(gdb) 
129            node->bounded_Done = node->bounded;
(gdb) 
130            node->bound_Done = node->bound;
(gdb) 
131            if (node->shared_info && node->am_worker)
(gdb) 
151        slot = node->ss.ps.ps_ResultTupleSlot;
(gdb) p *node
$7 = {ss = {ps = {type = T_SortState, plan = 0x179e540, state = 0x17a2798, ExecProcNode = 0x7118fd , 
      ExecProcNodeReal = 0x7118fd , instrument = 0x0, worker_instrument = 0x0, worker_jit_instrument = 0x0, 
      qual = 0x0, lefttree = 0x17a2ac8, righttree = 0x0, initPlan = 0x0, subPlan = 0x0, chgParam = 0x0, 
      ps_ResultTupleSlot = 0x17a3900, ps_ExprContext = 0x0, ps_ProjInfo = 0x0, scandesc = 0x17a2e50}, 
    ss_currentRelation = 0x0, ss_currentScanDesc = 0x0, ss_ScanTupleSlot = 0x17a33a8}, randomAccess = false, 
  bounded = false, bound = 0, sort_Done = true, bounded_Done = false, bound_Done = 0, tuplesortstate = 0x17ac7b8, 
  am_worker = false, shared_info = 0x0}
(gdb)

完成排序,获取元组

(gdb) p node->tuplesortstate
$8 = (void *) 0x17ac7b8
(gdb) n
152        (void) tuplesort_gettupleslot(tuplesortstate,
(gdb) 
155        return slot;
(gdb) p *slot
$9 = {type = T_TupleTableSlot, tts_isempty = false, tts_shouldFree = false, tts_shouldFreeMin = false, tts_slow = false, 
  tts_tuple = 0x17a3940, tts_tupleDescriptor = 0x17a34e8, tts_mcxt = 0x17a2680, tts_buffer = 0, tts_nvalid = 0, 
  tts_values = 0x17a3960, tts_isnull = 0x17a3998, tts_mintuple = 0x1bc07f8, tts_minhdr = {t_len = 56, t_self = {ip_blkid = {
        bi_hi = 0, bi_lo = 0}, ip_posid = 0}, t_tableOid = 0, t_data = 0x1bc07f0}, tts_off = 0, 
  tts_fixedTupleDescriptor = true}
(gdb)

下一次调用,直接提取元组

(gdb) c
Continuing.
Breakpoint 1, ExecSort (pstate=0x17a29b0) at nodeSort.c:42
42        SortState  *node = castNode(SortState, pstate);
(gdb) n
48        CHECK_FOR_INTERRUPTS();
(gdb) 
56        estate = node->ss.ps.state;
(gdb) 
57        dir = estate->es_direction;
(gdb) 
58        tuplesortstate = (Tuplesortstate *) node->tuplesortstate;
(gdb) 
65        if (!node->sort_Done)
(gdb) 
151        slot = node->ss.ps.ps_ResultTupleSlot;
(gdb) 
152        (void) tuplesort_gettupleslot(tuplesortstate,
(gdb)

四、参考资料

N/A