codekingpro/portable-devtools

1/*-------------------------------------------------------------------------2 *3 * tuplesort.h4 *	  Generalized tuple sorting routines.5 *6 * This module handles sorting of heap tuples, index tuples, or single7 * Datums (and could easily support other kinds of sortable objects,8 * if necessary).  It works efficiently for both small and large amounts9 * of data.  Small amounts are sorted in-memory using qsort().  Large10 * amounts are sorted using temporary files and a standard external sort11 * algorithm.  Parallel sorts use a variant of this external sort12 * algorithm, and are typically only used for large amounts of data.13 *14 * Portions Copyright (c) 1996-2023, PostgreSQL Global Development Group15 * Portions Copyright (c) 1994, Regents of the University of California16 *17 * src/include/utils/tuplesort.h18 *19 *-------------------------------------------------------------------------20 */21#ifndef TUPLESORT_H22#define TUPLESORT_H23 24#include "access/itup.h"25#include "executor/tuptable.h"26#include "storage/dsm.h"27#include "utils/logtape.h"28#include "utils/relcache.h"29#include "utils/sortsupport.h"30 31 32/*33 * Tuplesortstate and Sharedsort are opaque types whose details are not34 * known outside tuplesort.c.35 */36typedef struct Tuplesortstate Tuplesortstate;37typedef struct Sharedsort Sharedsort;38 39/*40 * Tuplesort parallel coordination state, allocated by each participant in41 * local memory.  Participant caller initializes everything.  See usage notes42 * below.43 */44typedef struct SortCoordinateData45{46	/* Worker process?  If not, must be leader. */47	bool		isWorker;48 49	/*50	 * Leader-process-passed number of participants known launched (workers51	 * set this to -1).  Includes state within leader needed for it to52	 * participate as a worker, if any.53	 */54	int			nParticipants;55 56	/* Private opaque state (points to shared memory) */57	Sharedsort *sharedsort;58}			SortCoordinateData;59 60typedef struct SortCoordinateData *SortCoordinate;61 62/*63 * Data structures for reporting sort statistics.  Note that64 * TuplesortInstrumentation can't contain any pointers because we65 * sometimes put it in shared memory.66 *67 * The parallel-sort infrastructure relies on having a zero TuplesortMethod68 * to indicate that a worker never did anything, so we assign zero to69 * SORT_TYPE_STILL_IN_PROGRESS.  The other values of this enum can be70 * OR'ed together to represent a situation where different workers used71 * different methods, so we need a separate bit for each one.  Keep the72 * NUM_TUPLESORTMETHODS constant in sync with the number of bits!73 */74typedef enum75{76	SORT_TYPE_STILL_IN_PROGRESS = 0,77	SORT_TYPE_TOP_N_HEAPSORT = 1 << 0,78	SORT_TYPE_QUICKSORT = 1 << 1,79	SORT_TYPE_EXTERNAL_SORT = 1 << 2,80	SORT_TYPE_EXTERNAL_MERGE = 1 << 381} TuplesortMethod;82 83#define NUM_TUPLESORTMETHODS 484 85typedef enum86{87	SORT_SPACE_TYPE_DISK,88	SORT_SPACE_TYPE_MEMORY89} TuplesortSpaceType;90 91/* Bitwise option flags for tuple sorts */92#define TUPLESORT_NONE					093 94/* specifies whether non-sequential access to the sort result is required */95#define	TUPLESORT_RANDOMACCESS			(1 << 0)96 97/* specifies if the tuplesort is able to support bounded sorts */98#define TUPLESORT_ALLOWBOUNDED			(1 << 1)99 100typedef struct TuplesortInstrumentation101{102	TuplesortMethod sortMethod; /* sort algorithm used */103	TuplesortSpaceType spaceType;	/* type of space spaceUsed represents */104	int64		spaceUsed;		/* space consumption, in kB */105} TuplesortInstrumentation;106 107/*108 * The objects we actually sort are SortTuple structs.  These contain109 * a pointer to the tuple proper (might be a MinimalTuple or IndexTuple),110 * which is a separate palloc chunk --- we assume it is just one chunk and111 * can be freed by a simple pfree() (except during merge, when we use a112 * simple slab allocator).  SortTuples also contain the tuple's first key113 * column in Datum/nullflag format, and a source/input tape number that114 * tracks which tape each heap element/slot belongs to during merging.115 *116 * Storing the first key column lets us save heap_getattr or index_getattr117 * calls during tuple comparisons.  We could extract and save all the key118 * columns not just the first, but this would increase code complexity and119 * overhead, and wouldn't actually save any comparison cycles in the common120 * case where the first key determines the comparison result.  Note that121 * for a pass-by-reference datatype, datum1 points into the "tuple" storage.122 *123 * There is one special case: when the sort support infrastructure provides an124 * "abbreviated key" representation, where the key is (typically) a pass by125 * value proxy for a pass by reference type.  In this case, the abbreviated key126 * is stored in datum1 in place of the actual first key column.127 *128 * When sorting single Datums, the data value is represented directly by129 * datum1/isnull1 for pass by value types (or null values).  If the datatype is130 * pass-by-reference and isnull1 is false, then "tuple" points to a separately131 * palloc'd data value, otherwise "tuple" is NULL.  The value of datum1 is then132 * either the same pointer as "tuple", or is an abbreviated key value as133 * described above.  Accordingly, "tuple" is always used in preference to134 * datum1 as the authoritative value for pass-by-reference cases.135 */136typedef struct137{138	void	   *tuple;			/* the tuple itself */139	Datum		datum1;			/* value of first key column */140	bool		isnull1;		/* is first key column NULL? */141	int			srctape;		/* source tape number */142} SortTuple;143 144typedef int (*SortTupleComparator) (const SortTuple *a, const SortTuple *b,145									Tuplesortstate *state);146 147/*148 * The public part of a Tuple sort operation state.  This data structure149 * contains the definition of sort-variant-specific interface methods and150 * the part of Tuple sort operation state required by their implementations.151 */152typedef struct153{154	/*155	 * These function pointers decouple the routines that must know what kind156	 * of tuple we are sorting from the routines that don't need to know it.157	 * They are set up by the tuplesort_begin_xxx routines.158	 *159	 * Function to compare two tuples; result is per qsort() convention, ie:160	 * <0, 0, >0 according as a<b, a=b, a>b.  The API must match161	 * qsort_arg_comparator.162	 */163	SortTupleComparator comparetup;164 165	/*166	 * Alter datum1 representation in the SortTuple's array back from the167	 * abbreviated key to the first column value.168	 */169	void		(*removeabbrev) (Tuplesortstate *state, SortTuple *stups,170								 int count);171 172	/*173	 * Function to write a stored tuple onto tape.  The representation of the174	 * tuple on tape need not be the same as it is in memory.175	 */176	void		(*writetup) (Tuplesortstate *state, LogicalTape *tape,177							 SortTuple *stup);178 179	/*180	 * Function to read a stored tuple from tape back into memory. 'len' is181	 * the already-read length of the stored tuple.  The tuple is allocated182	 * from the slab memory arena, or is palloc'd, see183	 * tuplesort_readtup_alloc().184	 */185	void		(*readtup) (Tuplesortstate *state, SortTuple *stup,186							LogicalTape *tape, unsigned int len);187 188	/*189	 * Function to do some specific release of resources for the sort variant.190	 * In particular, this function should free everything stored in the "arg"191	 * field, which wouldn't be cleared on reset of the Tuple sort memory192	 * contexts.  This can be NULL if nothing specific needs to be done.193	 */194	void		(*freestate) (Tuplesortstate *state);195 196	/*197	 * The subsequent fields are used in the implementations of the functions198	 * above.199	 */200	MemoryContext maincontext;	/* memory context for tuple sort metadata that201								 * persists across multiple batches */202	MemoryContext sortcontext;	/* memory context holding most sort data */203	MemoryContext tuplecontext; /* sub-context of sortcontext for tuple data */204 205	/*206	 * Whether SortTuple's datum1 and isnull1 members are maintained by the207	 * above routines.  If not, some sort specializations are disabled.208	 */209	bool		haveDatum1;210 211	/*212	 * The sortKeys variable is used by every case other than the hash index213	 * case; it is set by tuplesort_begin_xxx.  tupDesc is only used by the214	 * MinimalTuple and CLUSTER routines, though.215	 */216	int			nKeys;			/* number of columns in sort key */217	SortSupport sortKeys;		/* array of length nKeys */218 219	/*220	 * This variable is shared by the single-key MinimalTuple case and the221	 * Datum case (which both use qsort_ssup()).  Otherwise, it's NULL.  The222	 * presence of a value in this field is also checked by various sort223	 * specialization functions as an optimization when comparing the leading224	 * key in a tiebreak situation to determine if there are any subsequent225	 * keys to sort on.226	 */227	SortSupport onlyKey;228 229	int			sortopt;		/* Bitmask of flags used to setup sort */230 231	bool		tuples;			/* Can SortTuple.tuple ever be set? */232 233	void	   *arg;			/* Specific information for the sort variant */234} TuplesortPublic;235 236/* Sort parallel code from state for sort__start probes */237#define PARALLEL_SORT(coordinate)	(coordinate == NULL || \238									 (coordinate)->sharedsort == NULL ? 0 : \239									 (coordinate)->isWorker ? 1 : 2)240 241#define TuplesortstateGetPublic(state) ((TuplesortPublic *) state)242 243/* When using this macro, beware of double evaluation of len */244#define LogicalTapeReadExact(tape, ptr, len) \245	do { \246		if (LogicalTapeRead(tape, ptr, len) != (size_t) (len)) \247			elog(ERROR, "unexpected end of data"); \248	} while(0)249 250/*251 * We provide multiple interfaces to what is essentially the same code,252 * since different callers have different data to be sorted and want to253 * specify the sort key information differently.  There are two APIs for254 * sorting HeapTuples and two more for sorting IndexTuples.  Yet another255 * API supports sorting bare Datums.256 *257 * Serial sort callers should pass NULL for their coordinate argument.258 *259 * The "heap" API actually stores/sorts MinimalTuples, which means it doesn't260 * preserve the system columns (tuple identity and transaction visibility261 * info).  The sort keys are specified by column numbers within the tuples262 * and sort operator OIDs.  We save some cycles by passing and returning the263 * tuples in TupleTableSlots, rather than forming actual HeapTuples (which'd264 * have to be converted to MinimalTuples).  This API works well for sorts265 * executed as parts of plan trees.266 *267 * The "cluster" API stores/sorts full HeapTuples including all visibility268 * info. The sort keys are specified by reference to a btree index that is269 * defined on the relation to be sorted.  Note that putheaptuple/getheaptuple270 * go with this API, not the "begin_heap" one!271 *272 * The "index_btree" API stores/sorts IndexTuples (preserving all their273 * header fields).  The sort keys are specified by a btree index definition.274 *275 * The "index_hash" API is similar to index_btree, but the tuples are276 * actually sorted by their hash codes not the raw data.277 *278 * Parallel sort callers are required to coordinate multiple tuplesort states279 * in a leader process and one or more worker processes.  The leader process280 * must launch workers, and have each perform an independent "partial"281 * tuplesort, typically fed by the parallel heap interface.  The leader later282 * produces the final output (internally, it merges runs output by workers).283 *284 * Callers must do the following to perform a sort in parallel using multiple285 * worker processes:286 *287 * 1. Request tuplesort-private shared memory for n workers.  Use288 *    tuplesort_estimate_shared() to get the required size.289 * 2. Have leader process initialize allocated shared memory using290 *    tuplesort_initialize_shared().  Launch workers.291 * 3. Initialize a coordinate argument within both the leader process, and292 *    for each worker process.  This has a pointer to the shared293 *    tuplesort-private structure, as well as some caller-initialized fields.294 *    Leader's coordinate argument reliably indicates number of workers295 *    launched (this is unused by workers).296 * 4. Begin a tuplesort using some appropriate tuplesort_begin* routine,297 *    (passing the coordinate argument) within each worker.  The workMem298 *    arguments need not be identical.  All other arguments should match299 *    exactly, though.300 * 5. tuplesort_attach_shared() should be called by all workers.  Feed tuples301 *    to each worker, and call tuplesort_performsort() within each when input302 *    is exhausted.303 * 6. Call tuplesort_end() in each worker process.  Worker processes can shut304 *    down once tuplesort_end() returns.305 * 7. Begin a tuplesort in the leader using the same tuplesort_begin*306 *    routine, passing a leader-appropriate coordinate argument (this can307 *    happen as early as during step 3, actually, since we only need to know308 *    the number of workers successfully launched).  The leader must now wait309 *    for workers to finish.  Caller must use own mechanism for ensuring that310 *    next step isn't reached until all workers have called and returned from311 *    tuplesort_performsort().  (Note that it's okay if workers have already312 *    also called tuplesort_end() by then.)313 * 8. Call tuplesort_performsort() in leader.  Consume output using the314 *    appropriate tuplesort_get* routine.  Leader can skip this step if315 *    tuplesort turns out to be unnecessary.316 * 9. Call tuplesort_end() in leader.317 *318 * This division of labor assumes nothing about how input tuples are produced,319 * but does require that caller combine the state of multiple tuplesorts for320 * any purpose other than producing the final output.  For example, callers321 * must consider that tuplesort_get_stats() reports on only one worker's role322 * in a sort (or the leader's role), and not statistics for the sort as a323 * whole.324 *325 * Note that callers may use the leader process to sort runs as if it was an326 * independent worker process (prior to the process performing a leader sort327 * to produce the final sorted output).  Doing so only requires a second328 * "partial" tuplesort within the leader process, initialized like that of a329 * worker process.  The steps above don't touch on this directly.  The only330 * difference is that the tuplesort_attach_shared() call is never needed within331 * leader process, because the backend as a whole holds the shared fileset332 * reference.  A worker Tuplesortstate in leader is expected to do exactly the333 * same amount of total initial processing work as a worker process334 * Tuplesortstate, since the leader process has nothing else to do before335 * workers finish.336 *337 * Note that only a very small amount of memory will be allocated prior to338 * the leader state first consuming input, and that workers will free the339 * vast majority of their memory upon returning from tuplesort_performsort().340 * Callers can rely on this to arrange for memory to be used in a way that341 * respects a workMem-style budget across an entire parallel sort operation.342 *343 * Callers are responsible for parallel safety in general.  However, they344 * can at least rely on there being no parallel safety hazards within345 * tuplesort, because tuplesort thinks of the sort as several independent346 * sorts whose results are combined.  Since, in general, the behavior of347 * sort operators is immutable, caller need only worry about the parallel348 * safety of whatever the process is through which input tuples are349 * generated (typically, caller uses a parallel heap scan).350 */351 352 353extern Tuplesortstate *tuplesort_begin_common(int workMem,354											  SortCoordinate coordinate,355											  int sortopt);356extern void tuplesort_set_bound(Tuplesortstate *state, int64 bound);357extern bool tuplesort_used_bound(Tuplesortstate *state);358extern void tuplesort_puttuple_common(Tuplesortstate *state,359									  SortTuple *tuple, bool useAbbrev);360extern void tuplesort_performsort(Tuplesortstate *state);361extern bool tuplesort_gettuple_common(Tuplesortstate *state, bool forward,362									  SortTuple *stup);363extern bool tuplesort_skiptuples(Tuplesortstate *state, int64 ntuples,364								 bool forward);365extern void tuplesort_end(Tuplesortstate *state);366extern void tuplesort_reset(Tuplesortstate *state);367 368extern void tuplesort_get_stats(Tuplesortstate *state,369								TuplesortInstrumentation *stats);370extern const char *tuplesort_method_name(TuplesortMethod m);371extern const char *tuplesort_space_type_name(TuplesortSpaceType t);372 373extern int	tuplesort_merge_order(int64 allowedMem);374 375extern Size tuplesort_estimate_shared(int nWorkers);376extern void tuplesort_initialize_shared(Sharedsort *shared, int nWorkers,377										dsm_segment *seg);378extern void tuplesort_attach_shared(Sharedsort *shared, dsm_segment *seg);379 380/*381 * These routines may only be called if TUPLESORT_RANDOMACCESS was specified382 * during tuplesort_begin_*.  Additionally backwards scan in gettuple/getdatum383 * also require TUPLESORT_RANDOMACCESS.  Note that parallel sorts do not384 * support random access.385 */386extern void tuplesort_rescan(Tuplesortstate *state);387extern void tuplesort_markpos(Tuplesortstate *state);388extern void tuplesort_restorepos(Tuplesortstate *state);389 390extern void *tuplesort_readtup_alloc(Tuplesortstate *state, Size tuplen);391 392 393/* tuplesortvariants.c */394 395extern Tuplesortstate *tuplesort_begin_heap(TupleDesc tupDesc,396											int nkeys, AttrNumber *attNums,397											Oid *sortOperators, Oid *sortCollations,398											bool *nullsFirstFlags,399											int workMem, SortCoordinate coordinate,400											int sortopt);401extern Tuplesortstate *tuplesort_begin_cluster(TupleDesc tupDesc,402											   Relation indexRel, int workMem,403											   SortCoordinate coordinate,404											   int sortopt);405extern Tuplesortstate *tuplesort_begin_index_btree(Relation heapRel,406												   Relation indexRel,407												   bool enforceUnique,408												   bool uniqueNullsNotDistinct,409												   int workMem, SortCoordinate coordinate,410												   int sortopt);411extern Tuplesortstate *tuplesort_begin_index_hash(Relation heapRel,412												  Relation indexRel,413												  uint32 high_mask,414												  uint32 low_mask,415												  uint32 max_buckets,416												  int workMem, SortCoordinate coordinate,417												  int sortopt);418extern Tuplesortstate *tuplesort_begin_index_gist(Relation heapRel,419												  Relation indexRel,420												  int workMem, SortCoordinate coordinate,421												  int sortopt);422extern Tuplesortstate *tuplesort_begin_datum(Oid datumType,423											 Oid sortOperator, Oid sortCollation,424											 bool nullsFirstFlag,425											 int workMem, SortCoordinate coordinate,426											 int sortopt);427 428extern void tuplesort_puttupleslot(Tuplesortstate *state,429								   TupleTableSlot *slot);430extern void tuplesort_putheaptuple(Tuplesortstate *state, HeapTuple tup);431extern void tuplesort_putindextuplevalues(Tuplesortstate *state,432										  Relation rel, ItemPointer self,433										  Datum *values, bool *isnull);434extern void tuplesort_putdatum(Tuplesortstate *state, Datum val,435							   bool isNull);436 437extern bool tuplesort_gettupleslot(Tuplesortstate *state, bool forward,438								   bool copy, TupleTableSlot *slot, Datum *abbrev);439extern HeapTuple tuplesort_getheaptuple(Tuplesortstate *state, bool forward);440extern IndexTuple tuplesort_getindextuple(Tuplesortstate *state, bool forward);441extern bool tuplesort_getdatum(Tuplesortstate *state, bool forward, bool copy,442							   Datum *val, bool *isNull, Datum *abbrev);443 444 445#endif							/* TUPLESORT_H */446