granicus.if.org Git - postgresql/blob - src/include/utils/tuplesort.h

   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-2014, 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_putindextuple(Tuplesortstate *state, IndexTuple tuple);
  88 extern void tuplesort_putdatum(Tuplesortstate *state, Datum val,
  89                                    bool isNull);
  90
  91 extern void tuplesort_performsort(Tuplesortstate *state);
  92
  93 extern bool tuplesort_gettupleslot(Tuplesortstate *state, bool forward,
  94                                            TupleTableSlot *slot);
  95 extern HeapTuple tuplesort_getheaptuple(Tuplesortstate *state, bool forward,
  96                                            bool *should_free);
  97 extern IndexTuple tuplesort_getindextuple(Tuplesortstate *state, bool forward,
  98                                                 bool *should_free);
  99 extern bool tuplesort_getdatum(Tuplesortstate *state, bool forward,
 100                                    Datum *val, bool *isNull);
 101
 102 extern bool tuplesort_skiptuples(Tuplesortstate *state, int64 ntuples,
 103                                          bool forward);
 104
 105 extern void tuplesort_end(Tuplesortstate *state);
 106
 107 extern void tuplesort_get_stats(Tuplesortstate *state,
 108                                         const char **sortMethod,
 109                                         const char **spaceType,
 110                                         long *spaceUsed);
 111
 112 extern int      tuplesort_merge_order(int64 allowedMem);
 113
 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  */
 119
 120 extern void tuplesort_rescan(Tuplesortstate *state);
 121 extern void tuplesort_markpos(Tuplesortstate *state);
 122 extern void tuplesort_restorepos(Tuplesortstate *state);
 123
 124 #endif   /* TUPLESORT_H */