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-2010, 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 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
  44  * MinimalTuples).
  45  *
  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"
  49  * routine.
  50  *
  51  * Yet another slightly different interface supports sorting bare Datums.
  52  */
  53
  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,
  59                                                         bool enforceUnique,
  60                                                         int workMem, bool randomAccess);
  61 extern Tuplesortstate *tuplesort_begin_index_hash(Relation indexRel,
  62                                                    uint32 hash_mask,
  63                                                    int workMem, bool randomAccess);
  64 extern Tuplesortstate *tuplesort_begin_datum(Oid datumType,
  65                                           Oid sortOperator, bool nullsFirstFlag,
  66                                           int workMem, bool randomAccess);
  67
  68 extern void tuplesort_set_bound(Tuplesortstate *state, int64 bound);
  69
  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,
  74                                    bool isNull);
  75
  76 extern void tuplesort_performsort(Tuplesortstate *state);
  77
  78 extern bool tuplesort_gettupleslot(Tuplesortstate *state, bool forward,
  79                                            TupleTableSlot *slot);
  80 extern IndexTuple tuplesort_getindextuple(Tuplesortstate *state, bool forward,
  81                                                 bool *should_free);
  82 extern bool tuplesort_getdatum(Tuplesortstate *state, bool forward,
  83                                    Datum *val, bool *isNull);
  84
  85 extern void tuplesort_end(Tuplesortstate *state);
  86
  87 extern void tuplesort_get_stats(Tuplesortstate *state,
  88                                         const char **sortMethod,
  89                                         const char **spaceType,
  90                                         long *spaceUsed);
  91
  92 extern int      tuplesort_merge_order(long allowedMem);
  93
  94 /*
  95  * These routines may only be called if randomAccess was specified 'true'.
  96  * Likewise, backwards scan in gettuple/getdatum is only allowed if
  97  * randomAccess was specified.
  98  */
  99
 100 extern void tuplesort_rescan(Tuplesortstate *state);
 101 extern void tuplesort_markpos(Tuplesortstate *state);
 102 extern void tuplesort_restorepos(Tuplesortstate *state);
 103
 104 /* Setup for ApplySortFunction */
 105 extern void SelectSortFunction(Oid sortOperator, bool nulls_first,
 106                                    Oid *sortFunction,
 107                                    int *sortFlags);
 108
 109 /*
 110  * Apply a sort function (by now converted to fmgr lookup form)
 111  * and return a 3-way comparison result.  This takes care of handling
 112  * reverse-sort and NULLs-ordering properly.
 113  */
 114 extern int32 ApplySortFunction(FmgrInfo *sortFunction, int sortFlags,
 115                                   Datum datum1, bool isNull1,
 116                                   Datum datum2, bool isNull2);
 117
 118 #endif   /* TUPLESORT_H */