PostgreSQL Source Code interpretation (193)-query # 109 (sort # 2-ExecSort)

This section continues to introduce the implementation of sorting, the previous section introduced ExecInitSort, this section mainly introduces the sorting implementation function ExecSort.

I. data structure

SortState

Sort run-time status information

/ *-* SortState information * sort runtime status information *-* / typedef struct SortState {/ / base class ScanState ss; / * its first field is NodeTag * / / do I need to randomly access the sorted output? Bool randomAccess; / * need random access to sort output? * / is there a boundary in the result set? Bool bounded; / * is the result set bounded? * / / if there is a boundary, how many tuples are needed? Int64 bound; / * if bounded, how many tuples are needed * / / have you finished sorting? Bool sort_Done; / * sort completed yet? * / do you use bounded values? What is the bounded value used by bool bounded_Done; / * value of bounded we did the sort with * / /? Is the private status of 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? * / / each worker corresponds to an entry SharedSortInfo * shared_info; / * one entry per worker * /} SortState / *-* Shared memory container for per-worker sort information * the number of shared memory containers for per-worker sorting information *-* / typedef struct SharedSortInfo {/ / worker? Int num_workers; / / sorting mechanism TuplesortInstrumentation server [flex _ ARRAY_MEMBER];} SharedSortInfo

TuplesortInstrumentation

Report the data structure of sorted statistics.

/ * Data structures for reporting sort statistics. Note that * TuplesortInstrumentation can't contain any pointers because we * sometimes put it in shared memory. * report the data structure of sorted statistics. * Note that TuplesortInstrumentation cannot contain pointers because sometimes the structure is placed in shared memory. * / typedef enum {SORT_TYPE_STILL_IN_PROGRESS = 0 SORT_TYPE_STILL_IN_PROGRESS / still in sorting SORT_TYPE_TOP_N_HEAPSORT,//TOP N heap sort SORT_TYPE_QUICKSORT,// quick sort SORT_TYPE_EXTERNAL_SORT,// external sort SORT_TYPE_EXTERNAL_MERGE// external sort merge} TuplesortMethod / / sorting method typedef enum {SORT_SPACE_TYPE_DISK,// needs to use disk SORT_SPACE_TYPE_MEMORY// use memory} TuplesortSpaceType;typedef struct TuplesortInstrumentation {/ / sort algorithm TuplesortMethod sortMethod; / * sort algorithm used * / / sort using space type TuplesortSpaceType spaceType; / * type of space spaceUsed represents * / / Space consumption (in K) long spaceUsed / * space consumption, in kB * /} TuplesortInstrumentation; II. Source code interpretation

ExecSort uses tuplesort to sort tuples obtained from outer subtree nodes and cache results in memory or temporary files. After the initial call, a row is returned for each subsequent call.

The implementation logic is not complicated. Get all tuples from outer plan and call tuplesort to sort. If the size of work_mem is large enough, it is stored in memory or temporary file storage is used on disk.

/ *-* 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. * use tuplesort to sort tuples obtained by outer subtree nodes, and * cache results in memory or temporary files. * after the initial call, a row is returned for each subsequent call. * * Conditions: *-- none. *-- No * * Initial States: *-- the outer child is prepared to return the first tuple. * initial state: *-- the outer child node is ready to return the first tuple. *-* / static TupleTableSlot * ExecSort (PlanState * pstate) {/ / sort running status SortState * node = castNode (SortState, pstate); EState * estate;// running status ScanDirection dir / / scan direction Tuplesortstate * tuplesortstate;// tuple sort status TupleTableSlot * slot;// tuple slot CHECK_FOR_INTERRUPTS (); / * * get state info from node * get running status 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. * if the first round, read all tuples from outer plan and pass them to tuplesort.c. * subsequent calls only extract tuples from tuplesort. * / if (! node- > sort_Done) {/ /-for the first time, you need to sort 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. * when creating the sorted data of the results, scan the subplan forward * / set the scanning direction estate- > es_direction = ForwardScanDirection; / * * Initialize tuplesort module. * initialize tuplesort module * / SO1_printf ("ExecSort:% s\ n", "calling tuplesort_begin"); / / get outer plan running status outerNode = outerPlanState (node); / / get result type (tuple descriptor) tupDesc = ExecGetResultType (outerNode) / / execute tuplesort_begin_heap tuplesortstate = tuplesort_begin_heap (tupDesc, plannode- > numCols, plannode- > sortColIdx, plannode- > sortOperators Plannode- > collations, plannode- > nullsFirst, work_mem, NULL, node- > randomAccess) If the if (node- > bounded) / / node is bounded, set the boundary tuplesort_set_bound (tuplesortstate, node- > bound); node- > tuplesortstate = (void *) tuplesortstate; / * * Scan the subplan and feed all the tuples to tuplesort. * scan the subplan and send all tuples to tuplesort * / for (;;) {/ / get tuples slot = ExecProcNode (outerNode) from outer plan; if (TupIsNull (slot)) break;// until all are fetched / / sort tuplesort_puttupleslot (tuplesortstate, slot) } / * Complete the sort. * complete sorting * / tuplesort_performsort (tuplesortstate); / * * restore to user specified direction * restore the scan direction specified by the user * / estate- > es_direction = dir; / * * finally set the sorted flag to true * finally, set the sorted mark 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 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. * get the first / next tuple in tuplesort. * if there are no more tuples, return NULL. * Note that we keep the tuples stored in slot available until the next tuple is extracted from tuplesort. * / slot = node- > ss.ps.ps_ResultTupleSlot; (void) tuplesort_gettupleslot (tuplesortstate, ScanDirectionIsForward (dir), false, slot, NULL); return slot;} III. Tracking analysis

Create a data table and insert test data

Drop table if exists tours sortport 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 (1m 100000) as col;testdb=# explain (verbose,analyze) select * from t_sort order by C1 Magi 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)

Test script

Testdb=# select * from t_sort order by C1 and c2

Tracking and debugging

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

Input parameters

(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, 0x0 = scandesc}

The left tree node is SeqScan, or 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 = ps_ProjInfo, 0x0 = 0x0}

Get the running state of the node & scanning direction

(gdb) n48 CHECK_FOR_INTERRUPTS (); (gdb) 56 estate = node- > ss.ps.state; (gdb) 57 dir = estate- > es_direction; (gdb) 58 tuplesortstate = (Tuplesortstate *) node- > tuplesortstate (gdb) (gdb) n65 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 * tuplesortstateCannot access memory at address 0x0

Unfinished sorting, enter the sorting logic and set the scanning direction

(gdb) n67 Sort * plannode = (Sort *) node- > ss.ps.plan; (gdb) n78 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 = nullsFirst}

Get the result type and call tuplesort_begin_heap to get the sort status tuplesortstate

(gdb) N87 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) n89 tuplesortstate = tuplesort_begin_heap (tupDesc, (gdb) 97 if (node- > bounded) (gdb) 99 node- > tuplesortstate = (void *) tuplesortstate; (gdb)

Loop to get the tuple and call tuplesort_puttupleslot (described in the next section) to put it in the order to be sorted

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

Set breakpoints, complete the loop, and execute tuplesort_performsort (described in the next section) to complete the sorting

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

Set other related tags

(gdb) n123 estate- > es_direction = dir; (gdb) 128node- > sort_Done = true; (gdb) 129node- > bounded_Done = node- > bounded; (gdb) 130node- > bound_Done = node- > bound; (gdb) 131if (node- > shared_info & & node- > am_worker) (gdb) 151slot = 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, 0x0 = 0x0, ps_ResultTupleSlot = 0x17a3900, ps_ExprContext = 0x0, 0x0 = ps_ProjInfo, 0x0 = 0x0}, 0x0 = 0x0, scandesc =} RandomAccess = false, bounded = false, bound = 0, sort_Done = true, bounded_Done = false, bound_Done = 0, tuplesortstate = 0x17ac7b8, am_worker = false, shared_info = 0x0} (gdb)

Finish sorting and get tuples

(gdb) p node- > tuplesortstate$8 = (void *) 0x17ac7b8 (gdb) n152 (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)

Next call, extract the tuple directly

(gdb) cContinuing.Breakpoint 1, ExecSort (pstate=0x17a29b0) at nodeSort.c:4242 SortState * node = castNode (SortState, pstate); (gdb) n48 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) IV. References.

N/A