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-2008, 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.30 2008/05/12 00:00:54 alvherre Exp $
  17  *
  18  *-------------------------------------------------------------------------
  19  */
  20 #ifndef TUPLESORT_H
  21 #define TUPLESORT_H
  22
  23 #include "access/itup.h"
  24 #include "executor/tuptable.h"
  25 #include "utils/rel.h"
  26
  27
  28 /* Tuplesortstate is an opaque type whose details are not known outside
  29  * tuplesort.c.
  30  */
  31 typedef struct Tuplesortstate Tuplesortstate;
  32
  33 /*
  34  * We provide two different interfaces to what is essentially the same
  35  * code: one for sorting HeapTuples and one for sorting IndexTuples.
  36  * They differ primarily in the way that the sort key information is
  37  * supplied.  Also, the HeapTuple case actually stores MinimalTuples,
  38  * which means it doesn't preserve the "system columns" (tuple identity and
  39  * transaction visibility info).  The IndexTuple case does preserve all
  40  * the header fields of an index entry.  In the HeapTuple case we can
  41  * save some cycles by passing and returning the tuples in TupleTableSlots,
  42  * rather than forming actual HeapTuples (which'd have to be converted to
  43  * MinimalTuples).
  44  *
  45  * The IndexTuple case is itself broken into two subcases, one for btree
  46  * indexes and one for hash indexes; the latter variant actually sorts
  47  * the tuples by hash code.  The API is the same except for the "begin"
  48  * routine.
  49  *
  50  * Yet another slightly different interface supports sorting bare Datums.
  51  */
  52
  53 extern Tuplesortstate *tuplesort_begin_heap(TupleDesc tupDesc,
  54                                          int nkeys, AttrNumber *attNums,
  55                                          Oid *sortOperators, bool *nullsFirstFlags,
  56                                          int workMem, bool randomAccess);
  57 extern Tuplesortstate *tuplesort_begin_index_btree(Relation indexRel,
  58                                                         bool enforceUnique,
  59                                                         int workMem, bool randomAccess);
  60 extern Tuplesortstate *tuplesort_begin_index_hash(Relation indexRel,
  61                                                         uint32 hash_mask,
  62                                                         int workMem, bool randomAccess);
  63 extern Tuplesortstate *tuplesort_begin_datum(Oid datumType,
  64                                           Oid sortOperator, bool nullsFirstFlag,
  65                                           int workMem, bool randomAccess);
  66
  67 extern void tuplesort_set_bound(Tuplesortstate *state, int64 bound);
  68
  69 extern void tuplesort_puttupleslot(Tuplesortstate *state,
  70                                            TupleTableSlot *slot);
  71 extern void tuplesort_putindextuple(Tuplesortstate *state, IndexTuple tuple);
  72 extern void tuplesort_putdatum(Tuplesortstate *state, Datum val,
  73                                    bool isNull);
  74
  75 extern void tuplesort_performsort(Tuplesortstate *state);
  76
  77 extern bool tuplesort_gettupleslot(Tuplesortstate *state, bool forward,
  78                                            TupleTableSlot *slot);
  79 extern IndexTuple tuplesort_getindextuple(Tuplesortstate *state, bool forward,
  80                                                 bool *should_free);
  81 extern bool tuplesort_getdatum(Tuplesortstate *state, bool forward,
  82                                    Datum *val, bool *isNull);
  83
  84 extern void tuplesort_end(Tuplesortstate *state);
  85
  86 extern char *tuplesort_explain(Tuplesortstate *state);
  87
  88 extern int      tuplesort_merge_order(long allowedMem);
  89
  90 /*
  91  * These routines may only be called if randomAccess was specified 'true'.
  92  * Likewise, backwards scan in gettuple/getdatum is only allowed if
  93  * randomAccess was specified.
  94  */
  95
  96 extern void tuplesort_rescan(Tuplesortstate *state);
  97 extern void tuplesort_markpos(Tuplesortstate *state);
  98 extern void tuplesort_restorepos(Tuplesortstate *state);
  99
 100 /* Setup for ApplySortFunction */
 101 extern void SelectSortFunction(Oid sortOperator, bool nulls_first,
 102                                    Oid *sortFunction,
 103                                    int *sortFlags);
 104
 105 /*
 106  * Apply a sort function (by now converted to fmgr lookup form)
 107  * and return a 3-way comparison result.  This takes care of handling
 108  * reverse-sort and NULLs-ordering properly.
 109  */
 110 extern int32 ApplySortFunction(FmgrInfo *sortFunction, int sortFlags,
 111                                   Datum datum1, bool isNull1,
 112                                   Datum datum2, bool isNull2);
 113
 114 #endif   /* TUPLESORT_H */