LCOV - code coverage report
Current view: top level - src/include/utils - sortsupport.h (source / functions) Hit Total Coverage
Test: PostgreSQL 17devel Lines: 67 77 87.0 %
Date: 2024-03-29 06:11:42 Functions: 5 5 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-2024, 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   625459816 : ApplySortComparator(Datum datum1, bool isNull1,
     201             :                     Datum datum2, bool isNull2,
     202             :                     SortSupport ssup)
     203             : {
     204             :     int         compare;
     205             : 
     206   625459816 :     if (isNull1)
     207             :     {
     208      295840 :         if (isNull2)
     209      261374 :             compare = 0;        /* NULL "=" NULL */
     210       34466 :         else if (ssup->ssup_nulls_first)
     211        4992 :             compare = -1;       /* NULL "<" NOT_NULL */
     212             :         else
     213       29474 :             compare = 1;        /* NULL ">" NOT_NULL */
     214             :     }
     215   625163976 :     else if (isNull2)
     216             :     {
     217       52042 :         if (ssup->ssup_nulls_first)
     218         110 :             compare = 1;        /* NOT_NULL ">" NULL */
     219             :         else
     220       51932 :             compare = -1;       /* NOT_NULL "<" NULL */
     221             :     }
     222             :     else
     223             :     {
     224   625111934 :         compare = ssup->comparator(datum1, datum2, ssup);
     225   625111934 :         if (ssup->ssup_reverse)
     226     9443150 :             INVERT_COMPARE_RESULT(compare);
     227             :     }
     228             : 
     229   625459816 :     return compare;
     230             : }
     231             : 
     232             : static inline int
     233    44341926 : ApplyUnsignedSortComparator(Datum datum1, bool isNull1,
     234             :                             Datum datum2, bool isNull2,
     235             :                             SortSupport ssup)
     236             : {
     237             :     int         compare;
     238             : 
     239    44341926 :     if (isNull1)
     240             :     {
     241        3406 :         if (isNull2)
     242         350 :             compare = 0;        /* NULL "=" NULL */
     243        3056 :         else if (ssup->ssup_nulls_first)
     244         228 :             compare = -1;       /* NULL "<" NOT_NULL */
     245             :         else
     246        2828 :             compare = 1;        /* NULL ">" NOT_NULL */
     247             :     }
     248    44338520 :     else if (isNull2)
     249             :     {
     250         860 :         if (ssup->ssup_nulls_first)
     251          50 :             compare = 1;        /* NOT_NULL ">" NULL */
     252             :         else
     253         810 :             compare = -1;       /* NOT_NULL "<" NULL */
     254             :     }
     255             :     else
     256             :     {
     257    44337660 :         compare = datum1 < datum2 ? -1 : datum1 > datum2 ? 1 : 0;
     258    44337660 :         if (ssup->ssup_reverse)
     259     1015224 :             INVERT_COMPARE_RESULT(compare);
     260             :     }
     261             : 
     262    44341926 :     return compare;
     263             : }
     264             : 
     265             : #if SIZEOF_DATUM >= 8
     266             : static inline int
     267     5627636 : ApplySignedSortComparator(Datum datum1, bool isNull1,
     268             :                           Datum datum2, bool isNull2,
     269             :                           SortSupport ssup)
     270             : {
     271             :     int         compare;
     272             : 
     273     5627636 :     if (isNull1)
     274             :     {
     275          12 :         if (isNull2)
     276          12 :             compare = 0;        /* NULL "=" NULL */
     277           0 :         else if (ssup->ssup_nulls_first)
     278           0 :             compare = -1;       /* NULL "<" NOT_NULL */
     279             :         else
     280           0 :             compare = 1;        /* NULL ">" NOT_NULL */
     281             :     }
     282     5627624 :     else if (isNull2)
     283             :     {
     284          12 :         if (ssup->ssup_nulls_first)
     285           0 :             compare = 1;        /* NOT_NULL ">" NULL */
     286             :         else
     287          12 :             compare = -1;       /* NOT_NULL "<" NULL */
     288             :     }
     289             :     else
     290             :     {
     291     5627612 :         compare = DatumGetInt64(datum1) < DatumGetInt64(datum2) ? -1 :
     292     1665778 :             DatumGetInt64(datum1) > DatumGetInt64(datum2) ? 1 : 0;
     293     5627612 :         if (ssup->ssup_reverse)
     294        2136 :             INVERT_COMPARE_RESULT(compare);
     295             :     }
     296             : 
     297     5627636 :     return compare;
     298             : }
     299             : #endif
     300             : 
     301             : static inline int
     302    52224828 : ApplyInt32SortComparator(Datum datum1, bool isNull1,
     303             :                          Datum datum2, bool isNull2,
     304             :                          SortSupport ssup)
     305             : {
     306             :     int         compare;
     307             : 
     308    52224828 :     if (isNull1)
     309             :     {
     310       37620 :         if (isNull2)
     311       34174 :             compare = 0;        /* NULL "=" NULL */
     312        3446 :         else if (ssup->ssup_nulls_first)
     313         830 :             compare = -1;       /* NULL "<" NOT_NULL */
     314             :         else
     315        2616 :             compare = 1;        /* NULL ">" NOT_NULL */
     316             :     }
     317    52187208 :     else if (isNull2)
     318             :     {
     319        3256 :         if (ssup->ssup_nulls_first)
     320         712 :             compare = 1;        /* NOT_NULL ">" NULL */
     321             :         else
     322        2544 :             compare = -1;       /* NOT_NULL "<" NULL */
     323             :     }
     324             :     else
     325             :     {
     326    52183952 :         compare = DatumGetInt32(datum1) < DatumGetInt32(datum2) ? -1 :
     327    31370702 :             DatumGetInt32(datum1) > DatumGetInt32(datum2) ? 1 : 0;
     328    52183952 :         if (ssup->ssup_reverse)
     329     5154854 :             INVERT_COMPARE_RESULT(compare);
     330             :     }
     331             : 
     332    52224828 :     return compare;
     333             : }
     334             : 
     335             : /*
     336             :  * Apply a sort comparator function and return a 3-way comparison using full,
     337             :  * authoritative comparator.  This takes care of handling reverse-sort and
     338             :  * NULLs-ordering properly.
     339             :  */
     340             : static inline int
     341     3532124 : ApplySortAbbrevFullComparator(Datum datum1, bool isNull1,
     342             :                               Datum datum2, bool isNull2,
     343             :                               SortSupport ssup)
     344             : {
     345             :     int         compare;
     346             : 
     347     3532124 :     if (isNull1)
     348             :     {
     349         352 :         if (isNull2)
     350         352 :             compare = 0;        /* NULL "=" NULL */
     351           0 :         else if (ssup->ssup_nulls_first)
     352           0 :             compare = -1;       /* NULL "<" NOT_NULL */
     353             :         else
     354           0 :             compare = 1;        /* NULL ">" NOT_NULL */
     355             :     }
     356     3531772 :     else if (isNull2)
     357             :     {
     358           0 :         if (ssup->ssup_nulls_first)
     359           0 :             compare = 1;        /* NOT_NULL ">" NULL */
     360             :         else
     361           0 :             compare = -1;       /* NOT_NULL "<" NULL */
     362             :     }
     363             :     else
     364             :     {
     365     3531772 :         compare = ssup->abbrev_full_comparator(datum1, datum2, ssup);
     366     3531772 :         if (ssup->ssup_reverse)
     367      244338 :             INVERT_COMPARE_RESULT(compare);
     368             :     }
     369             : 
     370     3532124 :     return compare;
     371             : }
     372             : 
     373             : /*
     374             :  * Datum comparison functions that we have specialized sort routines for.
     375             :  * Datatypes that install these as their comparator or abbreviated comparator
     376             :  * are eligible for faster sorting.
     377             :  */
     378             : extern int  ssup_datum_unsigned_cmp(Datum x, Datum y, SortSupport ssup);
     379             : #if SIZEOF_DATUM >= 8
     380             : extern int  ssup_datum_signed_cmp(Datum x, Datum y, SortSupport ssup);
     381             : #endif
     382             : extern int  ssup_datum_int32_cmp(Datum x, Datum y, SortSupport ssup);
     383             : 
     384             : /* Other functions in utils/sort/sortsupport.c */
     385             : extern void PrepareSortSupportComparisonShim(Oid cmpFunc, SortSupport ssup);
     386             : extern void PrepareSortSupportFromOrderingOp(Oid orderingOp, SortSupport ssup);
     387             : extern void PrepareSortSupportFromIndexRel(Relation indexRel, int16 strategy,
     388             :                                            SortSupport ssup);
     389             : extern void PrepareSortSupportFromGistIndexRel(Relation indexRel, SortSupport ssup);
     390             : 
     391             : #endif                          /* SORTSUPPORT_H */

Generated by: LCOV version 1.14