LCOV - code coverage report
Current view: top level - src/include/utils - sortsupport.h (source / functions) Hit Total Coverage
Test: PostgreSQL 13devel Lines: 23 30 76.7 %
Date: 2019-09-22 07:07:17 Functions: 2 2 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       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.  However,
      25             :  * opclasses that support the optional additional abbreviated key capability
      26             :  * must always provide an authoritative comparator used to tie-break
      27             :  * inconclusive abbreviated comparisons and also used  when aborting
      28             :  * abbreviation.  Furthermore, a converter and abort/costing function must be
      29             :  * provided.
      30             :  *
      31             :  * All sort support functions will be passed the address of the
      32             :  * SortSupportData struct when called, so they can use it to store
      33             :  * additional private data as needed.  In particular, for collation-aware
      34             :  * datatypes, the ssup_collation field is set before calling BTSORTSUPPORT
      35             :  * and is available to all support functions.  Additional opclass-dependent
      36             :  * data can be stored using the ssup_extra field.  Any such data
      37             :  * should be allocated in the ssup_cxt memory context.
      38             :  *
      39             :  * Note: since pg_amproc functions are indexed by (lefttype, righttype)
      40             :  * it is possible to associate a BTSORTSUPPORT function with a cross-type
      41             :  * comparison.  This could sensibly be used to provide a fast comparator
      42             :  * function for such cases, but probably not any other acceleration method.
      43             :  *
      44             :  *
      45             :  * Portions Copyright (c) 1996-2019, PostgreSQL Global Development Group
      46             :  * Portions Copyright (c) 1994, Regents of the University of California
      47             :  *
      48             :  * src/include/utils/sortsupport.h
      49             :  *
      50             :  *-------------------------------------------------------------------------
      51             :  */
      52             : #ifndef SORTSUPPORT_H
      53             : #define SORTSUPPORT_H
      54             : 
      55             : #include "access/attnum.h"
      56             : #include "utils/relcache.h"
      57             : 
      58             : typedef struct SortSupportData *SortSupport;
      59             : 
      60             : typedef struct SortSupportData
      61             : {
      62             :     /*
      63             :      * These fields are initialized before calling the BTSORTSUPPORT function
      64             :      * and should not be changed later.
      65             :      */
      66             :     MemoryContext ssup_cxt;     /* Context containing sort info */
      67             :     Oid         ssup_collation; /* Collation to use, or InvalidOid */
      68             : 
      69             :     /*
      70             :      * Additional sorting parameters; but unlike ssup_collation, these can be
      71             :      * changed after BTSORTSUPPORT is called, so don't use them in selecting
      72             :      * sort support functions.
      73             :      */
      74             :     bool        ssup_reverse;   /* descending-order sort? */
      75             :     bool        ssup_nulls_first;   /* sort nulls first? */
      76             : 
      77             :     /*
      78             :      * These fields are workspace for callers, and should not be touched by
      79             :      * opclass-specific functions.
      80             :      */
      81             :     AttrNumber  ssup_attno;     /* column number to sort */
      82             : 
      83             :     /*
      84             :      * ssup_extra is zeroed before calling the BTSORTSUPPORT function, and is
      85             :      * not touched subsequently by callers.
      86             :      */
      87             :     void       *ssup_extra;     /* Workspace for opclass functions */
      88             : 
      89             :     /*
      90             :      * Function pointers are zeroed before calling the BTSORTSUPPORT function,
      91             :      * and must be set by it for any acceleration methods it wants to supply.
      92             :      * The comparator pointer must be set, others are optional.
      93             :      */
      94             : 
      95             :     /*
      96             :      * Comparator function has the same API as the traditional btree
      97             :      * comparison function, ie, return <0, 0, or >0 according as x is less
      98             :      * than, equal to, or greater than y.  Note that x and y are guaranteed
      99             :      * not null, and there is no way to return null either.
     100             :      *
     101             :      * This may be either the authoritative comparator, or the abbreviated
     102             :      * comparator.  Core code may switch this over the initial preference of
     103             :      * an opclass support function despite originally indicating abbreviation
     104             :      * was applicable, by assigning the authoritative comparator back.
     105             :      */
     106             :     int         (*comparator) (Datum x, Datum y, SortSupport ssup);
     107             : 
     108             :     /*
     109             :      * "Abbreviated key" infrastructure follows.
     110             :      *
     111             :      * All callbacks must be set by sortsupport opclasses that make use of
     112             :      * this optional additional infrastructure (unless for whatever reasons
     113             :      * the opclass doesn't proceed with abbreviation, in which case
     114             :      * abbrev_converter must not be set).
     115             :      *
     116             :      * This allows opclass authors to supply a conversion routine, used to
     117             :      * create an alternative representation of the underlying type (an
     118             :      * "abbreviated key").  This representation must be pass-by-value and
     119             :      * typically will use some ad-hoc format that only the opclass has
     120             :      * knowledge of.  An alternative comparator, used only with this
     121             :      * alternative representation must also be provided (which is assigned to
     122             :      * "comparator").  This representation is a simple approximation of the
     123             :      * original Datum.  It must be possible to compare datums of this
     124             :      * representation with each other using the supplied alternative
     125             :      * comparator, and have any non-zero return value be a reliable proxy for
     126             :      * what a proper comparison would indicate. Returning zero from the
     127             :      * alternative comparator does not indicate equality, as with a
     128             :      * conventional support routine 1, though -- it indicates that it wasn't
     129             :      * possible to determine how the two abbreviated values compared.  A
     130             :      * proper comparison, using "abbrev_full_comparator"/
     131             :      * ApplySortAbbrevFullComparator() is therefore required.  In many cases
     132             :      * this results in most or all comparisons only using the cheap
     133             :      * alternative comparison func, which is typically implemented as code
     134             :      * that compiles to just a few CPU instructions.  CPU cache miss penalties
     135             :      * are expensive; to get good overall performance, sort infrastructure
     136             :      * must heavily weigh cache performance.
     137             :      *
     138             :      * Opclass authors must consider the final cardinality of abbreviated keys
     139             :      * when devising an encoding scheme.  It's possible for a strategy to work
     140             :      * better than an alternative strategy with one usage pattern, while the
     141             :      * reverse might be true for another usage pattern.  All of these factors
     142             :      * must be considered.
     143             :      */
     144             : 
     145             :     /*
     146             :      * "abbreviate" concerns whether or not the abbreviated key optimization
     147             :      * is applicable in principle (that is, the sortsupport routine needs to
     148             :      * know if its dealing with a key where an abbreviated representation can
     149             :      * usefully be packed together.  Conventionally, this is the leading
     150             :      * attribute key).  Note, however, that in order to determine that
     151             :      * abbreviation is not in play, the core code always checks whether or not
     152             :      * the opclass has set abbrev_converter.  This is a one way, one time
     153             :      * message to the opclass.
     154             :      */
     155             :     bool        abbreviate;
     156             : 
     157             :     /*
     158             :      * Converter to abbreviated format, from original representation.  Core
     159             :      * code uses this callback to convert from a pass-by-reference "original"
     160             :      * Datum to a pass-by-value abbreviated key Datum.  Note that original is
     161             :      * guaranteed NOT NULL, because it doesn't make sense to factor NULLness
     162             :      * into ad-hoc cost model.
     163             :      *
     164             :      * abbrev_converter is tested to see if abbreviation is in play.  Core
     165             :      * code may set it to NULL to indicate abbreviation should not be used
     166             :      * (which is something sortsupport routines need not concern themselves
     167             :      * with). However, sortsupport routines must not set it when it is
     168             :      * immediately established that abbreviation should not proceed (e.g., for
     169             :      * !abbreviate calls, or due to platform-specific impediments to using
     170             :      * abbreviation).
     171             :      */
     172             :     Datum       (*abbrev_converter) (Datum original, SortSupport ssup);
     173             : 
     174             :     /*
     175             :      * abbrev_abort callback allows clients to verify that the current
     176             :      * strategy is working out, using a sortsupport routine defined ad-hoc
     177             :      * cost model. If there is a lot of duplicate abbreviated keys in
     178             :      * practice, it's useful to be able to abandon the strategy before paying
     179             :      * too high a cost in conversion (perhaps certain opclass-specific
     180             :      * adaptations are useful too).
     181             :      */
     182             :     bool        (*abbrev_abort) (int memtupcount, SortSupport ssup);
     183             : 
     184             :     /*
     185             :      * Full, authoritative comparator for key that an abbreviated
     186             :      * representation was generated for, used when an abbreviated comparison
     187             :      * was inconclusive (by calling ApplySortAbbrevFullComparator()), or used
     188             :      * to replace "comparator" when core system ultimately decides against
     189             :      * abbreviation.
     190             :      */
     191             :     int         (*abbrev_full_comparator) (Datum x, Datum y, SortSupport ssup);
     192             : } SortSupportData;
     193             : 
     194             : 
     195             : /*
     196             :  * Apply a sort comparator function and return a 3-way comparison result.
     197             :  * This takes care of handling reverse-sort and NULLs-ordering properly.
     198             :  */
     199             : static inline int
     200  1178689894 : ApplySortComparator(Datum datum1, bool isNull1,
     201             :                     Datum datum2, bool isNull2,
     202             :                     SortSupport ssup)
     203             : {
     204             :     int         compare;
     205             : 
     206  1178689894 :     if (isNull1)
     207             :     {
     208      159744 :         if (isNull2)
     209      151782 :             compare = 0;        /* NULL "=" NULL */
     210        7962 :         else if (ssup->ssup_nulls_first)
     211        3662 :             compare = -1;       /* NULL "<" NOT_NULL */
     212             :         else
     213        4300 :             compare = 1;        /* NULL ">" NOT_NULL */
     214             :     }
     215  1178530150 :     else if (isNull2)
     216             :     {
     217       25784 :         if (ssup->ssup_nulls_first)
     218         310 :             compare = 1;        /* NOT_NULL ">" NULL */
     219             :         else
     220       25474 :             compare = -1;       /* NOT_NULL "<" NULL */
     221             :     }
     222             :     else
     223             :     {
     224  1178504366 :         compare = ssup->comparator(datum1, datum2, ssup);
     225  1178504366 :         if (ssup->ssup_reverse)
     226     4766836 :             INVERT_COMPARE_RESULT(compare);
     227             :     }
     228             : 
     229  1178689894 :     return compare;
     230             : }
     231             : 
     232             : /*
     233             :  * Apply a sort comparator function and return a 3-way comparison using full,
     234             :  * authoritative comparator.  This takes care of handling reverse-sort and
     235             :  * NULLs-ordering properly.
     236             :  */
     237             : static inline int
     238      424150 : ApplySortAbbrevFullComparator(Datum datum1, bool isNull1,
     239             :                               Datum datum2, bool isNull2,
     240             :                               SortSupport ssup)
     241             : {
     242             :     int         compare;
     243             : 
     244      424150 :     if (isNull1)
     245             :     {
     246          10 :         if (isNull2)
     247          10 :             compare = 0;        /* NULL "=" NULL */
     248           0 :         else if (ssup->ssup_nulls_first)
     249           0 :             compare = -1;       /* NULL "<" NOT_NULL */
     250             :         else
     251           0 :             compare = 1;        /* NULL ">" NOT_NULL */
     252             :     }
     253      424140 :     else if (isNull2)
     254             :     {
     255           0 :         if (ssup->ssup_nulls_first)
     256           0 :             compare = 1;        /* NOT_NULL ">" NULL */
     257             :         else
     258           0 :             compare = -1;       /* NOT_NULL "<" NULL */
     259             :     }
     260             :     else
     261             :     {
     262      424140 :         compare = ssup->abbrev_full_comparator(datum1, datum2, ssup);
     263      424140 :         if (ssup->ssup_reverse)
     264           0 :             INVERT_COMPARE_RESULT(compare);
     265             :     }
     266             : 
     267      424150 :     return compare;
     268             : }
     269             : 
     270             : /* Other functions in utils/sort/sortsupport.c */
     271             : extern void PrepareSortSupportComparisonShim(Oid cmpFunc, SortSupport ssup);
     272             : extern void PrepareSortSupportFromOrderingOp(Oid orderingOp, SortSupport ssup);
     273             : extern void PrepareSortSupportFromIndexRel(Relation indexRel, int16 strategy,
     274             :                                            SortSupport ssup);
     275             : 
     276             : #endif                          /* SORTSUPPORT_H */

Generated by: LCOV version 1.13