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-2009, PostgreSQL Global Development Group
14 * Portions Copyright (c) 1994, Regents of the University of California
16 * $PostgreSQL: pgsql/src/include/utils/tuplesort.h,v 1.33 2009/06/11 14:49:13 momjian Exp $
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 two different interfaces to what is essentially the same
36 * code: one for sorting HeapTuples and one for sorting IndexTuples.
37 * They differ primarily in the way that the sort key information is
38 * supplied. Also, the HeapTuple case actually stores MinimalTuples,
39 * which means it doesn't preserve the "system columns" (tuple identity and
40 * transaction visibility info). The IndexTuple case does preserve all
41 * the header fields of an index entry. In the HeapTuple case we can
42 * save some cycles by passing and returning the tuples in TupleTableSlots,
43 * rather than forming actual HeapTuples (which'd have to be converted to
46 * The IndexTuple case is itself broken into two subcases, one for btree
47 * indexes and one for hash indexes; the latter variant actually sorts
48 * the tuples by hash code. The API is the same except for the "begin"
51 * Yet another slightly different interface supports sorting bare Datums.
54 extern Tuplesortstate *tuplesort_begin_heap(TupleDesc tupDesc,
55 int nkeys, AttrNumber *attNums,
56 Oid *sortOperators, bool *nullsFirstFlags,
57 int workMem, bool randomAccess);
58 extern Tuplesortstate *tuplesort_begin_index_btree(Relation indexRel,
60 int workMem, bool randomAccess);
61 extern Tuplesortstate *tuplesort_begin_index_hash(Relation indexRel,
63 int workMem, bool randomAccess);
64 extern Tuplesortstate *tuplesort_begin_datum(Oid datumType,
65 Oid sortOperator, bool nullsFirstFlag,
66 int workMem, bool randomAccess);
68 extern void tuplesort_set_bound(Tuplesortstate *state, int64 bound);
70 extern void tuplesort_puttupleslot(Tuplesortstate *state,
71 TupleTableSlot *slot);
72 extern void tuplesort_putindextuple(Tuplesortstate *state, IndexTuple tuple);
73 extern void tuplesort_putdatum(Tuplesortstate *state, Datum val,
76 extern void tuplesort_performsort(Tuplesortstate *state);
78 extern bool tuplesort_gettupleslot(Tuplesortstate *state, bool forward,
79 TupleTableSlot *slot);
80 extern IndexTuple tuplesort_getindextuple(Tuplesortstate *state, bool forward,
82 extern bool tuplesort_getdatum(Tuplesortstate *state, bool forward,
83 Datum *val, bool *isNull);
85 extern void tuplesort_end(Tuplesortstate *state);
87 extern char *tuplesort_explain(Tuplesortstate *state);
89 extern int tuplesort_merge_order(long allowedMem);
92 * These routines may only be called if randomAccess was specified 'true'.
93 * Likewise, backwards scan in gettuple/getdatum is only allowed if
94 * randomAccess was specified.
97 extern void tuplesort_rescan(Tuplesortstate *state);
98 extern void tuplesort_markpos(Tuplesortstate *state);
99 extern void tuplesort_restorepos(Tuplesortstate *state);
101 /* Setup for ApplySortFunction */
102 extern void SelectSortFunction(Oid sortOperator, bool nulls_first,
107 * Apply a sort function (by now converted to fmgr lookup form)
108 * and return a 3-way comparison result. This takes care of handling
109 * reverse-sort and NULLs-ordering properly.
111 extern int32 ApplySortFunction(FmgrInfo *sortFunction, int sortFlags,
112 Datum datum1, bool isNull1,
113 Datum datum2, bool isNull2);
115 #endif /* TUPLESORT_H */