PostgreSQL Source Code  git master
tuplesort.h
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * tuplesort.h
4  * Generalized tuple sorting routines.
5  *
6  * This module handles sorting of heap tuples, index tuples, or single
7  * Datums (and could easily support other kinds of sortable objects,
8  * if necessary). It works efficiently for both small and large amounts
9  * of data. Small amounts are sorted in-memory using qsort(). Large
10  * amounts are sorted using temporary files and a standard external sort
11  * algorithm. Parallel sorts use a variant of this external sort
12  * algorithm, and are typically only used for large amounts of data.
13  *
14  * Portions Copyright (c) 1996-2020, PostgreSQL Global Development Group
15  * Portions Copyright (c) 1994, Regents of the University of California
16  *
17  * src/include/utils/tuplesort.h
18  *
19  *-------------------------------------------------------------------------
20  */
21 #ifndef TUPLESORT_H
22 #define TUPLESORT_H
23 
24 #include "access/itup.h"
25 #include "executor/tuptable.h"
26 #include "storage/dsm.h"
27 #include "utils/relcache.h"
28 
29 
30 /*
31  * Tuplesortstate and Sharedsort are opaque types whose details are not
32  * known outside tuplesort.c.
33  */
35 typedef struct Sharedsort Sharedsort;
36 
37 /*
38  * Tuplesort parallel coordination state, allocated by each participant in
39  * local memory. Participant caller initializes everything. See usage notes
40  * below.
41  */
42 typedef struct SortCoordinateData
43 {
44  /* Worker process? If not, must be leader. */
45  bool isWorker;
46 
47  /*
48  * Leader-process-passed number of participants known launched (workers
49  * set this to -1). Includes state within leader needed for it to
50  * participate as a worker, if any.
51  */
53 
54  /* Private opaque state (points to shared memory) */
57 
59 
60 /*
61  * Data structures for reporting sort statistics. Note that
62  * TuplesortInstrumentation can't contain any pointers because we
63  * sometimes put it in shared memory.
64  *
65  * The parallel-sort infrastructure relies on having a zero TuplesortMethod
66  * to indicate that a worker never did anything, so we assign zero to
67  * SORT_TYPE_STILL_IN_PROGRESS. The other values of this enum can be
68  * OR'ed together to represent a situation where different workers used
69  * different methods, so we need a separate bit for each one. Keep the
70  * NUM_TUPLESORTMETHODS constant in sync with the number of bits!
71  */
72 typedef enum
73 {
80 
81 #define NUM_TUPLESORTMETHODS 4
82 
83 typedef enum
84 {
88 
90 {
91  TuplesortMethod sortMethod; /* sort algorithm used */
92  TuplesortSpaceType spaceType; /* type of space spaceUsed represents */
93  long spaceUsed; /* space consumption, in kB */
95 
96 
97 /*
98  * We provide multiple interfaces to what is essentially the same code,
99  * since different callers have different data to be sorted and want to
100  * specify the sort key information differently. There are two APIs for
101  * sorting HeapTuples and two more for sorting IndexTuples. Yet another
102  * API supports sorting bare Datums.
103  *
104  * Serial sort callers should pass NULL for their coordinate argument.
105  *
106  * The "heap" API actually stores/sorts MinimalTuples, which means it doesn't
107  * preserve the system columns (tuple identity and transaction visibility
108  * info). The sort keys are specified by column numbers within the tuples
109  * and sort operator OIDs. We save some cycles by passing and returning the
110  * tuples in TupleTableSlots, rather than forming actual HeapTuples (which'd
111  * have to be converted to MinimalTuples). This API works well for sorts
112  * executed as parts of plan trees.
113  *
114  * The "cluster" API stores/sorts full HeapTuples including all visibility
115  * info. The sort keys are specified by reference to a btree index that is
116  * defined on the relation to be sorted. Note that putheaptuple/getheaptuple
117  * go with this API, not the "begin_heap" one!
118  *
119  * The "index_btree" API stores/sorts IndexTuples (preserving all their
120  * header fields). The sort keys are specified by a btree index definition.
121  *
122  * The "index_hash" API is similar to index_btree, but the tuples are
123  * actually sorted by their hash codes not the raw data.
124  *
125  * Parallel sort callers are required to coordinate multiple tuplesort states
126  * in a leader process and one or more worker processes. The leader process
127  * must launch workers, and have each perform an independent "partial"
128  * tuplesort, typically fed by the parallel heap interface. The leader later
129  * produces the final output (internally, it merges runs output by workers).
130  *
131  * Callers must do the following to perform a sort in parallel using multiple
132  * worker processes:
133  *
134  * 1. Request tuplesort-private shared memory for n workers. Use
135  * tuplesort_estimate_shared() to get the required size.
136  * 2. Have leader process initialize allocated shared memory using
137  * tuplesort_initialize_shared(). Launch workers.
138  * 3. Initialize a coordinate argument within both the leader process, and
139  * for each worker process. This has a pointer to the shared
140  * tuplesort-private structure, as well as some caller-initialized fields.
141  * Leader's coordinate argument reliably indicates number of workers
142  * launched (this is unused by workers).
143  * 4. Begin a tuplesort using some appropriate tuplesort_begin* routine,
144  * (passing the coordinate argument) within each worker. The workMem
145  * arguments need not be identical. All other arguments should match
146  * exactly, though.
147  * 5. tuplesort_attach_shared() should be called by all workers. Feed tuples
148  * to each worker, and call tuplesort_performsort() within each when input
149  * is exhausted.
150  * 6. Call tuplesort_end() in each worker process. Worker processes can shut
151  * down once tuplesort_end() returns.
152  * 7. Begin a tuplesort in the leader using the same tuplesort_begin*
153  * routine, passing a leader-appropriate coordinate argument (this can
154  * happen as early as during step 3, actually, since we only need to know
155  * the number of workers successfully launched). The leader must now wait
156  * for workers to finish. Caller must use own mechanism for ensuring that
157  * next step isn't reached until all workers have called and returned from
158  * tuplesort_performsort(). (Note that it's okay if workers have already
159  * also called tuplesort_end() by then.)
160  * 8. Call tuplesort_performsort() in leader. Consume output using the
161  * appropriate tuplesort_get* routine. Leader can skip this step if
162  * tuplesort turns out to be unnecessary.
163  * 9. Call tuplesort_end() in leader.
164  *
165  * This division of labor assumes nothing about how input tuples are produced,
166  * but does require that caller combine the state of multiple tuplesorts for
167  * any purpose other than producing the final output. For example, callers
168  * must consider that tuplesort_get_stats() reports on only one worker's role
169  * in a sort (or the leader's role), and not statistics for the sort as a
170  * whole.
171  *
172  * Note that callers may use the leader process to sort runs as if it was an
173  * independent worker process (prior to the process performing a leader sort
174  * to produce the final sorted output). Doing so only requires a second
175  * "partial" tuplesort within the leader process, initialized like that of a
176  * worker process. The steps above don't touch on this directly. The only
177  * difference is that the tuplesort_attach_shared() call is never needed within
178  * leader process, because the backend as a whole holds the shared fileset
179  * reference. A worker Tuplesortstate in leader is expected to do exactly the
180  * same amount of total initial processing work as a worker process
181  * Tuplesortstate, since the leader process has nothing else to do before
182  * workers finish.
183  *
184  * Note that only a very small amount of memory will be allocated prior to
185  * the leader state first consuming input, and that workers will free the
186  * vast majority of their memory upon returning from tuplesort_performsort().
187  * Callers can rely on this to arrange for memory to be used in a way that
188  * respects a workMem-style budget across an entire parallel sort operation.
189  *
190  * Callers are responsible for parallel safety in general. However, they
191  * can at least rely on there being no parallel safety hazards within
192  * tuplesort, because tuplesort thinks of the sort as several independent
193  * sorts whose results are combined. Since, in general, the behavior of
194  * sort operators is immutable, caller need only worry about the parallel
195  * safety of whatever the process is through which input tuples are
196  * generated (typically, caller uses a parallel heap scan).
197  */
198 
200  int nkeys, AttrNumber *attNums,
201  Oid *sortOperators, Oid *sortCollations,
202  bool *nullsFirstFlags,
203  int workMem, SortCoordinate coordinate,
204  bool randomAccess);
206  Relation indexRel, int workMem,
207  SortCoordinate coordinate, bool randomAccess);
209  Relation indexRel,
210  bool enforceUnique,
211  int workMem, SortCoordinate coordinate,
212  bool randomAccess);
214  Relation indexRel,
215  uint32 high_mask,
216  uint32 low_mask,
217  uint32 max_buckets,
218  int workMem, SortCoordinate coordinate,
219  bool randomAccess);
220 extern Tuplesortstate *tuplesort_begin_datum(Oid datumType,
221  Oid sortOperator, Oid sortCollation,
222  bool nullsFirstFlag,
223  int workMem, SortCoordinate coordinate,
224  bool randomAccess);
225 
226 extern void tuplesort_set_bound(Tuplesortstate *state, int64 bound);
228 
230  TupleTableSlot *slot);
233  Relation rel, ItemPointer self,
234  Datum *values, bool *isnull);
236  bool isNull);
237 
239 
240 extern bool tuplesort_gettupleslot(Tuplesortstate *state, bool forward,
241  bool copy, TupleTableSlot *slot, Datum *abbrev);
244 extern bool tuplesort_getdatum(Tuplesortstate *state, bool forward,
245  Datum *val, bool *isNull, Datum *abbrev);
246 
247 extern bool tuplesort_skiptuples(Tuplesortstate *state, int64 ntuples,
248  bool forward);
249 
250 extern void tuplesort_end(Tuplesortstate *state);
251 
252 extern void tuplesort_reset(Tuplesortstate *state);
253 
255  TuplesortInstrumentation *stats);
256 extern const char *tuplesort_method_name(TuplesortMethod m);
257 extern const char *tuplesort_space_type_name(TuplesortSpaceType t);
258 
259 extern int tuplesort_merge_order(int64 allowedMem);
260 
261 extern Size tuplesort_estimate_shared(int nworkers);
262 extern void tuplesort_initialize_shared(Sharedsort *shared, int nWorkers,
263  dsm_segment *seg);
264 extern void tuplesort_attach_shared(Sharedsort *shared, dsm_segment *seg);
265 
266 /*
267  * These routines may only be called if randomAccess was specified 'true'.
268  * Likewise, backwards scan in gettuple/getdatum is only allowed if
269  * randomAccess was specified. Note that parallel sorts do not support
270  * randomAccess.
271  */
272 
276 
277 #endif /* TUPLESORT_H */
void tuplesort_puttupleslot(Tuplesortstate *state, TupleTableSlot *slot)
Definition: tuplesort.c:1608
struct TuplesortInstrumentation TuplesortInstrumentation
bool tuplesort_skiptuples(Tuplesortstate *state, int64 ntuples, bool forward)
Definition: tuplesort.c:2458
bool tuplesort_getdatum(Tuplesortstate *state, bool forward, Datum *val, bool *isNull, Datum *abbrev)
Definition: tuplesort.c:2418
TuplesortMethod
Definition: tuplesort.h:72
void tuplesort_putdatum(Tuplesortstate *state, Datum val, bool isNull)
Definition: tuplesort.c:1729
Tuplesortstate * tuplesort_begin_cluster(TupleDesc tupDesc, Relation indexRel, int workMem, SortCoordinate coordinate, bool randomAccess)
Definition: tuplesort.c:952
Sharedsort * sharedsort
Definition: tuplesort.h:55
const char * tuplesort_method_name(TuplesortMethod m)
Definition: tuplesort.c:3346
unsigned int Oid
Definition: postgres_ext.h:31
void tuplesort_performsort(Tuplesortstate *state)
Definition: tuplesort.c:1964
void tuplesort_restorepos(Tuplesortstate *state)
Definition: tuplesort.c:3268
void tuplesort_get_stats(Tuplesortstate *state, TuplesortInstrumentation *stats)
Definition: tuplesort.c:3302
void tuplesort_reset(Tuplesortstate *state)
Definition: tuplesort.c:1456
TuplesortMethod sortMethod
Definition: tuplesort.h:91
void tuplesort_rescan(Tuplesortstate *state)
Definition: tuplesort.c:3201
bool tuplesort_used_bound(Tuplesortstate *state)
Definition: tuplesort.c:1304
unsigned int uint32
Definition: c.h:367
void tuplesort_set_bound(Tuplesortstate *state, int64 bound)
Definition: tuplesort.c:1258
void tuplesort_putindextuplevalues(Tuplesortstate *state, Relation rel, ItemPointer self, Datum *values, bool *isnull)
Definition: tuplesort.c:1651
void tuplesort_markpos(Tuplesortstate *state)
Definition: tuplesort.c:3236
struct SortCoordinateData SortCoordinateData
HeapTuple tuplesort_getheaptuple(Tuplesortstate *state, bool forward)
Definition: tuplesort.c:2369
const char * tuplesort_space_type_name(TuplesortSpaceType t)
Definition: tuplesort.c:3369
void tuplesort_end(Tuplesortstate *state)
Definition: tuplesort.c:1388
struct SortCoordinateData * SortCoordinate
Definition: tuplesort.h:58
uintptr_t Datum
Definition: postgres.h:367
Tuplesortstate * tuplesort_begin_heap(TupleDesc tupDesc, int nkeys, AttrNumber *attNums, Oid *sortOperators, Oid *sortCollations, bool *nullsFirstFlags, int workMem, SortCoordinate coordinate, bool randomAccess)
Definition: tuplesort.c:878
IndexTuple tuplesort_getindextuple(Tuplesortstate *state, bool forward)
Definition: tuplesort.c:2389
Definition: regguts.h:298
void tuplesort_putheaptuple(Tuplesortstate *state, HeapTuple tup)
Definition: tuplesort.c:1630
Tuplesortstate * tuplesort_begin_index_hash(Relation heapRel, Relation indexRel, uint32 high_mask, uint32 low_mask, uint32 max_buckets, int workMem, SortCoordinate coordinate, bool randomAccess)
Definition: tuplesort.c:1125
TuplesortSpaceType
Definition: tuplesort.h:83
size_t Size
Definition: c.h:466
Tuplesortstate * tuplesort_begin_datum(Oid datumType, Oid sortOperator, Oid sortCollation, bool nullsFirstFlag, int workMem, SortCoordinate coordinate, bool randomAccess)
Definition: tuplesort.c:1171
void tuplesort_initialize_shared(Sharedsort *shared, int nWorkers, dsm_segment *seg)
Definition: tuplesort.c:4502
int tuplesort_merge_order(int64 allowedMem)
Definition: tuplesort.c:2526
static Datum values[MAXATTR]
Definition: bootstrap.c:167
void tuplesort_attach_shared(Sharedsort *shared, dsm_segment *seg)
Definition: tuplesort.c:4525
TuplesortSpaceType spaceType
Definition: tuplesort.h:92
int16 AttrNumber
Definition: attnum.h:21
bool tuplesort_gettupleslot(Tuplesortstate *state, bool forward, bool copy, TupleTableSlot *slot, Datum *abbrev)
Definition: tuplesort.c:2332
Tuplesortstate * tuplesort_begin_index_btree(Relation heapRel, Relation indexRel, bool enforceUnique, int workMem, SortCoordinate coordinate, bool randomAccess)
Definition: tuplesort.c:1047
long val
Definition: informix.c:664
Size tuplesort_estimate_shared(int nworkers)
Definition: tuplesort.c:4481