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-2007, PostgreSQL Global Development Group
  14  * Portions Copyright (c) 1994, Regents of the University of California
  15  *
  16  * $PostgreSQL: pgsql/src/include/utils/tuplesort.h,v 1.24 2007/01/05 22:20:00 momjian Exp $
  17  *
  18  *-------------------------------------------------------------------------
  19  */
  20 #ifndef TUPLESORT_H
  21 #define TUPLESORT_H
  22
  23 #include "access/itup.h"
  24 #include "executor/tuptable.h"
  25
  26
  27 /* Tuplesortstate is an opaque type whose details are not known outside
  28  * tuplesort.c.
  29  */
  30 typedef struct Tuplesortstate Tuplesortstate;
  31
  32 /*
  33  * We provide two different interfaces to what is essentially the same
  34  * code: one for sorting HeapTuples and one for sorting IndexTuples.
  35  * They differ primarily in the way that the sort key information is
  36  * supplied.  Also, the HeapTuple case actually stores MinimalTuples,
  37  * which means it doesn't preserve the "system columns" (tuple identity and
  38  * transaction visibility info).  The IndexTuple case does preserve all
  39  * the header fields of an index entry.  In the HeapTuple case we can
  40  * save some cycles by passing and returning the tuples in TupleTableSlots,
  41  * rather than forming actual HeapTuples (which'd have to be converted to
  42  * MinimalTuples).
  43  *
  44  * Yet a third slightly different interface supports sorting bare Datums.
  45  */
  46
  47 extern Tuplesortstate *tuplesort_begin_heap(TupleDesc tupDesc,
  48                                          int nkeys,
  49                                          Oid *sortOperators, AttrNumber *attNums,
  50                                          int workMem, bool randomAccess);
  51 extern Tuplesortstate *tuplesort_begin_index(Relation indexRel,
  52                                           bool enforceUnique,
  53                                           int workMem, bool randomAccess);
  54 extern Tuplesortstate *tuplesort_begin_datum(Oid datumType,
  55                                           Oid sortOperator,
  56                                           int workMem, bool randomAccess);
  57
  58 extern void tuplesort_puttupleslot(Tuplesortstate *state,
  59                                            TupleTableSlot *slot);
  60 extern void tuplesort_putindextuple(Tuplesortstate *state, IndexTuple tuple);
  61 extern void tuplesort_putdatum(Tuplesortstate *state, Datum val,
  62                                    bool isNull);
  63
  64 extern void tuplesort_performsort(Tuplesortstate *state);
  65
  66 extern bool tuplesort_gettupleslot(Tuplesortstate *state, bool forward,
  67                                            TupleTableSlot *slot);
  68 extern IndexTuple tuplesort_getindextuple(Tuplesortstate *state, bool forward,
  69                                                 bool *should_free);
  70 extern bool tuplesort_getdatum(Tuplesortstate *state, bool forward,
  71                                    Datum *val, bool *isNull);
  72
  73 extern void tuplesort_end(Tuplesortstate *state);
  74
  75 extern int      tuplesort_merge_order(long allowedMem);
  76
  77 /*
  78  * These routines may only be called if randomAccess was specified 'true'.
  79  * Likewise, backwards scan in gettuple/getdatum is only allowed if
  80  * randomAccess was specified.
  81  */
  82
  83 extern void tuplesort_rescan(Tuplesortstate *state);
  84 extern void tuplesort_markpos(Tuplesortstate *state);
  85 extern void tuplesort_restorepos(Tuplesortstate *state);
  86
  87 /*
  88  * This routine selects an appropriate sorting function to implement
  89  * a sort operator as efficiently as possible.
  90  */
  91 typedef enum
  92 {
  93         SORTFUNC_LT,                            /* raw "<" operator */
  94         SORTFUNC_REVLT,                         /* raw "<" operator, but reverse NULLs */
  95         SORTFUNC_CMP,                           /* -1 / 0 / 1 three-way comparator */
  96         SORTFUNC_REVCMP                         /* 1 / 0 / -1 (reversed) 3-way comparator */
  97 } SortFunctionKind;
  98
  99 extern void SelectSortFunction(Oid sortOperator,
 100                                    RegProcedure *sortFunction,
 101                                    SortFunctionKind *kind);
 102
 103 /*
 104  * Apply a sort function (by now converted to fmgr lookup form)
 105  * and return a 3-way comparison result.  This takes care of handling
 106  * NULLs and sort ordering direction properly.
 107  */
 108 extern int32 ApplySortFunction(FmgrInfo *sortFunction, SortFunctionKind kind,
 109                                   Datum datum1, bool isNull1,
 110                                   Datum datum2, bool isNull2);
 111
 112 #endif   /* TUPLESORT_H */