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-2016, 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 */ 32 typedef struct Tuplesortstate Tuplesortstate; 33 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 */ 60 61 extern Tuplesortstate *tuplesort_begin_heap(TupleDesc tupDesc, 62 int nkeys, AttrNumber *attNums, 63 Oid *sortOperators, Oid *sortCollations, 64 bool *nullsFirstFlags, 65 int workMem, bool randomAccess); 66 extern Tuplesortstate *tuplesort_begin_cluster(TupleDesc tupDesc, 67 Relation indexRel, 68 int workMem, bool randomAccess); 69 extern Tuplesortstate *tuplesort_begin_index_btree(Relation heapRel, 70 Relation indexRel, 71 bool enforceUnique, 72 int workMem, bool randomAccess); 73 extern Tuplesortstate *tuplesort_begin_index_hash(Relation heapRel, 74 Relation indexRel, 75 uint32 hash_mask, 76 int workMem, bool randomAccess); 77 extern Tuplesortstate *tuplesort_begin_datum(Oid datumType, 78 Oid sortOperator, Oid sortCollation, 79 bool nullsFirstFlag, 80 int workMem, bool randomAccess); 81 82 extern void tuplesort_set_bound(Tuplesortstate *state, int64 bound); 83 84 extern void tuplesort_puttupleslot(Tuplesortstate *state, 85 TupleTableSlot *slot); 86 extern void tuplesort_putheaptuple(Tuplesortstate *state, HeapTuple tup); 87 extern void tuplesort_putindextuplevalues(Tuplesortstate *state, 88 Relation rel, ItemPointer self, 89 Datum *values, bool *isnull); 90 extern void tuplesort_putdatum(Tuplesortstate *state, Datum val, 91 bool isNull); 92 93 extern void tuplesort_performsort(Tuplesortstate *state); 94 95 extern bool tuplesort_gettupleslot(Tuplesortstate *state, bool forward, 96 TupleTableSlot *slot, Datum *abbrev); 97 extern HeapTuple tuplesort_getheaptuple(Tuplesortstate *state, bool forward, 98 bool *should_free); 99 extern IndexTuple tuplesort_getindextuple(Tuplesortstate *state, bool forward, 100 bool *should_free); 101 extern bool tuplesort_getdatum(Tuplesortstate *state, bool forward, 102 Datum *val, bool *isNull, Datum *abbrev); 103 104 extern bool tuplesort_skiptuples(Tuplesortstate *state, int64 ntuples, 105 bool forward); 106 107 extern void tuplesort_end(Tuplesortstate *state); 108 109 extern void tuplesort_get_stats(Tuplesortstate *state, 110 const char **sortMethod, 111 const char **spaceType, 112 long *spaceUsed); 113 114 extern int tuplesort_merge_order(int64 allowedMem); 115 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 */ 121 122 extern void tuplesort_rescan(Tuplesortstate *state); 123 extern void tuplesort_markpos(Tuplesortstate *state); 124 extern void tuplesort_restorepos(Tuplesortstate *state); 125 126 #endif /* TUPLESORT_H */ 127