1 /*-------------------------------------------------------------------------
4 * Generalized tuple sorting routines.
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
13 * Portions Copyright (c) 1996-2011, PostgreSQL Global Development Group
14 * Portions Copyright (c) 1994, Regents of the University of California
16 * src/include/utils/tuplesort.h
18 *-------------------------------------------------------------------------
23 #include "access/itup.h"
24 #include "executor/tuptable.h"
26 #include "utils/relcache.h"
29 /* Tuplesortstate is an opaque type whose details are not known outside
32 typedef struct Tuplesortstate Tuplesortstate;
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.
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.
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!
54 * The "index_btree" API stores/sorts IndexTuples (preserving all their
55 * header fields). The sort keys are specified by a btree index definition.
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.
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,
68 int workMem, bool randomAccess);
69 extern Tuplesortstate *tuplesort_begin_index_btree(Relation indexRel,
71 int workMem, bool randomAccess);
72 extern Tuplesortstate *tuplesort_begin_index_hash(Relation indexRel,
74 int workMem, bool randomAccess);
75 extern Tuplesortstate *tuplesort_begin_datum(Oid datumType,
76 Oid sortOperator, Oid sortCollation,
78 int workMem, bool randomAccess);
80 extern void tuplesort_set_bound(Tuplesortstate *state, int64 bound);
82 extern void tuplesort_puttupleslot(Tuplesortstate *state,
83 TupleTableSlot *slot);
84 extern void tuplesort_putheaptuple(Tuplesortstate *state, HeapTuple tup);
85 extern void tuplesort_putindextuple(Tuplesortstate *state, IndexTuple tuple);
86 extern void tuplesort_putdatum(Tuplesortstate *state, Datum val,
89 extern void tuplesort_performsort(Tuplesortstate *state);
91 extern bool tuplesort_gettupleslot(Tuplesortstate *state, bool forward,
92 TupleTableSlot *slot);
93 extern HeapTuple tuplesort_getheaptuple(Tuplesortstate *state, bool forward,
95 extern IndexTuple tuplesort_getindextuple(Tuplesortstate *state, bool forward,
97 extern bool tuplesort_getdatum(Tuplesortstate *state, bool forward,
98 Datum *val, bool *isNull);
100 extern void tuplesort_end(Tuplesortstate *state);
102 extern void tuplesort_get_stats(Tuplesortstate *state,
103 const char **sortMethod,
104 const char **spaceType,
107 extern int tuplesort_merge_order(long allowedMem);
110 * These routines may only be called if randomAccess was specified 'true'.
111 * Likewise, backwards scan in gettuple/getdatum is only allowed if
112 * randomAccess was specified.
115 extern void tuplesort_rescan(Tuplesortstate *state);
116 extern void tuplesort_markpos(Tuplesortstate *state);
117 extern void tuplesort_restorepos(Tuplesortstate *state);
119 /* Setup for ApplySortFunction */
120 extern void SelectSortFunction(Oid sortOperator, bool nulls_first,
125 * Apply a sort function (by now converted to fmgr lookup form)
126 * and return a 3-way comparison result. This takes care of handling
127 * reverse-sort and NULLs-ordering properly.
129 extern int32 ApplySortFunction(FmgrInfo *sortFunction, int sortFlags,
131 Datum datum1, bool isNull1,
132 Datum datum2, bool isNull2);
134 #endif /* TUPLESORT_H */