PostgreSQL Source Code interpretation (199)-query # 114 (sort # 7-inittapes&dumptuples)

This section continues to introduce the implementation of sorting, mainly the inittapes and dumptuples functions called by tuplesort_puttupleslot- > puttuple_common.

Polyphase Merging sorting is used when the memory cannot meet the sorting requirements.

I. data structure

Tuplesortstate

The private state of the Tuplesort operation.

/ * Possible states of a Tuplesort object. These denote the states that * persist between calls of Tuplesort routines. * the possible state of the Tuplesort object. * these indicate states that persist between calls to Tuplesort routines. * / typedef enum {/ / load tuple, TSS_INITIAL within memory limit, / * Loading tuples; still within memory limit * / / load tuple to TSS_BOUNDED in bounded heap, / * Loading tuples into bounded-size heap * / / load tuple, write to tape TSS_BUILDRUNS, / * Loading tuples Writing to tape * / / complete sorting TSS_SORTEDINMEM completely in memory, / * Sort completed entirely in memory * / / complete sorting, and finally execute sorting TSS_SORTEDONTAPE on tape, / * Sort completed, final run is on tape * / / do not perform final merge TSS_FINALMERGE / * Performing final merge on-the-fly * /} TupSortStatus / * * Parameters for calculation of number of tapes to use-see inittapes () * and tuplesort_merge_order (). * parameters used to calculate how many tapes are needed.-see inittapes () and tuplesort_merge_order () for details. * * In this calculation we assume that each tape will cost us about 1 blocks * worth of buffer space. This ignores the overhead of all the other data * structures needed for each tape, but it's probably close enough. * in this calculation, we assume that each tape consumes about one block of cache space. * although all other data structures that each tape depends on have been ignored, they are very close. * * MERGE_BUFFER_SIZE is how much data we'd like to read from each input * tape during a preread cycle (see discussion at top of file) * MERGE_BUFFER_SIZE indicates the size of the data we will read from each input taple in each read cycle * / # define MINORDER 6 / * minimum merge order * / # define MAXORDER 500 / * maximum merge order * / # define TAPE_BUFFER_OVERHEAD BLCKSZ#define MERGE_BUFFER_SIZE (BLCKSZ * 32) typedef int (* SortTupleComparator) (const SortTuple * a, const SortTuple * b) Tuplesortstate * state) / * Private state of a Tuplesort operation. * Private status of Tuplesort operation. * / struct Tuplesortstate {/ / status: for more information on enumerated values, please see the number of columns in TupSortStatus status; / * enumerated value as shown above * / / sort key. Int nKeys; / * number of columns in sort key * / / the caller needs random access? Bool randomAccess; / * did caller request random access? * / does the caller specify the maximum number of tuples returned? Bool bounded; / * did caller specify a maximum number of * tuples to return? * / / if bounded heap is used, return T bool boundUsed; / * true if we made use of a bounded heap * / if bounded heap is used, the maximum number of tuples int bound is stored here Can I configure / * if bounded, the maximum number of tuples * / / SortTuple.tuple? Bool tuples; / * Can SortTuple.tuple ever be set? * / / remaining available memory size (in bytes) int64 availMem; / * remaining memory available, in bytes * / Total allowed memory size (in bytes) int64 allowedMem; / * total memory allowed, in bytes * / / tapes number int maxTapes / * number of tapes (Knuth's T) * / / number of tapes-1 int tapeRange; / * maxTapes-1 (Knuth's P) * / / memory context MemoryContext sortcontext; / * memory context holding most sort data * / subcontext MemoryContext tuplecontext of sortcontext for tuple data mainly used to sort data / * sub-context of sortcontext for tuple data * / / the logtape.c object LogicalTapeSet * tapeset; / * logtape.c object for tapes in a temp file * / / * * These function pointers decouple the routines that must know what kind * of tuple we are sorting from the routines that don't need to know it of tapes in the temporary file. * They are set up by the tuplesort_begin_xxx routines. * these function pointers will have to know which tuple routines to sort are decoupled from routines that do not need to know it. * * Function to compare two tuples; result is per qsort () convention, ie: * 0 according as ab. The API must match * qsort_arg_comparator. * compare the functions of two tuples, and the result is specified by each qsort (), for example: *

< 0, 0, >

< maxTapes; j++) { state->

Tp_ packages [j] = 1; state- > tp_ runs [j] = 0; state- > tp_ Tap [j] = 1; state- > tp_ taps [j] = j;} state- > tp_ Tap [state-> tapeRange] = 0; state- > tp_ Dummy [state-> tapeRange] = 0; state- > Level = 1; state- > destTape = 0; / / change state to TSS_BUILDRUNS state- > status = TSS_BUILDRUNS;}

Dumptuples

Clear the tuples in memtuples and write the initial run to tape

/ * * dumptuples-remove tuples from memtuples and write initial run to tape * clears the tuples in memtuples and writes the initial run to tape * * When alltuples = true, dump everything currently in memory. (This case is * only used at end of input data.) * for example, alltuples dumps all data in memory. * (only applicable at the end of input data) * / static voiddumptuples (Tuplesortstate * state, bool alltuples) {int memtupwrite; int i; / * * Nothing to do if we still fit in available memory and have array slots, * unless this is the final call during initial run generation. * if it can be put into available memory and the data slots is still available, and this is not the last call when the initial run is generated, return * / if (state- > memtupcount)

< state->

Memtupsize &! LACKMEM (state) & &! alltuples) return; / * * Final call might require no sorting, in rare cases where we just so * happen to have previously LACKMEM ()'d at the point where exactly all * remaining tuples are loaded into memory, just before input was * exhausted. * the last call may not require sorting, and in rare cases, * we call LACKMEM () 'd just before the input runs out, and all remaining tuples are loaded into memory. * In general, short final runs are quite possible. Rather than allowing * a special case where there was a superfluous selectnewtape () call (i.e. * a call with no subsequent run actually written to destTape), we prefer * to write out a 0 tuple run. * generally speaking, the final runs is likely to be short. Instead of allowing an additional selectnewtape () function call (that is, a call that is actually written to destTape without subsequent runs), * might as well write a 0-tuple run. * * mergereadnext () is prepared for 0 tuple runs, and will reliably mark * the tape inactive for the merge when called from beginmerge (). This * case is therefore similar to the case where mergeonerun () finds a dummy * run for the tape, and so doesn't need to merge a run from the tape (or * conceptually "merges" the dummy run, if you prefer). According to * Knuth, Algorithm D "isn't strictly optimal" in its method of * distribution and dummy run assignment; this edge case seems very * unlikely to make that appreciably worse. * mergereadnext () prepares the 0-tuple runs and marks tape as inactive when the beginmerge () function calls the function. * this situation is similar to mergeonerun () retrieving the virtual run for tape, so there is no need for merging (nominal merging can be performed if you like). * according to Knuth, algorithm D is not strictly distributed and optimized for virtual run allocation, but this extreme situation is unlikely to make the situation very bad. * / Assert (state- > status = = TSS_BUILDRUNS); / * It seems unlikely that this limit will ever be exceeded, but take no * chances * is out of bounds. * / if (state- > currentRun = = INT_MAX) ereport (ERROR, (errcode (ERRCODE_PROGRAM_LIMIT_EXCEEDED), errmsg ("cannot have more than% d runs for an external sort", INT_MAX)); state- > currentRun++ # ifdef TRACE_SORT if (trace_sort) elog (LOG, "worker% d starting quicksort of run% d:% s", state- > worker, state- > currentRun, pg_rusage_show (& state- > ru_start)); # endif / * * Sort all tuples accumulated within the allowed amount of memory for * this run using quicksort * sort tuples in memory using quick sort. * / tuplesort_sort_memtuples (state); # ifdef TRACE_SORT if (trace_sort) elog (LOG, "worker% d finished quicksort of run% d:% s", state- > worker, state- > currentRun, pg_rusage_show (& state- > ru_start)); # endif / / write to tape memtupwrite = state- > memtupcount; for (I = 0; I

< memtupwrite; i++) { WRITETUP(state, state->

Tp_ taping [state-> destTape], & state- > memtuples [I]); state- > memtupcount--;} / * * Reset tuple memory. We've freed all of the tuples that we previously * allocated. It's important to avoid fragmentation when there is a stark * change in the sizes of incoming tuples. Fragmentation due to * AllocSetFree's bucketing by size class might be particularly bad if * this step wasn't taken. * reset the tuple memory context. * the goal is to avoid memory fragmentation. * / MemoryContextReset (state- > tuplecontext); markrunend (state, state- > tp_ tapping [state-> destTape]); state- > tp_ runs [state-> destTape] +; state- > tp_ Dummy [state-> destTape]-- / * per Alg D step D2 * / # ifdef TRACE_SORT if (trace_sort) elog (LOG, "worker% d finished writing run% d to tape% d:% s", state- > worker, state- > currentRun, state- > destTape, pg_rusage_show (& state- > ru_start)); # endif / / incomplete processing of all tuples, assign new tape if (! alltuples) selectnewtape (state) Third, follow-up and analysis

N/A

IV. Reference materials

Merge sort

Polyphase merge sort

Sorting Algorithms: Internal and External