PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
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
23 #include "access/itup.h"
24 #include "executor/tuptable.h"
25 #include "fmgr.h"
26 #include "utils/relcache.h"
29 /* Tuplesortstate is an opaque type whose details are not known outside
30  * tuplesort.c.
31  */
34 /*
35  * We provide multiple interfaces to what is essentially the same code,
36  * since different callers have different data to be sorted and want to
37  * specify the sort key information differently. There are two APIs for
38  * sorting HeapTuples and two more for sorting IndexTuples. Yet another
39  * API supports sorting bare Datums.
40  *
41  * The "heap" API actually stores/sorts MinimalTuples, which means it doesn't
42  * preserve the system columns (tuple identity and transaction visibility
43  * info). The sort keys are specified by column numbers within the tuples
44  * and sort operator OIDs. We save some cycles by passing and returning the
45  * tuples in TupleTableSlots, rather than forming actual HeapTuples (which'd
46  * have to be converted to MinimalTuples). This API works well for sorts
47  * executed as parts of plan trees.
48  *
49  * The "cluster" API stores/sorts full HeapTuples including all visibility
50  * info. The sort keys are specified by reference to a btree index that is
51  * defined on the relation to be sorted. Note that putheaptuple/getheaptuple
52  * go with this API, not the "begin_heap" one!
53  *
54  * The "index_btree" API stores/sorts IndexTuples (preserving all their
55  * header fields). The sort keys are specified by a btree index definition.
56  *
57  * The "index_hash" API is similar to index_btree, but the tuples are
58  * actually sorted by their hash codes not the raw data.
59  */
62  int nkeys, AttrNumber *attNums,
63  Oid *sortOperators, Oid *sortCollations,
64  bool *nullsFirstFlags,
65  int workMem, bool randomAccess);
68  int workMem, bool randomAccess);
71  bool enforceUnique,
72  int workMem, bool randomAccess);
78  int workMem, bool randomAccess);
80  Oid sortOperator, Oid sortCollation,
81  bool nullsFirstFlag,
82  int workMem, bool randomAccess);
84 extern void tuplesort_set_bound(Tuplesortstate *state, int64 bound);
87  TupleTableSlot *slot);
90  Relation rel, ItemPointer self,
91  Datum *values, bool *isnull);
93  bool isNull);
97 extern bool tuplesort_gettupleslot(Tuplesortstate *state, bool forward,
98  bool copy, TupleTableSlot *slot, Datum *abbrev);
101 extern bool tuplesort_getdatum(Tuplesortstate *state, bool forward,
102  Datum *val, bool *isNull, Datum *abbrev);
104 extern bool tuplesort_skiptuples(Tuplesortstate *state, int64 ntuples,
105  bool forward);
107 extern void tuplesort_end(Tuplesortstate *state);
110  const char **sortMethod,
111  const char **spaceType,
112  long *spaceUsed);
114 extern int tuplesort_merge_order(int64 allowedMem);
116 /*
117  * These routines may only be called if randomAccess was specified 'true'.
118  * Likewise, backwards scan in gettuple/getdatum is only allowed if
119  * randomAccess was specified.
120  */
126 #endif /* TUPLESORT_H */
void tuplesort_puttupleslot(Tuplesortstate *state, TupleTableSlot *slot)
Definition: tuplesort.c:1364
Relation heapRel
Definition: tuplesort.c:470
bool tuplesort_skiptuples(Tuplesortstate *state, int64 ntuples, bool forward)
Definition: tuplesort.c:2238
bool tuplesort_getdatum(Tuplesortstate *state, bool forward, Datum *val, bool *isNull, Datum *abbrev)
Definition: tuplesort.c:2199
void tuplesort_putdatum(Tuplesortstate *state, Datum val, bool isNull)
Definition: tuplesort.c:1485
Tuplesortstate * tuplesort_begin_index_btree(Relation heapRel, Relation indexRel, bool enforceUnique, int workMem, bool randomAccess)
Definition: tuplesort.c:920
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:995
bool randomAccess
Definition: tuplesort.c:275
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:756
void tuplesort_performsort(Tuplesortstate *state)
Definition: tuplesort.c:1773
void tuplesort_restorepos(Tuplesortstate *state)
Definition: tuplesort.c:3198
uint32 high_mask
Definition: tuplesort.c:477
void tuplesort_rescan(Tuplesortstate *state)
Definition: tuplesort.c:3131
Tuplesortstate * tuplesort_begin_datum(Oid datumType, Oid sortOperator, Oid sortCollation, bool nullsFirstFlag, int workMem, bool randomAccess)
Definition: tuplesort.c:1038
unsigned int uint32
Definition: c.h:268
void tuplesort_set_bound(Tuplesortstate *state, int64 bound)
Definition: tuplesort.c:1123
int64 allowedMem
Definition: tuplesort.c:282
void tuplesort_putindextuplevalues(Tuplesortstate *state, Relation rel, ItemPointer self, Datum *values, bool *isnull)
Definition: tuplesort.c:1407
void tuplesort_markpos(Tuplesortstate *state)
Definition: tuplesort.c:3166
HeapTuple tuplesort_getheaptuple(Tuplesortstate *state, bool forward)
Definition: tuplesort.c:2150
void tuplesort_end(Tuplesortstate *state)
Definition: tuplesort.c:1167
Relation indexRel
Definition: tuplesort.c:471
uintptr_t Datum
Definition: postgres.h:372
void tuplesort_get_stats(Tuplesortstate *state, const char **sortMethod, const char **spaceType, long *spaceUsed)
Definition: tuplesort.c:3233
IndexTuple tuplesort_getindextuple(Tuplesortstate *state, bool forward)
Definition: tuplesort.c:2170
Definition: regguts.h:298
bool enforceUnique
Definition: tuplesort.c:474
void tuplesort_putheaptuple(Tuplesortstate *state, HeapTuple tup)
Definition: tuplesort.c:1386
uint32 max_buckets
Definition: tuplesort.c:479
int tuplesort_merge_order(int64 allowedMem)
Definition: tuplesort.c:2305
static Datum values[MAXATTR]
Definition: bootstrap.c:163
uint32 low_mask
Definition: tuplesort.c:478
int16 AttrNumber
Definition: attnum.h:21
bool tuplesort_gettupleslot(Tuplesortstate *state, bool forward, bool copy, TupleTableSlot *slot, Datum *abbrev)
Definition: tuplesort.c:2113
Tuplesortstate * tuplesort_begin_cluster(TupleDesc tupDesc, Relation indexRel, int workMem, bool randomAccess)
Definition: tuplesort.c:828
long val
Definition: informix.c:689
TupleDesc tupDesc
Definition: tuplesort.c:441