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

   1 /*-------------------------------------------------------------------------
   2  *
   3  * sortsupport.h
   4  *        Framework for accelerated sorting.
   5  *
   6  * Traditionally, PostgreSQL has implemented sorting by repeatedly invoking
   7  * an SQL-callable comparison function "cmp(x, y) returns int" on pairs of
   8  * values to be compared, where the comparison function is the BTORDER_PROC
   9  * pg_amproc support function of the appropriate btree index opclass.
  10  *
  11  * This file defines alternative APIs that allow sorting to be performed with
  12  * reduced overhead.  To support lower-overhead sorting, a btree opclass may
  13  * provide a BTSORTSUPPORT_PROC pg_amproc entry, which must take a single
  14  * argument of type internal and return void.  The argument is actually a
  15  * pointer to a SortSupportData struct, which is defined below.
  16  *
  17  * If provided, the BTSORTSUPPORT function will be called during sort setup,
  18  * and it must initialize the provided struct with pointers to function(s)
  19  * that can be called to perform sorting.  This API is defined to allow
  20  * multiple acceleration mechanisms to be supported, but no opclass is
  21  * required to provide all of them.  The BTSORTSUPPORT function should
  22  * simply not set any function pointers for mechanisms it doesn't support.
  23  * Opclasses that provide BTSORTSUPPORT and don't provide a comparator
  24  * function will have a shim set up by sort support automatically.
  25  *
  26  * All sort support functions will be passed the address of the
  27  * SortSupportData struct when called, so they can use it to store
  28  * additional private data as needed.  In particular, for collation-aware
  29  * datatypes, the ssup_collation field is set before calling BTSORTSUPPORT
  30  * and is available to all support functions.  Additional opclass-dependent
  31  * data can be stored using the ssup_extra field.  Any such data
  32  * should be allocated in the ssup_cxt memory context.
  33  *
  34  * Note: since pg_amproc functions are indexed by (lefttype, righttype)
  35  * it is possible to associate a BTSORTSUPPORT function with a cross-type
  36  * comparison.  This could sensibly be used to provide a fast comparator
  37  * function for such cases, but probably not any other acceleration method.
  38  *
  39  *
  40  * Portions Copyright (c) 1996-2014, PostgreSQL Global Development Group
  41  * Portions Copyright (c) 1994, Regents of the University of California
  42  *
  43  * src/include/utils/sortsupport.h
  44  *
  45  *-------------------------------------------------------------------------
  46  */
  47 #ifndef SORTSUPPORT_H
  48 #define SORTSUPPORT_H
  49
  50 #include "access/attnum.h"
  51 #include "utils/relcache.h"
  52
  53 typedef struct SortSupportData *SortSupport;
  54
  55 typedef struct SortSupportData
  56 {
  57         /*
  58          * These fields are initialized before calling the BTSORTSUPPORT function
  59          * and should not be changed later.
  60          */
  61         MemoryContext ssup_cxt;         /* Context containing sort info */
  62         Oid                     ssup_collation; /* Collation to use, or InvalidOid */
  63
  64         /*
  65          * Additional sorting parameters; but unlike ssup_collation, these can be
  66          * changed after BTSORTSUPPORT is called, so don't use them in selecting
  67          * sort support functions.
  68          */
  69         bool            ssup_reverse;   /* descending-order sort? */
  70         bool            ssup_nulls_first;               /* sort nulls first? */
  71
  72         /*
  73          * These fields are workspace for callers, and should not be touched by
  74          * opclass-specific functions.
  75          */
  76         AttrNumber      ssup_attno;             /* column number to sort */
  77
  78         /*
  79          * ssup_extra is zeroed before calling the BTSORTSUPPORT function, and is
  80          * not touched subsequently by callers.
  81          */
  82         void       *ssup_extra;         /* Workspace for opclass functions */
  83
  84         /*
  85          * Function pointers are zeroed before calling the BTSORTSUPPORT function,
  86          * and must be set by it for any acceleration methods it wants to supply.
  87          * The comparator pointer must be set, others are optional.
  88          */
  89
  90         /*
  91          * Comparator function has the same API as the traditional btree
  92          * comparison function, ie, return <0, 0, or >0 according as x is less
  93          * than, equal to, or greater than y.  Note that x and y are guaranteed
  94          * not null, and there is no way to return null either.  Do not return
  95          * INT_MIN, as callers are allowed to negate the result before using it.
  96          */
  97         int                     (*comparator) (Datum x, Datum y, SortSupport ssup);
  98
  99         /*
 100          * Additional sort-acceleration functions might be added here later.
 101          */
 102 } SortSupportData;
 103
 104
 105 /*
 106  * ApplySortComparator should be inlined if possible.  See STATIC_IF_INLINE
 107  * in c.h.
 108  */
 109 #ifndef PG_USE_INLINE
 110 extern int ApplySortComparator(Datum datum1, bool isNull1,
 111                                         Datum datum2, bool isNull2,
 112                                         SortSupport ssup);
 113 #endif   /* !PG_USE_INLINE */
 114 #if defined(PG_USE_INLINE) || defined(SORTSUPPORT_INCLUDE_DEFINITIONS)
 115 /*
 116  * Apply a sort comparator function and return a 3-way comparison result.
 117  * This takes care of handling reverse-sort and NULLs-ordering properly.
 118  */
 119 STATIC_IF_INLINE int
 120 ApplySortComparator(Datum datum1, bool isNull1,
 121                                         Datum datum2, bool isNull2,
 122                                         SortSupport ssup)
 123 {
 124         int                     compare;
 125
 126         if (isNull1)
 127         {
 128                 if (isNull2)
 129                         compare = 0;            /* NULL "=" NULL */
 130                 else if (ssup->ssup_nulls_first)
 131                         compare = -1;           /* NULL "<" NOT_NULL */
 132                 else
 133                         compare = 1;            /* NULL ">" NOT_NULL */
 134         }
 135         else if (isNull2)
 136         {
 137                 if (ssup->ssup_nulls_first)
 138                         compare = 1;            /* NOT_NULL ">" NULL */
 139                 else
 140                         compare = -1;           /* NOT_NULL "<" NULL */
 141         }
 142         else
 143         {
 144                 compare = (*ssup->comparator) (datum1, datum2, ssup);
 145                 if (ssup->ssup_reverse)
 146                         compare = -compare;
 147         }
 148
 149         return compare;
 150 }
 151 #endif   /*-- PG_USE_INLINE || SORTSUPPORT_INCLUDE_DEFINITIONS */
 152
 153 /* Other functions in utils/sort/sortsupport.c */
 154 extern void PrepareSortSupportComparisonShim(Oid cmpFunc, SortSupport ssup);
 155 extern void PrepareSortSupportFromOrderingOp(Oid orderingOp, SortSupport ssup);
 156 extern void PrepareSortSupportFromIndexRel(Relation indexRel, int16 strategy,
 157                                                                                    SortSupport ssup);
 158
 159 #endif   /* SORTSUPPORT_H */