本节继续介绍排序的实现,上一节介绍了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