Line data    Source code

       1             : /*-------------------------------------------------------------------------
       2             :  *
       3             :  * nbtcompare.c
       4             :  *    Comparison functions for btree access method.
       5             :  *
       6             :  * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group
       7             :  * Portions Copyright (c) 1994, Regents of the University of California
       8             :  *
       9             :  *
      10             :  * IDENTIFICATION
      11             :  *    src/backend/access/nbtree/nbtcompare.c
      12             :  *
      13             :  * NOTES
      14             :  *
      15             :  *  These functions are stored in pg_amproc.  For each operator class
      16             :  *  defined on btrees, they compute
      17             :  *
      18             :  *              compare(a, b):
      19             :  *                      < 0 if a < b,
      20             :  *                      = 0 if a == b,
      21             :  *                      > 0 if a > b.
      22             :  *
      23             :  *  The result is always an int32 regardless of the input datatype.
      24             :  *
      25             :  *  Although any negative int32 is acceptable for reporting "<",
      26             :  *  and any positive int32 is acceptable for reporting ">", routines
      27             :  *  that work on 32-bit or wider datatypes can't just return "a - b".
      28             :  *  That could overflow and give the wrong answer.
      29             :  *
      30             :  *  NOTE: it is critical that the comparison function impose a total order
      31             :  *  on all non-NULL values of the data type, and that the datatype's
      32             :  *  boolean comparison operators (= < >= etc) yield results consistent
      33             :  *  with the comparison routine.  Otherwise bad behavior may ensue.
      34             :  *  (For example, the comparison operators must NOT punt when faced with
      35             :  *  NAN or other funny values; you must devise some collation sequence for
      36             :  *  all such values.)  If the datatype is not trivial, this is most
      37             :  *  reliably done by having the boolean operators invoke the same
      38             :  *  three-way comparison code that the btree function does.  Therefore,
      39             :  *  this file contains only btree support for "trivial" datatypes ---
      40             :  *  all others are in the /utils/adt/ files that implement their datatypes.
      41             :  *
      42             :  *  NOTE: these routines must not leak memory, since memory allocated
      43             :  *  during an index access won't be recovered till end of query.  This
      44             :  *  primarily affects comparison routines for toastable datatypes;
      45             :  *  they have to be careful to free any detoasted copy of an input datum.
      46             :  *
      47             :  *  NOTE: we used to forbid comparison functions from returning INT_MIN,
      48             :  *  but that proves to be too error-prone because some platforms' versions
      49             :  *  of memcmp() etc can return INT_MIN.  As a means of stress-testing
      50             :  *  callers, this file can be compiled with STRESS_SORT_INT_MIN defined
      51             :  *  to cause many of these functions to return INT_MIN or INT_MAX instead of
      52             :  *  their customary -1/+1.  For production, though, that's not a good idea
      53             :  *  since users or third-party code might expect the traditional results.
      54             :  *-------------------------------------------------------------------------
      55             :  */
      56             : #include "postgres.h"
      57             : 
      58             : #include <limits.h>
      59             : 
      60             : #include "utils/fmgrprotos.h"
      61             : #include "utils/sortsupport.h"
      62             : 
      63             : #ifdef STRESS_SORT_INT_MIN
      64             : #define A_LESS_THAN_B       INT_MIN
      65             : #define A_GREATER_THAN_B    INT_MAX
      66             : #else
      67             : #define A_LESS_THAN_B       (-1)
      68             : #define A_GREATER_THAN_B    1
      69             : #endif
      70             : 
      71             : 
      72             : Datum
      73    50985310 : btboolcmp(PG_FUNCTION_ARGS)
      74             : {
      75    50985310 :     bool        a = PG_GETARG_BOOL(0);
      76    50985310 :     bool        b = PG_GETARG_BOOL(1);
      77             : 
      78    50985310 :     PG_RETURN_INT32((int32) a - (int32) b);
      79             : }
      80             : 
      81             : Datum
      82    11445336 : btint2cmp(PG_FUNCTION_ARGS)
      83             : {
      84    11445336 :     int16       a = PG_GETARG_INT16(0);
      85    11445336 :     int16       b = PG_GETARG_INT16(1);
      86             : 
      87    11445336 :     PG_RETURN_INT32((int32) a - (int32) b);
      88             : }
      89             : 
      90             : static int
      91    36504022 : btint2fastcmp(Datum x, Datum y, SortSupport ssup)
      92             : {
      93    36504022 :     int16       a = DatumGetInt16(x);
      94    36504022 :     int16       b = DatumGetInt16(y);
      95             : 
      96    36504022 :     return (int) a - (int) b;
      97             : }
      98             : 
      99             : Datum
     100       11438 : btint2sortsupport(PG_FUNCTION_ARGS)
     101             : {
     102       11438 :     SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
     103             : 
     104       11438 :     ssup->comparator = btint2fastcmp;
     105       11438 :     PG_RETURN_VOID();
     106             : }
     107             : 
     108             : Datum
     109    97455884 : btint4cmp(PG_FUNCTION_ARGS)
     110             : {
     111    97455884 :     int32       a = PG_GETARG_INT32(0);
     112    97455884 :     int32       b = PG_GETARG_INT32(1);
     113             : 
     114    97455884 :     if (a > b)
     115    37324698 :         PG_RETURN_INT32(A_GREATER_THAN_B);
     116    60131186 :     else if (a == b)
     117    20023300 :         PG_RETURN_INT32(0);
     118             :     else
     119    40107886 :         PG_RETURN_INT32(A_LESS_THAN_B);
     120             : }
     121             : 
     122             : Datum
     123      169334 : btint4sortsupport(PG_FUNCTION_ARGS)
     124             : {
     125      169334 :     SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
     126             : 
     127      169334 :     ssup->comparator = ssup_datum_int32_cmp;
     128      169334 :     PG_RETURN_VOID();
     129             : }
     130             : 
     131             : Datum
     132    16636144 : btint8cmp(PG_FUNCTION_ARGS)
     133             : {
     134    16636144 :     int64       a = PG_GETARG_INT64(0);
     135    16636144 :     int64       b = PG_GETARG_INT64(1);
     136             : 
     137    16636144 :     if (a > b)
     138     9721354 :         PG_RETURN_INT32(A_GREATER_THAN_B);
     139     6914790 :     else if (a == b)
     140      844844 :         PG_RETURN_INT32(0);
     141             :     else
     142     6069946 :         PG_RETURN_INT32(A_LESS_THAN_B);
     143             : }
     144             : 
     145             : #if SIZEOF_DATUM < 8
     146             : static int
     147             : btint8fastcmp(Datum x, Datum y, SortSupport ssup)
     148             : {
     149             :     int64       a = DatumGetInt64(x);
     150             :     int64       b = DatumGetInt64(y);
     151             : 
     152             :     if (a > b)
     153             :         return A_GREATER_THAN_B;
     154             :     else if (a == b)
     155             :         return 0;
     156             :     else
     157             :         return A_LESS_THAN_B;
     158             : }
     159             : #endif
     160             : 
     161             : Datum
     162        3208 : btint8sortsupport(PG_FUNCTION_ARGS)
     163             : {
     164        3208 :     SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
     165             : 
     166             : #if SIZEOF_DATUM >= 8
     167        3208 :     ssup->comparator = ssup_datum_signed_cmp;
     168             : #else
     169             :     ssup->comparator = btint8fastcmp;
     170             : #endif
     171        3208 :     PG_RETURN_VOID();
     172             : }
     173             : 
     174             : Datum
     175        1452 : btint48cmp(PG_FUNCTION_ARGS)
     176             : {
     177        1452 :     int32       a = PG_GETARG_INT32(0);
     178        1452 :     int64       b = PG_GETARG_INT64(1);
     179             : 
     180        1452 :     if (a > b)
     181         498 :         PG_RETURN_INT32(A_GREATER_THAN_B);
     182         954 :     else if (a == b)
     183          66 :         PG_RETURN_INT32(0);
     184             :     else
     185         888 :         PG_RETURN_INT32(A_LESS_THAN_B);
     186             : }
     187             : 
     188             : Datum
     189         102 : btint84cmp(PG_FUNCTION_ARGS)
     190             : {
     191         102 :     int64       a = PG_GETARG_INT64(0);
     192         102 :     int32       b = PG_GETARG_INT32(1);
     193             : 
     194         102 :     if (a > b)
     195          30 :         PG_RETURN_INT32(A_GREATER_THAN_B);
     196          72 :     else if (a == b)
     197          30 :         PG_RETURN_INT32(0);
     198             :     else
     199          42 :         PG_RETURN_INT32(A_LESS_THAN_B);
     200             : }
     201             : 
     202             : Datum
     203       44724 : btint24cmp(PG_FUNCTION_ARGS)
     204             : {
     205       44724 :     int16       a = PG_GETARG_INT16(0);
     206       44724 :     int32       b = PG_GETARG_INT32(1);
     207             : 
     208       44724 :     if (a > b)
     209       24464 :         PG_RETURN_INT32(A_GREATER_THAN_B);
     210       20260 :     else if (a == b)
     211        6048 :         PG_RETURN_INT32(0);
     212             :     else
     213       14212 :         PG_RETURN_INT32(A_LESS_THAN_B);
     214             : }
     215             : 
     216             : Datum
     217        1462 : btint42cmp(PG_FUNCTION_ARGS)
     218             : {
     219        1462 :     int32       a = PG_GETARG_INT32(0);
     220        1462 :     int16       b = PG_GETARG_INT16(1);
     221             : 
     222        1462 :     if (a > b)
     223         104 :         PG_RETURN_INT32(A_GREATER_THAN_B);
     224        1358 :     else if (a == b)
     225         302 :         PG_RETURN_INT32(0);
     226             :     else
     227        1056 :         PG_RETURN_INT32(A_LESS_THAN_B);
     228             : }
     229             : 
     230             : Datum
     231          36 : btint28cmp(PG_FUNCTION_ARGS)
     232             : {
     233          36 :     int16       a = PG_GETARG_INT16(0);
     234          36 :     int64       b = PG_GETARG_INT64(1);
     235             : 
     236          36 :     if (a > b)
     237           0 :         PG_RETURN_INT32(A_GREATER_THAN_B);
     238          36 :     else if (a == b)
     239           0 :         PG_RETURN_INT32(0);
     240             :     else
     241          36 :         PG_RETURN_INT32(A_LESS_THAN_B);
     242             : }
     243             : 
     244             : Datum
     245           0 : btint82cmp(PG_FUNCTION_ARGS)
     246             : {
     247           0 :     int64       a = PG_GETARG_INT64(0);
     248           0 :     int16       b = PG_GETARG_INT16(1);
     249             : 
     250           0 :     if (a > b)
     251           0 :         PG_RETURN_INT32(A_GREATER_THAN_B);
     252           0 :     else if (a == b)
     253           0 :         PG_RETURN_INT32(0);
     254             :     else
     255           0 :         PG_RETURN_INT32(A_LESS_THAN_B);
     256             : }
     257             : 
     258             : Datum
     259   206123542 : btoidcmp(PG_FUNCTION_ARGS)
     260             : {
     261   206123542 :     Oid         a = PG_GETARG_OID(0);
     262   206123542 :     Oid         b = PG_GETARG_OID(1);
     263             : 
     264   206123542 :     if (a > b)
     265    55374878 :         PG_RETURN_INT32(A_GREATER_THAN_B);
     266   150748664 :     else if (a == b)
     267    49006660 :         PG_RETURN_INT32(0);
     268             :     else
     269   101742004 :         PG_RETURN_INT32(A_LESS_THAN_B);
     270             : }
     271             : 
     272             : static int
     273   235800240 : btoidfastcmp(Datum x, Datum y, SortSupport ssup)
     274             : {
     275   235800240 :     Oid         a = DatumGetObjectId(x);
     276   235800240 :     Oid         b = DatumGetObjectId(y);
     277             : 
     278   235800240 :     if (a > b)
     279    58804944 :         return A_GREATER_THAN_B;
     280   176995296 :     else if (a == b)
     281   119628722 :         return 0;
     282             :     else
     283    57366574 :         return A_LESS_THAN_B;
     284             : }
     285             : 
     286             : Datum
     287      115228 : btoidsortsupport(PG_FUNCTION_ARGS)
     288             : {
     289      115228 :     SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
     290             : 
     291      115228 :     ssup->comparator = btoidfastcmp;
     292      115228 :     PG_RETURN_VOID();
     293             : }
     294             : 
     295             : Datum
     296     7090754 : btoidvectorcmp(PG_FUNCTION_ARGS)
     297             : {
     298     7090754 :     oidvector  *a = (oidvector *) PG_GETARG_POINTER(0);
     299     7090754 :     oidvector  *b = (oidvector *) PG_GETARG_POINTER(1);
     300             :     int         i;
     301             : 
     302             :     /* We arbitrarily choose to sort first by vector length */
     303     7090754 :     if (a->dim1 != b->dim1)
     304     1194984 :         PG_RETURN_INT32(a->dim1 - b->dim1);
     305             : 
     306    10391284 :     for (i = 0; i < a->dim1; i++)
     307             :     {
     308     7916732 :         if (a->values[i] != b->values[i])
     309             :         {
     310     3421218 :             if (a->values[i] > b->values[i])
     311     1708952 :                 PG_RETURN_INT32(A_GREATER_THAN_B);
     312             :             else
     313     1712266 :                 PG_RETURN_INT32(A_LESS_THAN_B);
     314             :         }
     315             :     }
     316     2474552 :     PG_RETURN_INT32(0);
     317             : }
     318             : 
     319             : Datum
     320    53439624 : btcharcmp(PG_FUNCTION_ARGS)
     321             : {
     322    53439624 :     char        a = PG_GETARG_CHAR(0);
     323    53439624 :     char        b = PG_GETARG_CHAR(1);
     324             : 
     325             :     /* Be careful to compare chars as unsigned */
     326    53439624 :     PG_RETURN_INT32((int32) ((uint8) a) - (int32) ((uint8) b));
     327             : }