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.
12  *
13  * Portions Copyright (c) 1996-2017, PostgreSQL Global Development Group
14  * Portions Copyright (c) 1994, Regents of the University of California
15  *
16  * src/include/utils/tuplesort.h
17  *
18  *-------------------------------------------------------------------------
19  */
20 #ifndef TUPLESORT_H
21 #define TUPLESORT_H
22 
23 #include "access/itup.h"
24 #include "executor/tuptable.h"
25 #include "fmgr.h"
26 #include "utils/relcache.h"
27 
28 
29 /* Tuplesortstate is an opaque type whose details are not known outside
30  * tuplesort.c.
31  */
33 
34 /*
35  * Data structures for reporting sort statistics. Note that
36  * TuplesortInstrumentation can't contain any pointers because we
37  * sometimes put it in shared memory.
38  */
39 typedef enum
40 {
47 
48 typedef enum
49 {
53 
55 {
56  TuplesortMethod sortMethod; /* sort algorithm used */
57  TuplesortSpaceType spaceType; /* type of space spaceUsed represents */
58  long spaceUsed; /* space consumption, in kB */
60 
61 
62 /*
63  * We provide multiple interfaces to what is essentially the same code,
64  * since different callers have different data to be sorted and want to
65  * specify the sort key information differently. There are two APIs for
66  * sorting HeapTuples and two more for sorting IndexTuples. Yet another
67  * API supports sorting bare Datums.
68  *
69  * The "heap" API actually stores/sorts MinimalTuples, which means it doesn't
70  * preserve the system columns (tuple identity and transaction visibility
71  * info). The sort keys are specified by column numbers within the tuples
72  * and sort operator OIDs. We save some cycles by passing and returning the
73  * tuples in TupleTableSlots, rather than forming actual HeapTuples (which'd
74  * have to be converted to MinimalTuples). This API works well for sorts
75  * executed as parts of plan trees.
76  *
77  * The "cluster" API stores/sorts full HeapTuples including all visibility
78  * info. The sort keys are specified by reference to a btree index that is
79  * defined on the relation to be sorted. Note that putheaptuple/getheaptuple
80  * go with this API, not the "begin_heap" one!
81  *
82  * The "index_btree" API stores/sorts IndexTuples (preserving all their
83  * header fields). The sort keys are specified by a btree index definition.
84  *
85  * The "index_hash" API is similar to index_btree, but the tuples are
86  * actually sorted by their hash codes not the raw data.
87  */
88 
90  int nkeys, AttrNumber *attNums,
91  Oid *sortOperators, Oid *sortCollations,
92  bool *nullsFirstFlags,
93  int workMem, bool randomAccess);
95  Relation indexRel,
96  int workMem, bool randomAccess);
98  Relation indexRel,
99  bool enforceUnique,
100  int workMem, bool randomAccess);
102  Relation indexRel,
103  uint32 high_mask,
104  uint32 low_mask,
105  uint32 max_buckets,
106  int workMem, bool randomAccess);
107 extern Tuplesortstate *tuplesort_begin_datum(Oid datumType,
108  Oid sortOperator, Oid sortCollation,
109  bool nullsFirstFlag,
110  int workMem, bool randomAccess);
111 
112 extern void tuplesort_set_bound(Tuplesortstate *state, int64 bound);
113 
115  TupleTableSlot *slot);
118  Relation rel, ItemPointer self,
119  Datum *values, bool *isnull);
121  bool isNull);
122 
124 
125 extern bool tuplesort_gettupleslot(Tuplesortstate *state, bool forward,
126  bool copy, TupleTableSlot *slot, Datum *abbrev);
129 extern bool tuplesort_getdatum(Tuplesortstate *state, bool forward,
130  Datum *val, bool *isNull, Datum *abbrev);
131 
132 extern bool tuplesort_skiptuples(Tuplesortstate *state, int64 ntuples,
133  bool forward);
134 
135 extern void tuplesort_end(Tuplesortstate *state);
136 
138  TuplesortInstrumentation *stats);
139 extern const char *tuplesort_method_name(TuplesortMethod m);
140 extern const char *tuplesort_space_type_name(TuplesortSpaceType t);
141 
142 extern int tuplesort_merge_order(int64 allowedMem);
143 
144 /*
145  * These routines may only be called if randomAccess was specified 'true'.
146  * Likewise, backwards scan in gettuple/getdatum is only allowed if
147  * randomAccess was specified.
148  */
149 
153 
154 #endif /* TUPLESORT_H */
void tuplesort_puttupleslot(Tuplesortstate *state, TupleTableSlot *slot)
Definition: tuplesort.c:1301
struct TuplesortInstrumentation TuplesortInstrumentation
bool tuplesort_skiptuples(Tuplesortstate *state, int64 ntuples, bool forward)
Definition: tuplesort.c:2120
bool tuplesort_getdatum(Tuplesortstate *state, bool forward, Datum *val, bool *isNull, Datum *abbrev)
Definition: tuplesort.c:2081
TuplesortMethod
Definition: tuplesort.h:39
void tuplesort_putdatum(Tuplesortstate *state, Datum val, bool isNull)
Definition: tuplesort.c:1422
Tuplesortstate * tuplesort_begin_index_btree(Relation heapRel, Relation indexRel, bool enforceUnique, int workMem, bool randomAccess)
Definition: tuplesort.c:857
Tuplesortstate * tuplesort_begin_index_hash(Relation heapRel, Relation indexRel, uint32 high_mask, uint32 low_mask, uint32 max_buckets, int workMem, bool randomAccess)
Definition: tuplesort.c:932
const char * tuplesort_method_name(TuplesortMethod m)
Definition: tuplesort.c:2987
unsigned int Oid
Definition: postgres_ext.h:31
Tuplesortstate * tuplesort_begin_heap(TupleDesc tupDesc, int nkeys, AttrNumber *attNums, Oid *sortOperators, Oid *sortCollations, bool *nullsFirstFlags, int workMem, bool randomAccess)
Definition: tuplesort.c:693
void tuplesort_performsort(Tuplesortstate *state)
Definition: tuplesort.c:1655
void tuplesort_restorepos(Tuplesortstate *state)
Definition: tuplesort.c:2906
void tuplesort_get_stats(Tuplesortstate *state, TuplesortInstrumentation *stats)
Definition: tuplesort.c:2940
TuplesortMethod sortMethod
Definition: tuplesort.h:56
void tuplesort_rescan(Tuplesortstate *state)
Definition: tuplesort.c:2839
Tuplesortstate * tuplesort_begin_datum(Oid datumType, Oid sortOperator, Oid sortCollation, bool nullsFirstFlag, int workMem, bool randomAccess)
Definition: tuplesort.c:975
unsigned int uint32
Definition: c.h:296
void tuplesort_set_bound(Tuplesortstate *state, int64 bound)
Definition: tuplesort.c:1060
void tuplesort_putindextuplevalues(Tuplesortstate *state, Relation rel, ItemPointer self, Datum *values, bool *isnull)
Definition: tuplesort.c:1344
void tuplesort_markpos(Tuplesortstate *state)
Definition: tuplesort.c:2874
HeapTuple tuplesort_getheaptuple(Tuplesortstate *state, bool forward)
Definition: tuplesort.c:2032
const char * tuplesort_space_type_name(TuplesortSpaceType t)
Definition: tuplesort.c:3010
void tuplesort_end(Tuplesortstate *state)
Definition: tuplesort.c:1104
uintptr_t Datum
Definition: postgres.h:372
IndexTuple tuplesort_getindextuple(Tuplesortstate *state, bool forward)
Definition: tuplesort.c:2052
Definition: regguts.h:298
void tuplesort_putheaptuple(Tuplesortstate *state, HeapTuple tup)
Definition: tuplesort.c:1323
TuplesortSpaceType
Definition: tuplesort.h:48
int tuplesort_merge_order(int64 allowedMem)
Definition: tuplesort.c:2187
static Datum values[MAXATTR]
Definition: bootstrap.c:164
TuplesortSpaceType spaceType
Definition: tuplesort.h:57
int16 AttrNumber
Definition: attnum.h:21
bool tuplesort_gettupleslot(Tuplesortstate *state, bool forward, bool copy, TupleTableSlot *slot, Datum *abbrev)
Definition: tuplesort.c:1995
Tuplesortstate * tuplesort_begin_cluster(TupleDesc tupDesc, Relation indexRel, int workMem, bool randomAccess)
Definition: tuplesort.c:765
long val
Definition: informix.c:689