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);
76  int workMem, bool randomAccess);
78  Oid sortOperator, Oid sortCollation,
79  bool nullsFirstFlag,
80  int workMem, bool randomAccess);
82 extern void tuplesort_set_bound(Tuplesortstate *state, int64 bound);
85  TupleTableSlot *slot);
88  Relation rel, ItemPointer self,
89  Datum *values, bool *isnull);
91  bool isNull);
95 extern bool tuplesort_gettupleslot(Tuplesortstate *state, bool forward,
96  TupleTableSlot *slot, Datum *abbrev);
99 extern bool tuplesort_getdatum(Tuplesortstate *state, bool forward,
100  Datum *val, bool *isNull, Datum *abbrev);
102 extern bool tuplesort_skiptuples(Tuplesortstate *state, int64 ntuples,
103  bool forward);
105 extern void tuplesort_end(Tuplesortstate *state);
108  const char **sortMethod,
109  const char **spaceType,
110  long *spaceUsed);
112 extern int tuplesort_merge_order(int64 allowedMem);
114 /*
115  * These routines may only be called if randomAccess was specified 'true'.
116  * Likewise, backwards scan in gettuple/getdatum is only allowed if
117  * randomAccess was specified.
118  */
124 #endif /* TUPLESORT_H */
void tuplesort_puttupleslot(Tuplesortstate *state, TupleTableSlot *slot)
Definition: tuplesort.c:1354
Relation heapRel
Definition: tuplesort.c:469
bool tuplesort_skiptuples(Tuplesortstate *state, int64 ntuples, bool forward)
Definition: tuplesort.c:2222
bool tuplesort_getdatum(Tuplesortstate *state, bool forward, Datum *val, bool *isNull, Datum *abbrev)
Definition: tuplesort.c:2183
bool tuplesort_gettupleslot(Tuplesortstate *state, bool forward, TupleTableSlot *slot, Datum *abbrev)
Definition: tuplesort.c:2099
void tuplesort_putdatum(Tuplesortstate *state, Datum val, bool isNull)
Definition: tuplesort.c:1475
Tuplesortstate * tuplesort_begin_index_btree(Relation heapRel, Relation indexRel, bool enforceUnique, int workMem, bool randomAccess)
Definition: tuplesort.c:917
bool randomAccess
Definition: tuplesort.c:274
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:753
void tuplesort_performsort(Tuplesortstate *state)
Definition: tuplesort.c:1763
void tuplesort_restorepos(Tuplesortstate *state)
Definition: tuplesort.c:3182
void hash_mask(char *pagedata, BlockNumber blkno)
Definition: hash_xlog.c:1228
void tuplesort_rescan(Tuplesortstate *state)
Definition: tuplesort.c:3115
Tuplesortstate * tuplesort_begin_index_hash(Relation heapRel, Relation indexRel, uint32 hash_mask, int workMem, bool randomAccess)
Definition: tuplesort.c:992
Tuplesortstate * tuplesort_begin_datum(Oid datumType, Oid sortOperator, Oid sortCollation, bool nullsFirstFlag, int workMem, bool randomAccess)
Definition: tuplesort.c:1028
unsigned int uint32
Definition: c.h:268
void tuplesort_set_bound(Tuplesortstate *state, int64 bound)
Definition: tuplesort.c:1113
int64 allowedMem
Definition: tuplesort.c:281
void tuplesort_putindextuplevalues(Tuplesortstate *state, Relation rel, ItemPointer self, Datum *values, bool *isnull)
Definition: tuplesort.c:1397
void tuplesort_markpos(Tuplesortstate *state)
Definition: tuplesort.c:3150
HeapTuple tuplesort_getheaptuple(Tuplesortstate *state, bool forward)
Definition: tuplesort.c:2134
void tuplesort_end(Tuplesortstate *state)
Definition: tuplesort.c:1157
Relation indexRel
Definition: tuplesort.c:470
uintptr_t Datum
Definition: postgres.h:372
void tuplesort_get_stats(Tuplesortstate *state, const char **sortMethod, const char **spaceType, long *spaceUsed)
Definition: tuplesort.c:3217
IndexTuple tuplesort_getindextuple(Tuplesortstate *state, bool forward)
Definition: tuplesort.c:2154
Definition: regguts.h:298
bool enforceUnique
Definition: tuplesort.c:473
void tuplesort_putheaptuple(Tuplesortstate *state, HeapTuple tup)
Definition: tuplesort.c:1376
int tuplesort_merge_order(int64 allowedMem)
Definition: tuplesort.c:2289
static Datum values[MAXATTR]
Definition: bootstrap.c:162
int16 AttrNumber
Definition: attnum.h:21
Tuplesortstate * tuplesort_begin_cluster(TupleDesc tupDesc, Relation indexRel, int workMem, bool randomAccess)
Definition: tuplesort.c:825
long val
Definition: informix.c:689
TupleDesc tupDesc
Definition: tuplesort.c:440