Shulou(Shulou.com)06/01 Report--

This section continues to introduce the implementation of sorting, the previous section introduced ExecSort, this section describes the specific implementation of sorting functions called in this function, this section is the first part, including tuplesort_begin_heap/tuplesort_puttupleslot.

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

Tuplesort_begin_heap and tuplesort_puttupleslot are both preparatory work, putting tuple into an array (heap) to prepare for subsequent actual sorting implementations.

Tuplesort_begin_heap

Tuplesortstate * tuplesort_begin_heap (TupleDesc tupDesc,// tuple descriptor int nkeys, / / number of sort keys AttrNumber * attNums,// attribute number Oid * sortOperators, / / sort operator Oid * sortCollations,// collation bool * nullsFirstFlags,// tag int workMem / / memory size SortCoordinate coordinate,// coordinator bool randomAccess) / / whether to randomly access {/ / get sort status Tuplesortstate * state = tuplesort_begin_common (workMem, coordinate, randomAccess) MemoryContext oldcontext; int i; oldcontext = MemoryContextSwitchTo (state- > sortcontext); AssertArg (nkeys > 0); # ifdef TRACE_SORT if (trace_sort) elog (LOG, "begin tuple sort: nkeys =% d, workMem =% d, randomAccess =% c", nkeys, workMem, randomAccess? 't':'f'); # endif state- > nKeys = nkeys TRACE_POSTGRESQL_SORT_START (HEAP_SORT, false, / * no unique check * / nkeys, workMem, randomAccess, PARALLEL_SORT (state)) / / set the running status state- > comparetup = comparetup_heap; state- > copytup = copytup_heap; state- > writetup = writetup_heap; state- > readtup = readtup_heap; / / assuming there is no need to copy the tuple descriptor state- > tupDesc = tupDesc; / * assume we need not copy tupDesc * / state- > abbrevNext = 10 / * Prepare SortSupport data for each column * / / prepare SortSupport data for each column (allocate memory space) state- > sortKeys = (SortSupport) palloc0 (nkeys * sizeof (SortSupportData)); for (I = 0; I

SortKeys + I; AssertArg (attNums [I]! = 0); AssertArg (sortoperators [I]! = 0); / / set SortSupport sortKey- > ssup_cxt = CurrentMemoryContext; sortKey- > ssup_collation = sortCollations [I]; sortKey- > ssup_nulls_first = nullsFirstFlags [I]; sortKey- > ssup_attno = attNums [I] / * Convey if abbreviation optimization is applicable in principle * / / is acronym optimization available in principle? SortKey- > abbreviate = (I = = 0); / / set PrepareSortSupportFromOrderingOp (sortOperators [I], sortKey);} / * * The "onlyKey" optimization cannot be used with abbreviated keys, since * tie-breaker comparisons may be required. Typically, the optimization * is only of value to pass-by-value types anyway, whereas abbreviated * keys are typically only of value to pass-by-reference types. * for acronym optimization "onlyKey" optimization cannot be used because tie-breaker comparison may be required. * typically, the optimizer is only valuable for passing types by value, while abbreviations are usually only valuable for passing types by reference. * / if (nkeys = = 1 & &! state- > sortKeys- > abbrev_converter) state- > onlyKey = state- > sortKeys; MemoryContextSwitchTo (oldcontext); return state;}

Tuplesort_puttupleslot

Receive a tuple (one line)

/ * Accept one tuple while collecting input data for sort. * receive a tuple (one line) * * Note that the input data is always copied; the caller need not save it. * Note that input data is usually copied and the caller does not need to save it. * / voidtuplesort_puttupleslot (Tuplesortstate * state, TupleTableSlot * slot) {MemoryContext oldcontext = MemoryContextSwitchTo (state- > sortcontext); SortTuple stup; / * * Copy the given tuple into memory we control, and decrease availMem. * Then call the common code. * copy the given tuple in the memory we control while reducing the available memory. * then call the puttuple_common function. * / / # define COPYTUP (state,stup,tup) ((* (state)-> copytup) (state,stup,tup)) COPYTUP (state, & stup, (void *) slot); puttuple_common (state, & stup); MemoryContextSwitchTo (oldcontext);} / * Shared code for tuple and datum cases. * Code shared by tuple and datum. * / static voidputtuple_common (Tuplesortstate * state, SortTuple * tuple) {Assert (! LEADER (state)); switch (state- > status) {case TSS_INITIAL:// initialization / * * Save the tuple into the unsorted array. First, grow the array * as needed. Note that we try to grow the array when there is * still one free slot remaining-if we fail, there'll still be * room to store the incoming tuple, and then we'll switch to * tape-based operation. * store tuples in an unsorted array. * first, expand the array size if necessary. Note that you try to extend the array only when there is only 1 slot left. * if the expansion fails, there is still room to store the input tuples and then switch to the tape-based (tape-based) operation. * / if (state- > memtupcount > = state- > memtupsize-1) {(void) grow_memtuples (state); Assert (state- > memtupcount

Memtupsize);} state- > memtuples [state-> memtupcount++] = * tuple;// saves tuples / * * Check if it's time to switch over to a bounded heapsort in the array. We do * so if the input tuple count exceeds twice the desired tuple * count (this is a heuristic for where heapsort becomes cheaper * than a quicksort), or if we've just filled workMem and have * enough tuples to meet the bound. * check whether to switch to bounded heapsort. * perform this check when the number of input tuples exceeds twice the expected number of tuples * (insight gained when heap sorting is cheaper than quick sorting), or if we have populated workMem and have enough tuples to satisfy bound. * Note that once we enter TSS_BOUNDED state we will always try to * complete the sort that way. In the worst case, if later input * tuples are larger than earlier ones, this might cause us to * exceed workMem significantly. * Note that once we enter the TSS_BOUNDED state, we will try to complete the sorting in the specified way. * in the worst case, if the subsequent input tuple is larger than the previous one, this may cause the memory size to exceed workMem. * / if (state- > bounded & & (state- > memtupcount > state- > bound * 2 | | (state- > memtupcount > state- > bound & & LACKMEM (state) {# ifdef TRACE_SORT if (trace_sort) elog (LOG, "switching to bounded heapsort at% d tuples:% s", state- > memtupcount Pg_rusage_show (& state- > ru_start)) # endif / / switch to heap sort make_bounded_heap (state); return;} / * * Done if we still fit in available memory and have array slots. * if memory space is available and the array has location storage, the task is completed! * / if (state- > memtupcount)

Memtupsize & &! LACKMEM (state) return; / * * Nope; time to switch to tape-based operation. * switch to tape-base operation * / inittapes (state, true); / * Dump all tuples. * dump all tuples * / dumptuples (state, false); break; case TSS_BOUNDED:// bounded heap sort / * * We don't want to grow the array here, so check whether the new * tuple can be discarded before putting it in. This should be a * good speed optimization, too, since when there are many more * input tuples than the bound, most input tuples can be discarded * with just this one comparison. Note that because we currently * have the sort direction reversed, we must check for =. * you don't want to extend the array here, so check to see if some of the new tuples are available before putting them into the array. * this will be a good performance optimization because there are input tuples that are much larger than the boundary. * most input tuples will be discarded by comparison. * / if (COMPARETUP (state, tuple, & state- > memtuples [0]) memtupcount++] = * tuple; / * * If we are over the memory limit, dump all tuples. * if the memory limit has been exceeded, dump all tuples * / dumptuples (state, false); break; default: elog (ERROR, "invalid tuplesort state"); break;}} III. Trace analysis

N/A

IV. Reference materials

N/A

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.